pekempeyのブログ

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

HL分解 (Heavy-Light Decomposition)

HL分解で解ける問題を最近よく見る。(想定解法であるかどうかは別として)

No.235 めぐるはめぐる (5) - yukicoder
F: 根付き木のみさわさん - 天下一プログラマーコンテスト2015本戦(オープンコンテスト) | AtCoder
Problem - 588E - Codeforces
Problem - 593D - Codeforces

HL分解については、この記事がとてもわかりやすい。
math314.hateblo.jp

HL分解については既に分かりやすい記事があるので、この記事では木をパスに分解してクエリするという考え方について説明する。

たとえば、パス上の値の総和を求めるというものを考える。
f:id:pekempey:20151106183847p:plain
今回のクエリの答えは2+3+4+9+6+4+7+5=40。

一次元であればSegment TreeやBITなどで計算できる。実は木をパスに分解することにより、このようなクエリに対してもSegment TreeやBITを使うことができる。

まず木をパスに分解するというのは、こんな感じのイメージ。
f:id:pekempey:20151106174136p:plain

それぞれのパスに対して、根に近い方から順に番号を割り振っていく。ついでにパスにも番号を振っておく。
f:id:pekempey:20151106180216p:plain

最初の例のクエリはこんな感じだった。
f:id:pekempey:20151106184618p:plain

このクエリを計算するには
path 0: [0,1]
path 1: [0,1]
path 3: [0,0]
path 4: [0,1]
path 5: [0,0]
に対するクエリをそれぞれ計算してマージすればいいことがわかる。たとえば総和クエリだったら、それぞれのパスのクエリ結果を計算して足すだけである。

さてここで問題になるのはu-vパスクエリを計算するときに必要になるパスの数だ。実はパスの分解方法にHL分解を使うと必要な数がO(log n)になる。つまりSegmentTreeを用いれば、クエリ一回あたりO(log^2 n)で計算できる。

実装

パス add、パス sum の問題の解答コードを書いておきます。自分が持っているライブラリをそのまま使っているので、この問題を解くのに不要な関数も含まれています。

HL分解には様々な実装方法があるので、この実装だけでなく他の実装も参照することをおすすめします。今回用意した実装は、パスごとにセグメント木を用意するのではなく、セグメント木一個にまとめています。

区間に分解する作業しかライブラリでは行っていないので、既存の segment tree や BIT などとすぐに組み合わせられると思います(内部処理を知らなくても使えるレベルにしたつもりですが、よく考えると一点更新に罠があるかもしれません。書き直したい箇所もあるので、余裕ができたら修正しようと思っています)


余談

これは体感的なものなのですが、HL分解のLCAの方がダブリングやオイラーツアーによるLCAよりも高速に動くような気がします。まあ速度はオカルトかもしれませんが、少なくとも構築と空間に関してはダブリングやオイラーツアーより優位です。