Heavy-Light Decomposition

概要

木上pathをO(log N)本の連続区間へ分解し、配列data structure上のqueryへ変換する。

Heavy-Light Decomposition(HLD)は、根付き木の各頂点で部分木サイズ最大の子への辺をheavy、それ以外をlightとして分ける。heavy辺が連なるpathを連続した配列区間へ写し、木のpathを区間列として扱う。

light辺を子へ降りると部分木サイズは半分未満になるため、根へのpathが通るlight辺はO(log N)本。任意の二頂点間のpathもO(log N)個のheavy path区間に分かれる。分解の前処理はO(N)、各区間をsegment treeでO(log N)処理するならpath queryはO(log² N)。

和や最大値なら区間の向きを無視できるが、行列積や文字列の連結では結合順を保つ必要がある。両端からLCAへ向かう区間を分け、逆向き集約も用意する。辺に値を置くときはLCA自身の頂点位置を除外する。

考え方

最大の子部分木へ進む辺をheavyにし、他をlightにする。light辺を上へ越えるたび部分木サイズが少なくとも倍になるため、一pathをO(log N)本のheavy pathへ分けられる。

一回目のDFSでsize[v]=1+Σ size[child]と最大の子heavy[v]を作る。二回目はheavy childを最初に訪問するDFSでposを連番にし、heavy childはheadを親から継承、light childは自分自身をheadにする。これで一heavy pathが配列上で連続する。

二頂点u,vのheadが違う間は、headの深い側(例えばu)の [pos[head[u]],pos[u]+1) をqueryへ渡し、u=parent[head[u]]へ上げる。同じheadになったら両pos間の区間を処理する。非可換のpath積では、u側の区間を逆順にして左累積へ追加、v側の区間を正順にして右累積の先頭へ追加し、最後に結合する。辺値を子頂点posへ置くときは、最後の同head区間の浅い端(LCA)を一つ除く。各段でlight edgeを一本越すので区間数O(log N)である。

成立条件と計算量

構築O(N)、Segment Treeを使うpath queryは典型的にO(log² N)。非可換の合成は向きを反転した要約も必要。頂点値と辺値でLCAを含めるかが違うため、区間端点を固定する。

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 青色(1600–1999)。軽い辺の回数を界し、pathを少数の区間に分解して順序付きqueryを処理する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 木のancestor・部分木・pathを索引化する。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-heavy-light-decomposition

Heavy-Light Decomposition

習得する技能

  • heavy childを選んで木をheavy path列へ分け、path range queryまたはbalanced tree-cluster構築へ接続できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: ancestor query・LCA、Euler順による部分木区間化。

このUnitを直接前提とする単元: なし。

ancestor query・LCA・Euler順による部分木区間化で得た考え方と実装を再利用し、Heavy-Light Decompositionの発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • Heavy-Light Decompositionの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠