HL decomposition+SegTreeのlogを1個消す

はじめに

この記事はHL分解について書きます。

HL分解+SegTreeでパス上のクエリに答えると、最悪ケースで O(log2 N) per query ですが、これを O(logN) per query に改善したいと思います。

イデア

HL分解の詳細についての解説は省きます。たくさんネットに資料は転がっているので探してください。

HL分解+SegTreeでパス上のクエリに答えるのは

  • 木をHL分解でパスに分解し
  • パスをSegTreeで管理する

という 2ステップからなります。パスに分解してまとめた後の木の高さが O(logN)、そのパスへのクエリが O(logN) で、合わせて計算量は O(log2 N) です。

実は 2つめのステップで、あえてアンバランス(完全二分木ではない)なSegTreeを使うことで、logを1つ落とすことができます。 1つめのステップは普通のHL分解と全く同一です。(ただし、最も子の中で部分木のサイズが大きいものをheavy-pathとして選ぶものとする。)(本家は部分木が小さいのばっかだったらheavy-pathを選ばない?)

まず、ノードごとに以下のように重みを定義します。

  • weight[p] = pの部分木のサイズ - pのheavy-pathに選んだ子の部分木のサイズ(もしpがheavy-pathの末端なら0)

そして、Segtreeは普通、左右のNodeの数が等しくなるように分割していきますが、これをweight[p]の和が左右でできる限り等しくなるように分割していくだけで計算量が改善されます。

具体的には、"2段降りるとweightの和が1/2以下になるように"構築することができます。(多分)

計算量解析

Mi_Sawaさんに行けそうじゃないこれ?と言ったらいい感じの説明が帰ってきました。↓です。

再帰的に考えます。サイズAの木について、その根から生えるheavy-pathを考えます。そのheavy-path上の頂点pについて、weight[p] = B と仮定したらpは上から何段目に存在するでしょうか。

これは2段降りるとweightの和が1/2以下になることを考えると、O(log(A/B)) + O(1) です。

そしてその後はサイズKの木について考えれば良いので、結局 O(log(A/B)) + O(log(B/C)) +O(log(C/D)) ... = O(logA) が成立し、左辺の足し算の項の数は O(logN)個なので、良さそうです。

実測

一応実装しました。 実験の題材はかの有名なDo use segment treeです。 AOJに投げるとなんか遅いです。普通のHL分解+SegTreeと速度が変わりません。考えさせられますね。びっくりしました。

遅いケース(test8)を手元で動かすと最速タイ(LinkCut, 0.23s)とほとんど速度が変わらないのでお手上げです。

というわけで、手元で計測する卑怯な方法に出ます。

計測法は3回測って平均です。クソ適当。

木の形は完全二分木 (N=217 -1 = 131071) クエリは Q=1,000,000 で完全ランダムのテストケースメーカを作り、実験しました。

普通のHL分解が 3.06sec で、今回のHL分解が 2.66sec、LC-Treeは4.10sです。 クエリ数が多いとやっぱり有利です。

また、HL分解の最悪ケースっぽいものを作って実験しました。 これはN=196606, Q=1,000,000 です。

普通のHL分解が 4.17sec で、今回のHL分解が 2.53sec、LC-Treeは3.27sです。

なお、比較対象の普通のHL分解ってのは定数倍が遅いです。配列に展開せずポインタですし。実装に疲れてしまった。

コード

テストケースジェネレーター

完全二分木

gist.github.com

悪質ケース

gist.github.com

HL分解

37行目と38行目をいじることで普通のHL分解と今回のHL分解が変えられます。

gist.github.com