セグメント木の理屈を学ぶ(1) データ構造とモノイド構造の整合性 の続きです。
前回はセグメント木のデータ構造と操作を定義し、それが期待通りに動くことを証明しました。
今回は、前回「天下り的に与えた」と書いた定義が、実はなるべくしてなった定義であることを見ていくとともに、木としての幾何的な構造が効いてくる場所を解き明かしていきます。
前提
- 前回の記事の設定と記法をそのまま引き継ぎます。
- 圏、関手、自然変換を断りなく使いますが、必要になるのは定義のレベルまでです。
- 今回もモノイドは可換性を仮定しません。
不変条件とは何なのか？
前回の記事は以下のような構成をしていました。
- 木の各ノードに値 \(v_\tau\) を持たせ、不変条件 \(v_\tau = \prod_{i \in \mathrm{seg}(\tau)} a_i\) を課す。
SetとQueryの疑似コードを与える。- それらが不変条件を保ち、正しい答えを返すことを証明する。
今回より詳しく調べるのは、なぜ Set や Query があのような疑似コードになるかです。
セグメント木の「効率的に演算ができる『配列っぽさ』」を明確に定式化していくことで理解を深めていきます。
前回、不変条件というものを定義しましたが、今回は次を示します。
不変条件とは、木の状態空間と配列の空間の間の同型のことである。
これを認めると、Set と Query は同型で移送するだけで一意に定まってしまい、疑似コードには「何を計算するか」という自由度が最初から存在しなかったことがわかります。そして同型であるということは、木が情報としては配列と区別できないということでもあります。
一方、この同型からはセグメント木の効率性は導出できません。ここが面白いところですね。
セグメント木の状態空間 \(\mathrm{Seg}_d(M)\)
では初めていきます。まず、木の「あり得る状態」の集合を定義します。
深さ \(d\) の完全二分木のノード集合を \(T_d\) と書きます。\(|T_d| = 2^{d+1}-1\) です。木の状態とは各ノードにモノイドの元を割り当てたもの、すなわち \(M^{T_d}\) の元ですが、前回の不変条件を満たすものだけがセグメント木として意味のある状態です。
そこで、モノイド \(M\) 上の深さ \(d\) のセグメント木の状態空間 \(\mathrm{Seg}_d(M)\) を
$$ \mathrm{Seg}_d(M) = \{ v \in M^{T_d} \mid v_\tau = v_{\text{lch}(\tau)}\cdot v_{\text{rch}(\tau)} \quad (\forall h(\tau) > 0) \} $$と定義します。これは葉でないノードに対して、「親は子の積である」という局所的な条件だけを課した集合であることに注意してください。区間 \(\mathrm{seg}(\tau)\) も配列 \(a\) も、この定義には登場しません。
葉への制限写像
\(2^d = n\) 個ある葉のうち、インデックス \(i\) に対応する葉を \(\mathrm{leaf}(i)\) と書きます。
セグメント木の状態空間を葉に制限する
$$ \begin{align*} \pi_d : \mathrm{Seg}_d(M) &\longrightarrow M^{n}\\\\ v &\longmapsto \bigl(v_{\mathrm{leaf}(0)}, \ldots, v_{\mathrm{leaf}(n-1)}\bigr) \end{align*} $$が、これから主役になる写像です。管理したい配列 \(a\) は、木の葉に置かれた値そのものですから、\(\pi_d\) は「木の状態から、それが表している配列を読み出す写像」に相当します。
補題2 の再解釈: \(\pi_d\) は全単射
前回、補題2で Set 操作により不変条件が保存されることを確認しました。先ほど定義した \(\pi_d\) が全単射であることを示し、不変条件を別の角度から捉えてみます。
命題7
\(\pi_d\) は全単射である。さらにその逆写像は
$$ (\pi_d^{-1}(a))_\tau = \prod_{i \in \mathrm{seg}(\tau)} a_i $$で与えられる。
見ての通り、右辺は前回の不変条件そのものです。つまり前回の不変条件は「\(v\) が \(a\) に対応する唯一の状態、すなわち \(v = \pi_d^{-1}(a)\) であること」を書き下したものだった、ということになります。
証明は前回と同様に高さに関する帰納法でもできますが、次の分解を使うと \(d\) に関する帰納法で短く書けます。前回の補題2 とは別筋なので、こちらを紹介します。
補題8 (再帰的分解)
\(d \ge 0\) について、根の子を根とする左右の部分木への制限は全単射
$$ \rho : \mathrm{Seg}_{d+1}(M) \xrightarrow{\ \sim\ } \mathrm{Seg}_{d}(M) \times \mathrm{Seg}_{d}(M) $$を与える。
証明. 深さ \(d+1\) の木は、根 \(\tau_0\) と、その子 \(\tau_1, \tau_2\) を根とする深さ \(d\) の部分木 2 つからなる。\(v \in M^{T_{d+1}}\) に対し、内部ノードにおける条件を根とそれ以外に分けると、
- 根における条件: \(v_{\tau_0} = v_{\tau_1}\cdot v_{\tau_2}\)
- それ以外の内部ノードにおける条件: 左右の部分木への制限がそれぞれ \(\mathrm{Seg}_d(M)\) に属すること
と書ける。したがって \(v \in \mathrm{Seg}_{d+1}(M)\) を与えることは、 \(\mathrm{Seg}_d(M)\) の元の組 \((v|_{\tau_1}, v|_{\tau_2})\) を与えることと同じである。 根の値 \(v_{\tau_0}\) は組から一意に決まり、逆に任意の組に対して根の値をそう定めれば条件を満たす。◼️
根自体は情報がなく、値が組から決まってしまうという点が要点です。
命題7 の証明
\(d\) に関する帰納法で示す。
\(d = 0\) のとき、木はノード 1 つ(根であり葉である)からなり、内部ノードが無いので条件は空、 \(\mathrm{Seg}_0(M) = M^{T_0} = M\) であって \(\pi_0\) は恒等写像である。
\(d\) で成立するとする。モノイドの列を前半と後半に分ける同型 \(M^{2^{d+1}} \cong M^{2^d} \times M^{2^d}\)のもとで、図式
$$ \begin{CD} \mathrm{Seg}_{d+1}(M) @>{\rho}>> \mathrm{Seg}_{d}(M)\ \times \ \mathrm{Seg}_{d}(M) \\ @V{\pi_{d+1}}VV @VV{\pi_d\times\pi_d}V \\ M^{2^{d+1}} @>{\sim}>> M^{2^{d}}\ \times \ M^{2^{d}} \end{CD} $$は可換である(深さ \(d+1\) の木の葉の前半は左部分木の葉、後半は右部分木の葉に他ならないため)。補題8 より \(\rho\) は全単射、帰納法の仮定より \(\pi_d\times\pi_d\) は全単射、下の横向きの写像は全単射なので、\(\pi_{d+1}\) も全単射である。
逆写像の表示は、\((\pi_d^{-1}(a))_\tau := \prod_{i\in\mathrm{seg}(\tau)} a_i\) と定めたものが \(\mathrm{Seg}_d(M)\) に属し(結合則: 親の区間は子の区間の順序を保った非交和なので、親の積は子の積の積に等しい)、葉で \(a_i\) を与えることから従う。◼️
一点注意を述べておきます。\(n\) が 2 冪でない場合、単位元でパディングして \(M^n \to M^{2^d}\) と埋め込んでいました。 この写像は準同型と可換する自然な写像ですが、単射なだけで同型ではありません。そのため、2 冪でない場合にはそのまま同じ議論はできません。
操作は一意に決まる
配列側で、私たちが本当に欲しかった操作は
\(i\) 番目を書き換える
$$ \begin{align*} \mathrm{set}_i : M \times M^n &\longrightarrow M^n\\ (c, a) &\longmapsto (a_0,\ldots,a_{i-1}, c, a_{i+1},\ldots,a_{n-1}) \end{align*} $$と区間の積を取る
$$ \begin{align*} \mu_{[l:r]} : M^n &\longrightarrow M\\ a &\longmapsto \prod_{i\in[l:r]} a_i \end{align*} $$2 つの操作でした。
さて、命題7 により \(\pi_d\) は全単射でした。したがって木側の操作は、配列側の操作を \(\pi_d\) で移送することで一意に定まります。
$$ \begin{align*} \mathrm{Set}_i &:= \pi_d^{-1} \circ \mathrm{set}_i \circ (\mathrm{id}_M \times \pi_d)\\ \mathrm{Query}_{[l:r]} &:= \mu_{[l:r]} \circ \pi_d \end{align*} $$「一意に」というのは、次の2つの図式を可換にする木側の写像は他にない、という意味です。
$$ \begin{CD} M\ \times \ \mathrm{Seg}_d(M) @>{\mathrm{Set}_i}>> \mathrm{Seg}_d(M) \\ @V{\mathrm{id} \ \times \ \pi_d}V{\sim}V @V{\sim}V{\pi_d}V \\ M\ \times \ M^n @>{\mathrm{set}_i}>> M^n \end{CD} $$$$ \begin{CD} \mathrm{Seg}_d(M) @>{\mathrm{Query}_{[l:r]}}>> M \\ @V{\pi_d}V{\sim}V @| \\ M^n @>{\mu_{[l:r]}}>> M \end{CD} $$そして、前回の補題2・補題3 が主張していたのは、まさに
疑似コードで書いた再帰手続きは、この一意に定まる写像と一致する
ということでした。前回「天下り的に与えた」と書いた Set, Query は配列側の操作から自動的に決まってくるようなものだったということですね。
厳密に言えば、疑似コードは \(M^{T_d}\) 全体の上で動く手続きではあるので、主張は「その手続きは部分集合 \(\mathrm{Seg}_d(M)\) を保ち、そこへの制限が上の写像に一致する」となります。前回の補題2 が不変条件の保存を言っていたのは、この「\(\mathrm{Seg}_d(M)\) を保つ」の部分に対応します。
こうして前回の補題の役割分担が見えます。
- 補題2・補題3 (正当性): 疑似コードが、一意に定まった写像と一致することの確認。
- 補題4・補題6 (計算量): それが \(O(\log n)\) で計算できることの主張。
存在と一意性は \(\pi_d\) が同型であることから自明でした。非自明なのは後者だけです。
実際、\(\mathrm{Set}_i\) の定義をそのまま実装すれば、\(\pi_d\) で配列を読み出し、書き換え、\(\pi_d^{-1}\) で木を作り直すことになり、これは \(O(n)\) かかります。
疑似コードは、変化しない部分を再計算せずに工夫することで、同じ写像をより効率的に求めているわけですね。
準同型との整合性
もう一つ、この定式化から自然に出てくる性質を見ます。
\(\mathrm{Seg}_d\) は関手である
モノイドの準同型 \(f : M \to N\) に対し、成分ごとの適用 \(f^{T_d} : M^{T_d}\to N^{T_d}\) を考えると、これは整合性条件を保ちます。実際 \(v_\tau = v_{\tau_1}\cdot v_{\tau_2}\) なら
$$ f(v_\tau) = f(v_{\tau_1}\cdot v_{\tau_2}) = f(v_{\tau_1})\cdot f(v_{\tau_2}) $$です。よって
$$ \mathrm{Seg}_d(f) : \mathrm{Seg}_d(M)\to\mathrm{Seg}_d(N) $$が定まり、
$$ \mathrm{Seg}_d(\mathrm{id}) = \mathrm{id}, \mathrm{Seg}_d(g\circ f) = \mathrm{Seg}_d(g)\circ\mathrm{Seg}_d(f) $$も成分ごとに明らかなので、\(\mathrm{Seg}_d\) は関手 \(\mathbf{Mon}\to\mathbf{Set}\) です。\((-)^n\) も同様に関手であり、\(\pi_d\) は成分の取り出しなので
$$ \begin{CD} \mathrm{Seg}_d(M) @>{\pi_d}>{\sim}> M^n \\ @V{\mathrm{Seg}_d(f)}VV @VV{f^n}V \\ \mathrm{Seg}_d(N) @>{\pi_d}>{\sim}> N^n \end{CD} $$は可換で、
$$ \pi : \mathrm{Seg}_d \Longrightarrow (-)^{n} $$は自然変換、しかも各成分が全単射なので自然同型です。
操作も準同型と可換する
\(\mathrm{Seg}_d\) が関手であるだけだと、Set とか Query といったセグメント木上で行う操作と整合的になっているか不安になって確かめたくなりますよね。
配列側で \(\mathrm{set}_i\) と \(\mu_{[l:r]}\) が \(f\) と可換することは直接確かめられます。
$$ \begin{CD} M\ \times\ M^n @>{f \times f^n}>> N\ \times\ N^n \\ @V{\mathrm{set}_i}VV @VV{\mathrm{set}_i}V \\ M^n @>{f^n}>> N^n \end{CD} $$\(\mathrm{set}_i\) は成分の入れ替えだけなので上は可換ですし、\(f\) がモノイド準同型であることから
$$ \begin{CD} M^n @>{f^n}>> N^n \\ @V{\mu_{[l:r]}}VV @VV{\mu_{[l:r]}}V \\ M @>{f}>> N \end{CD} $$も可換です。
これを \(\pi\) の自然性と合わせると、木側でも
$$ \begin{CD} M\ \times\ \mathrm{Seg}_d(M) @>{f \times \mathrm{Seg}_d(f)}>> N\ \times\ \mathrm{Seg}_d(N) \\ @V{\mathrm{Set}_i}VV @VV{\mathrm{Set}_i}V \\ \mathrm{Seg}_d(M) @>{\mathrm{Seg}_d(f)}>> \mathrm{Seg}_d(N) \end{CD} $$$$ \begin{CD} \mathrm{Seg}_d(M) @>{\mathrm{Seg}_d(f)}>> \mathrm{Seg}_d(N) \\ @V{\mathrm{Query}{[l:r]}}VV @VV{\mathrm{Query}{[l:r]}}V \\ M @>{f}>> N \end{CD} $$が成り立ちます。
競技プログラミング的に言えば、これはセグメント木を使う時であっても「\(\mathbb{Z}\) 上で計算してから最後に \(\bmod\ m\) を取っても、最初から \(\mathbb{Z}/m\) 上で計算しても答えは同じ」という、普段何気なく使っている事実です。準同型 \(\mathbb{Z}\to\mathbb{Z}/m\) が積と \(1\) を保つからそうなっている、というのがここでの説明になります。
今までセグメント木を使う時はこのあたりは深く考えてなかったです。
余談: \(\mathrm{Seg}_d(M)\) 自身はモノイドか
\(M^{T_d}\) には成分ごとの積でモノイド構造が入ります。これは \(\mathrm{Seg}_d(M)\) に制限できるでしょうか。\(v, w \in \mathrm{Seg}_d(M)\) に対して条件を書くと
$$ (vw)_\tau = v_\tau w_\tau = v_{\tau_1}v_{\tau_2}w_{\tau_1}w_{\tau_2},\\ (vw)_{\tau_1}(vw)_{\tau_2} = v_{\tau_1}w_{\tau_1}v_{\tau_2}w_{\tau_2} $$となり、両者が一致するには \(v_{\tau_2}w_{\tau_1} = w_{\tau_1}v_{\tau_2}\) が必要です。実際、\(M = \langle x, y\rangle\)(2文字の自由モノイド)、\(d = 1\) として葉の値が \((e, x)\) の状態と \((y, e)\) の状態を取ると、成分ごとの積の根の値は \(xy\) ですが、葉の成分ごとの積 \((y, x)\) から決まる根の値は \(yx\) であって、一致しません。
つまり \(M\) が可換なときに限り、\(\pi_d\) は集合の同型ではなくモノイドの同型に持ち上がります。ここまで可換性は一度も要らなかったので、非可換性が本当に効く数少ない場所として面白いところです。
おわりに
- セグメント木は追加の構造を課さないモノイドに対してあたかも配列のように振る舞い、しかも無駄がないはずだ、という素朴な直感が定式化できた
- \(\pi_d\) が同型だということは、集合の圏の中では木と配列が区別できない
- 不変条件、
Set,Queryはこの同型を通してモノイドの操作から定まる自然なもの - 計算量の議論だけ（前回の補題4 と補題6）は、モノイドの性質を一切使わず、木の幾何(各高さの境界ノードが高々 2 個であること)だけから出ていて、\(\pi_d\) を通した同型からは出てこない
次回は、セグメント木に載せる構造の一般化について考えてみたいと思います。