pekempelog

ペケンペイのブログ

HL分解 (Heavy-Light Decomposition)

HL 分解 (heavy-light decomposition) についてではなく、パスクエリを複数の列クエリに分解するという考え方について説明する。HL 分解は木が与えられて次の二種類のクエリを処理する問題等で用いられる。

  • uv パス上のすべての頂点にxを加算する
  • uv パス上の値の総和を求める


f:id:pekempey:20170806195644p:plain:w400

総和クエリの例。この場合は 2+3+4+9+6+4+7+1=36 が答えになる

木ではなく列であれば segment tree によって効率的に処理できる。HL 分解は木をパスに分解することで、木の問題を列の問題に還元する。木をパスに分解するとはどういうことだろうか。例えば次の図のようなものが木をパスに分解した例になっている。

f:id:pekempey:20170806195717p:plain:w500

冒頭で例に出したクエリは次の形に分解できる。

f:id:pekempey:20170806195733p:plain

このクエリはsum[16..16] + sum[13..14] + sum[0..1] + sum[6..8]で計算できる。個々のクエリは segment tree 等で効率的に処理できるため、全体としても効率的に処理できる。なお、パスクエリは複数の列クエリに分解されるが、このとき列クエリの総数は O(log n) 個で抑えられる。詳しくは HL 分解について調べると良いだろう。

References

計算量解析で使っている論文の存在は確認しているが、アルゴリズム内で陽に現れるものは調査できていない。