【ポエム】Rake Edge を Splay Tree で管理する Link Cut Tree の各種操作は O(log N) と言って差し支えないのではないかという話．

前提

Nachiaさんの記事¹において競技プログラミングとTopTreeの関係が良くまとめられている．ei1333 さんの記事 ² では Rake Edge を Splay Tree で管理する Link Cut Tree について深堀されている．また、この記事は ei1333 さんの記事² をみて作られたポエムなので名称等をいくつか引用して用いている．

主張

TopTree の variant として競技プログラマの間ではよく知られているこの つよい LCT であるが、この計算量が 償却 $\mathcal{O}(\log N)$ であることは予想であるとして語られがち¹²である．
本記事は、直にこの事実を主張する論文こそ知られていないが、Link Cut Tree の計算量解析の系として少し解析を改変すれば得られるものであり、証明出来ているものとして扱って良いのではないかと主張する目的で作られた物である．ただし、これはあくまでもポエムなので厳密な論証は元論文に当たってほしい．

splay tree の 計算量解析

論文の³ 証明の概略を書く．本記事では splay 操作にしか触れないためぜひ元論文を読んでみて欲しい．

ポテンシャルの定義

頂点に重み $W(v)$ を定義し、各頂点の部分木に対する重みの和の積をポテンシャルとして解析する．
$x$ をsplayする事を考える時に
$
S(x)=\text{(ステップ前のxの部分木の重み和)}
$
$
S'(x)=\text{(ステップ後のxの部分木の重み和)}
$
と定義すると親の部分木の重み和は子のそれより大きいので、各ステップにおいてうまく比率が抑えられる．

zig step

zigステップの場合重みが変化するのは $x$ とその親 $p$ なので、変化率は $(S'(x)*S'(p))/(S(x)*S(p))$
変化前xの親はpで変化後pの親はxなのでこれは $(S'(x)/S(x))^2$ より小さい

zig-zag/zig-zig step

同様に $(S'(x)/S(x))^3$ で抑えられるが、さらに相加相乗平均の関係を使って少し厳しく評価すると $(S'(x)/S(x))^3/4$ 以下であることが言える．

全体のポテンシャルの定義

以上より、全体でポテンシャルが一回の splay操作で高々 $\frac{(S'(x)/S(x))^3}{4^\text{(xのsplay前の深さ)}}$ 倍にしかならない事が言える．

ここで、 $W(x)=1$　と置けば splay treeが償却 $\mathcal{O}(\log N)$ であることを簡単に示せる．
また、 この事実は zig-step が償却 $\mathcal{O}(\log N)$ 回行われてもポテンシャルが $\frac{(S'(x)/S(x))^3}{4^\text{(xのsplay前の深さ)}-\mathcal{O}(\log N)}$ になるだけなので成り立ち、これこそが link/cut tree の計算量が $\mathcal{O}(\log N)$ となるのに必要なトリックである．

link/cut tree の計算量解析

ここにある議論はこの論文⁴を元にしたものであるが Wikipedia にも書かれている⁵
まず、解析のため HL分解を始めに行い、 heavy edge と light edge を決める．
次に compress edge を よわい LCT において
あるノードに対し、HL分解におけるその子とのheavy edgeは一つのみなので、
link/cut tree に compress edge として使用されている heavy edge の数をポテンシャルに持つと．

• heavy -> light : ポテンシャル $+1$
• light -> heavy : ポテンシャル $-1$
• light -> light : HL分解の性質より 根までに light edge を $\mathcal{O}(\log N)$ 回しか通らないため、 $\mathcal{O}(\log N)$ 回
• heavy -> heavy : HL分解の性質より起こりえない

このことからノード入れ替え、すなわち zig-step の上限回数は 償却 $\mathcal{O}(\log N)$ 回となる．これを splay tree の先ほどの議論を合わせて link/cut tree の計算量解析となる．
これはつよいLCT においても同様である (compress-rake-compress-rake の様に交互に通るため)．

結論

splay tree は 償却 $\mathcal{O}(\log N)$ 回までの zig-step を行っても 計算量は変わらず、 よわいLCT と つよいLCT はどちらも zig-step を $\mathcal{O}(\log N)$ に抑えているため、 つよいLCT も同様に抑えられる．

おまけ biased search tree について

biased search tree⁴⁶ という概念を用意するとさらに簡単に議論できる．
biased search tree は良くアクセスする場所に速くアクセスしたいというような要求に対してのある種の解となる概念で、与えられた重み関数 $w(v)$ に対して 頂点 $v$ に $\mathcal{O}(\log{\frac{\sum_{v \in V} w(v)}{w(v)}})$ でのアクセスが可能な平衡二分探索木の事であり、 これは償却計算量の意味で任意の重みに対し splay tree にも成り立つ(元論文の補題2¹)．これを認めてしまえば計算量解析は簡単で、部分木の重みを頂点に持たせて望遠鏡和を考えれば、償却 $\mathcal{O}(\log N)$．

参考文献

1. https://www.mathenachia.blog/top-trees-intro/ ↩ ↩² ↩³

2. https://ei1333.hateblo.jp/entry/2024/05/05/012015 ↩ ↩² ↩³

3. Sleator, D. D., & Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3), 652-686. ↩

4. Sleator, D. D., & Tarjan, R. E. (1981, May). A data structure for dynamic trees. In Proceedings of the thirteenth annual ACM symposium on Theory of computing (pp. 114-122). ↩ ↩²

5. https://en.wikipedia.org/wiki/Link/cut_tree ↩

6. Bent, S. W., Sleator, D. D., & Tarjan, R. E. (1985). Biased search trees. SIAM Journal on Computing, 14(3), 545-568. ↩