pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

HL分解 (Heavy-Light Decomposition)

この記事ではHL分解の原理ではなく使い方を説明する。

HL分解を使う問題例

n頂点の木が与えられる。以下の二種類のクエリが飛んでくる。

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


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

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

木ではなく数列であれば有名なセグメント木の問題である。実は木をパスに分解することで、このようなクエリに対してもセグメント木を使うことができる。

パス分解

木を複数のパスに分解したものを図に示す。同一パスに含まれる頂点は連番になるようにラベリングしている。

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

冒頭のクエリの計算方法を雰囲気で示す。

f:id:pekempey:20170806195733p:plain

このパスクエリはsum[16..16] + sum[13..14] + sum[0..1] + sum[6..8]で計算できる。sum[L..R]はセグメント木やFenwick Treeで計算すれば良い。

パスの分解にHL分解を用いると、uvパスクエリを計算するときに参照するパスの数が O(log N) になる。

更新履歴

  • (2017/8/6) 昔に書いた実装がいつまでも参照されるのは良くないと思い、実装例を消しました。実装例を見たいのであれば、問題の提出一覧からコードを探すのが良いかと思います。
  • (2017/8/6) 内容をかなり書き換えました。