セグメント木の理屈を学ぶ(1) データ構造とモノイド構造の整合性

競技プログラミングの文脈で出てくるセグメント木について「どう使うか」ではなく、「なぜ使えるのか」を考察します。

セグメント木の解説記事の多くは、配列を2べきの長さに区切って完全二分木に載せる様子や、任意の区間が高々 \(O(\log n)\) 個のノードに分解できる様子を図で示すことに重点が置かれています。

図を見れば「なるほど、正しそうだ」という感覚は得られるのですが、その感覚がどこまで厳密な正しさの根拠になっているのか理解できていませんでした。

この記事では、そうしたギャップを埋めることを目標に、セグメント木というデータ構造を天下り的に構成したあとで、それが期待通りに動作すること、そして期待通りの計算量で動作することを、モノイドの結合則だけを用いて証明します。

おことわり

この記事は、セグメント木に一定の親しみがある私が、セグメント木の持つ優れた性質について証明を通して理解するために整理した内容です。

そのため、セグメント木を1から学習しようとしている方、セグメント木の実装を知りたい方、具体例を通じてセグメント木の使い方を知り、競技プログラミングで出題される問題を解きたい方向けの内容ではないことをご了承ください。

また、内容については確認したつもりではありますが、間違いを発見した方は教えて頂けると助かります。

前提

• セグメント木に関する基本的な知識を仮定します。
• モノイドなどの数学の概念を断りなく利用します。
• モノイドは可換性を仮定しません。
• コードを全て疑似コードで記述します。
• 配列・区間のインデックスは 0-indexed とします。
• \([l:r]\) で離散化された区間 \([l, r] \cap \mathbb{Z}\) を表すことにします。

アプローチ

最初に木の構造そのものを定義し、次に具体的なデータ構造(セグメント木)を定義し、そのあとに構成したデータ構造がセグメント木として成り立って欲しい性質を満たすことを証明します。

木の構造

セグメント木の議論を始める前に、土台となる木の構造だけを先に定義しておきます。ここで導入する概念(区間 \(\mathrm{seg}\)、高さ \(h\)、子ノードの記法、パス)はモノイドの値 \(v_\tau\) とは無関係で、純粋に組合せ論的な性質です。

定義

• 管理する配列の長さを \(n = 2^d\) とします。一般の \(n\) は単位元でパディングしてこの形に帰着させます。
• 深さ \(d\) の完全二分木 \(T\) を考え、各ノード \(\tau \in T\) に区間 \(\mathrm{seg}(\tau) \subseteq [0:n-1]\) を対応させます。
• 根 \(\tau_0\) は \(\mathrm{seg}(\tau_0) = [0:n-1]\) とします。葉は単一のインデックス \(\mathrm{seg}(\tau) = {i}\)(\(0 \le i \le n-1\)) で表せるものです。
• 非葉ノード \(\tau\) は必ず2つの子を持ちます。モノイドの非可換性のために子ノードの順序を明示する必要が頻繁に生じるので、左の子を \(\mathrm{lch}(\tau)\)、右の子を \(\mathrm{rch}(\tau)\) と書くことにします。子は親の区間を前半・後半に分割するもの、すなわち \[ \mathrm{seg}(\tau) = \mathrm{seg}(\mathrm{lch}(\tau)) \sqcup \mathrm{seg}(\mathrm{rch}(\tau)) \] (インデックス順を保った非交和、すなわち \(\mathrm{seg}(\mathrm{lch}(\tau))\) の全要素は \(\mathrm{seg}(\mathrm{rch}(\tau))\) の全要素より小さい)として定義します。
• 高さ \(h(\tau)\) を、葉について \(h(\tau) = 0\)、非葉ノード \(\tau\) について \(h(\tau) = h(\mathrm{lch}(\tau)) + 1 = h(\mathrm{rch}(\tau)) + 1\)（完全二分木なので両辺は一致し、これも定義の一部とします）として定義します。根の高さは \(d\) であり、\(|\mathrm{seg}(\tau)| = 2^{h(\tau)}\) が成り立ちます。特に、非葉ノード \(\tau\) について \[ h(\mathrm{lch}(\tau)) = h(\mathrm{rch}(\tau)) = h(\tau) - 1 \] が成り立ちます。

以降、「非葉ノード \(\tau\) の子を \(\mathrm{lch}(\tau), \mathrm{rch}(\tau)\) とする」という前提のもとで、上の2つの関係式を断りなく使います。

ノードから根へのパス

各インデックス \(i \in [0:n-1]\) に対して、\(i \in \mathrm{seg}(\tau)\) となるノード \(\tau\) 全体を \(P_i\) と書き、これを(葉 \({i}\) から根 \(\tau_0\) への)パスと呼びます。

補題1 (パスの一意性). 任意の \(i \in [0:n-1]\) と高さ \(h \in {0,1,\ldots,d}\) に対して、\(P_i\) に属する高さ \(h\) のノードはちょうど1つ存在する。

証明. \(h\) に関する下降帰納法(\(d\) から \(0\) へ)で示す。\(h=d\) のときは根 \(\tau_0\) のみが高さ \(d\) であり、\(\mathrm{seg}(\tau_0)=[0:n-1]\) より任意の \(i\) について \(\tau_0 \in P_i\)。これが唯一の高さ \(d\) のノードなので成立。

高さ \(h+1\) のノード \(\tau\) について \(\tau \in P_i\) であるものがちょうど1つ存在すると仮定する。\(\mathrm{seg}(\tau) = \mathrm{seg}(\mathrm{lch}(\tau)) \sqcup \mathrm{seg}(\mathrm{rch}(\tau))\) は非交和なので、\(i \in \mathrm{seg}(\tau)\) ならば \(i \in \mathrm{seg}(\mathrm{lch}(\tau))\) と \(i \in \mathrm{seg}(\mathrm{rch}(\tau))\) のちょうど一方のみが成り立つ。すなわち \(\tau\) の子のうち \(P_i\) に属するものがちょうど1つ存在する。これが高さ \(h\) の唯一のノードであり(他の高さ \(h+1\) のノードの子は \(\mathrm{seg}\) が \(i\) を含まないので \(P_i\) に属さない)、主張が示された。■

以降、この一意性のもとで、\(P_i\) の高さ \(h\) のノードを単に「\(P_i\) の高さ \(h\) のノード」と呼びます。

セグメント木の構成

木の構造の上に、値としてモノイドを扱う、一点更新・区間取得ができるセグメント木を構成します。

設定

• \(M = (M, \cdot, e)\) をモノイドとします。
• 管理するモノイドの配列を \(a = (a_0, \ldots, a_{n-1}) \in M^n\) とします。
• 各ノード \(\tau\) に、モノイドの元 \(v_\tau \in M\) を保持します。
• 不変条件: 常に \[ v_\tau = \prod_{i \in \mathrm{seg}(\tau)} a_i \] が成り立つようにします。\(\prod\) はモノイドの演算 \(\cdot \) に関する積をインデックス順に取ったもので、結合則から括弧の付け方に依存しません。

セグメント木の初期化

すべての \(i\) について \(a_i \leftarrow e\) とし、木の全ノードで \(v_\tau \leftarrow e\) と初期化します。単位元の積は単位元なので不変条件を満たします。

Set(i, c): 一点更新

配列の単一要素の更新 \(a_i \leftarrow c\) に対応する操作 Set(i, c) を定義します。

まず、 \(a_i \leftarrow c\) を行うためにノード \(\tau \) の値を更新する操作 Set(i, c, τ) を下のように定義します。

Set(i, c, τ):
  if seg(τ) = {i}:
    v_τ ← c            # 葉なので直接書き換え
    return
  if i ∈ seg(lch(τ)):
    Set(i, c, lch(τ))
  else:
    Set(i, c, rch(τ))
  v_τ ← v_lch(τ) · v_rch(τ)     # 子の更新後に再計算

そして、Set(i, c) を ルートに対する更新 Set(i, c, τ0) として定義します。

Query(l, r): 区間 [l:r] の総積

区間に配置されたモノイドの元の積に対応する操作を同様に定義します。

Query(l, r, τ):
  if seg(τ) ∩ [l:r] = ∅:
    return e             # 単位元(何も無ければ影響しない)
  if seg(τ) ⊆ [l:r]:
    return v_τ           # 部分木を丸ごと使える
  return Query(l, r, lch(τ)) · Query(l, r, rch(τ))

こちらも、Query(l, r) を Query(l, r, τ0) として定義します。

成り立って欲しい性質

お待たせしました。天下り的に与えた Set, Query が期待する性質を持つことを確認しましょう。

補題2 (Set操作の不変条件保存)

任意の木のノード \(\tau\) について、（初期状態を含む）任意の Set 呼び出し列の後で

\[ v_\tau = \prod_{i \in \mathrm{seg}(\tau)} a_i \]

が成立する。

証明. 呼び出し列の長さに関する帰納法で示す。初期状態ではすべての \(a_i = e\) かつすべての \(v_\tau = e\) なので、空でない \(\mathrm{seg}(\tau)\) についても \(\prod_{i} e = e\) より成立する。

呼び出し列の前まで不変条件が成立していると仮定し、次の呼び出し \(\mathrm{Set}(i,c)\) の後でも成立することを示す。以下、ノード \(\tau\) の高さ \(h(\tau)\) に関する帰納法で、「呼び出し \(\mathrm{Set}(i,c,\tau_0)\) の後、\(v_\tau = \prod_{j \in \mathrm{seg}(\tau)} a_j\)(新しい配列に対して)が成り立つ」ことを、すべてのノード \(\tau\) について示す。

• \(h(\tau) = 0\)（\(\tau\) は葉、\(\mathrm{seg}(\tau) = {k}\) とする）:

  • \(k = i\) の場合、アルゴリズムは \(v_\tau \leftarrow c\) と直接書き換える。新しい配列では \(a_i = c\) なので \(\prod_{j \in {i}} a_j = c = v_\tau\) より成立する。
  • \(k \neq i\) の場合、\(i \notin \mathrm{seg}(\tau)\) なのでアルゴリズムはこのノードを訪問せず \(v_\tau\) を書き換えない。また \(a_k\)(\(k\neq i\))も変化しないので \(\prod_{j\in{k}} a_j\) の値も変わらない。呼び出し前に不変条件が成り立っていた（帰納法の仮定）ので、呼び出し後も \(v_\tau = \prod_{j\in\mathrm{seg}(\tau)} a_j\) が成立する。

• \(h(\tau) > 0\)（子を \(\mathrm{lch}(\tau), \mathrm{rch}(\tau)\) とする）: 高さに関する帰納法の仮定より、子については主張がすでに成立している、すなわち \[ v_{\mathrm{lch}(\tau)} = \prod_{j \in \mathrm{seg}(\mathrm{lch}(\tau))} a_j, \qquad v_{\mathrm{rch}(\tau)} = \prod_{j \in \mathrm{seg}(\mathrm{rch}(\tau))} a_j \] が(新しい配列に対して)成り立つ。

  • \(i \in \mathrm{seg}(\tau)\) の場合、アルゴリズムはこのノードを訪問し、\(v_\tau \leftarrow v_{\mathrm{lch}(\tau)}\cdot v_{\mathrm{rch}(\tau)}\) と計算する。\(\mathrm{seg}(\tau) = \mathrm{seg}(\mathrm{lch}(\tau)) \sqcup \mathrm{seg}(\mathrm{rch}(\tau))\)(インデックス順を保った非交和)なので、モノイドの結合則により \[ v_\tau = \Bigl(\prod_{j \in \mathrm{seg}(\mathrm{lch}(\tau))} a_j\Bigr)\cdot\Bigl(\prod_{j \in \mathrm{seg}(\mathrm{rch}(\tau))} a_j\Bigr) = \prod_{j \in \mathrm{seg}(\tau)} a_j. \] 成立。
  • \(i \notin \mathrm{seg}(\tau)\) の場合、アルゴリズムはこのノードを訪問せず \(v_\tau\) を書き換えない。\(i \notin \mathrm{seg}(\tau)\) なので \(a_i\) の変化は \(\prod_{j\in\mathrm{seg}(\tau)} a_j\) に影響しない。呼び出し前の不変条件（帰納法の仮定）より、呼び出し後も \(v_\tau = \prod_{j\in\mathrm{seg}(\tau)} a_j\) が成立する。

以上、高さに関する帰納法によりすべてのノード \(\tau\) で主張が示され、特に呼び出し列に関する外側の帰納法の帰納段も示された。■

ここで使っているのは結合則(と単位元の存在、空積のため)のみで、可換性は不要です。

補題3 (Query操作の正当性)

補題2の不変条件が成り立っている状態で、任意のノード \(\tau\) について \[ \mathrm{Query}(l,r,\tau) = \prod_{i \in \mathrm{seg}(\tau) \cap [l:r]} a_i. \]

証明. ノード \(\tau\) の高さ \(h(\tau)\) に関する帰納法で示す。

• \(h(\tau) = 0\)（\(\tau\) は葉、\(\mathrm{seg}(\tau) = {k}\) とする）:

  • \(k \notin [l:r]\) の場合、\(\mathrm{seg}(\tau)\cap[l:r] = \emptyset\) なのでアルゴリズムは \(e\) を返す。空積の約束により \(\prod_{i\in\emptyset} a_i = e\) より成立。
  • \(k \in [l:r]\) の場合、\(\mathrm{seg}(\tau) = {k} \subseteq [l:r]\) なのでアルゴリズムは \(v_\tau\) を返す。補題2より \(v_\tau = \prod_{i\in{k}} a_i\)、かつ \(\mathrm{seg}(\tau)\cap[l:r] = {k}\) より成立。

  （葉では \(\mathrm{seg}(\tau)\cap[l:r]\) は \(\emptyset\) か \(\mathrm{seg}(\tau)\) 自身のいずれかであり、この2ケースで尽くされる。）

• \(h(\tau) > 0\)（子を \(\mathrm{lch}(\tau), \mathrm{rch}(\tau)\) とする）: 高さに関する帰納法の仮定より、子については主張がすでに成立している、すなわち \[ \mathrm{Query}(l,r,\mathrm{lch}(\tau)) = \prod_{i \in \mathrm{seg}(\mathrm{lch}(\tau))\cap[l:r]} a_i, \qquad \mathrm{Query}(l,r,\mathrm{rch}(\tau)) = \prod_{i \in \mathrm{seg}(\mathrm{rch}(\tau))\cap[l:r]} a_i \] が成り立つ。

  • \(\mathrm{seg}(\tau) \cap [l:r] = \emptyset\) の場合、アルゴリズムは \(e\) を返す。空積の約束により \(\prod_{i\in\emptyset} a_i = e\) より成立。
  • \(\mathrm{seg}(\tau) \subseteq [l:r]\) の場合、アルゴリズムは \(v_\tau\) を返す。補題2より \(v_\tau = \prod_{i\in\mathrm{seg}(\tau)} a_i\)、かつ \(\mathrm{seg}(\tau)\subseteq[l:r]\) より \(\mathrm{seg}(\tau)\cap[l:r] = \mathrm{seg}(\tau)\) より成立。
  • それ以外(\(\mathrm{seg}(\tau)\cap[l:r]\) が \(\mathrm{seg}(\tau)\) の空でない真部分集合)の場合、子を再帰的に呼び出し \(\mathrm{Query}(l,r,\mathrm{lch}(\tau))\cdot\mathrm{Query}(l,r,\mathrm{rch}(\tau))\) を返す。\(\mathrm{seg}(\tau)\cap[l:r] = (\mathrm{seg}(\mathrm{lch}(\tau))\cap[l:r]) \sqcup (\mathrm{seg}(\mathrm{rch}(\tau))\cap[l:r])\)(順序を保った非交和)なので、帰納法の仮定とモノイドの結合則により \[ \mathrm{Query}(l,r,\mathrm{lch}(\tau))\cdot\mathrm{Query}(l,r,\mathrm{rch}(\tau)) = \Bigl(\prod_{i \in \mathrm{seg}(\mathrm{lch}(\tau))\cap[l:r]} a_i\Bigr)\cdot\Bigl(\prod_{i \in \mathrm{seg}(\mathrm{rch}(\tau))\cap[l:r]} a_i\Bigr) = \prod_{i \in \mathrm{seg}(\tau)\cap[l:r]} a_i. \] より成立。

以上、高さに関する帰納法によりすべてのノード \(\tau\) で主張が示された。■

系. \(\mathrm{seg}(\tau_0) = [0:n-1] \supseteq [l:r]\) なので、\(\mathrm{Query}(l,r) = \mathrm{Query}(l,r,\tau_0) = \prod_{i \in [l:r]} a_i\)。これが求めたかった性質です。

計算量

次に、計算量です。

Set, Query はいずれも根から高々 \(d = \log_2 n\) 段の再帰で計算できます。ただし Query については、単純に「各ノードで定数回」という理由だけでは \(O(\log n)\) は言えません。訪問されるノードの総数自体を、木の幾何を使って各階層ごとに定数個に抑える必要があります。

補題4 (Setの計算量)

ノード \(\tau\) に対する呼び出し Set(i, c, τ) の実行にかかるモノイド演算(積 \(\cdot\) の呼び出し)の回数を \(T_{\mathrm{Set}}(\tau)\) とすると、\(T_{\mathrm{Set}}(\tau) \le h(\tau)\)。

証明. \(h(\tau)\) に関する帰納法。

• \(h(\tau) = 0\)(葉): \(v_\tau \leftarrow c\) の代入のみでモノイド演算は行われないので \(T_{\mathrm{Set}}(\tau) = 0 = h(\tau)\)。
• \(h(\tau) > 0\)(子 \(\mathrm{lch}(\tau), \mathrm{rch}(\tau)\) のうちいずれか一方だけを再帰的に呼ぶ): 呼ばれた子を \(\tau_k\) とすると、Set はまず Set(i, c, τ\_k) を呼び、その後 \(v_\tau \leftarrow v_{\mathrm{lch}(\tau)}\cdot v_{\mathrm{rch}(\tau)}\) で積を1回計算する。呼ばれなかった子は再帰されない。よって \[ T_{\mathrm{Set}}(\tau) = T_{\mathrm{Set}}(\tau_k) + 1 \le h(\tau_k) + 1 = h(\tau) \] (最後の不等号は帰納法の仮定、最後の等号は \(h(\tau_k) = h(\tau)-1\) による)。■

根 \(\tau_0\) の高さは \(d = \log_2 n\) なので、Set(i, c) のモノイド演算の回数は \(O(\log n)\) です。木を辿る際の分岐判定などの付随する処理も各段で定数回なので、全体でも \(O(\log n)\) となります。

与えられた配列からのセグメント木の構築は Set を \(n\) 回呼び出すため \(O(n\log n)\) になります。

---

Query の計算量の証明をするために、補題を証明します。

補題5(境界ノードの局在)

ノード \(\tau\) が「境界ノード」、すなわち \(\mathrm{seg}(\tau)\cap[l:r] \neq \emptyset\) かつ \(\mathrm{seg}(\tau) \not\subseteq [l:r]\) であるとする。このとき \(l \in \mathrm{seg}(\tau)\) または \(r \in \mathrm{seg}(\tau)\) が成り立つ。

証明. \(\mathrm{seg}(\tau) = [x:y]\) と書く。\(\mathrm{seg}(\tau)\cap[l:r] \neq \emptyset\) より \(\max(x,l) \le \min(y,r)\)。\(\mathrm{seg}(\tau)\not\subseteq[l:r]\) より \(x<l\) または \(y>r\) の少なくとも一方が成り立つ。

• \(x<l\) の場合: このとき \(\max(x,l)=l\) なので \(l \le \min(y,r) \le y\)、かつ \(x<l\) より \(l\ge x\)。よって \(l\in[x:y]=\mathrm{seg}(\tau)\)。
• \(y>r\) の場合: 同様に \(\min(y,r)=r\) なので \(\max(x,l)\le r\)、かつ \(x\le\max(x,l)\le r<y\)、\(l\le\max(x,l)\le r\) より \(r\in[x:y]=\mathrm{seg}(\tau)\)。■

系 (境界ノード数の評価). 境界ノードは補題4より \(l\in\mathrm{seg}(\tau)\) または \(r\in\mathrm{seg}(\tau)\) を満たす、すなわちパス \(P_l\) または \(P_r\) 上のノードに限られます。補題1(パスの一意性)より \(P_l, P_r\) はいずれも各高さ \(h \in {0,1,\ldots,d}\) にちょうど1つのノードを持つので、

\[ \begin{align*} & \#({\text{高さ } h \text{ の境界ノード}}) \\ &\le \#(P_l \text{ の高さ } h \text{ のノード}) + \#(P_r \text{ の高さ } h \text{ のノード}) \\ &\le 2 \end{align*} \]

が任意の \(h\) について成り立ちます。

補題6(Queryの計算量)

Query(l, r) の実行全体にかかるモノイド演算(積 \(\cdot\) の呼び出し)の回数は、高々 \(2(d+1) = O(\log n)\) である。

証明. Query(l, r, τ) の呼び出し全体で積が計算されるのは境界ノードにおいてであり、境界ノード1つにつき積はちょうど1回計算されます。境界ノードの高さは \(0\) から \(d\) までの \(d+1\) 通りで、補題5の系より各高さの境界ノード数は高々2個です。よって積の計算回数の総和は高々 \(2(d+1)\) です。■

\(d = \log_2 n\) なので、Query(l, r) にかかるモノイド演算の回数は \(O(\log n)\) です。境界ノードでない訪問ノード(第1・第2分岐で即座に返るノード)も、境界ノードの子としてしか生成されないため、その総数も \(O(\log n)\) に抑えられ、条件判定などの付随する処理も含めて全体で \(O(\log n)\) となります。

おわりに

いかがだったでしょうか。当たり前のように書いている性質をただ証明しただけではありますが、この記事がセグメント木によって目的の計算ができる仕組みを理解するのに役立てば幸いです。

次回は、今回天下り的に与えた構成がなぜ「自然なもの」であるかについて考えてみたいと思います。お楽しみに。

参考文献

入門寄り

• “セグメント木を徹底解説！0から遅延評価やモノイドまで”¹: セグメント木についての日本語の概要です。
• “Segment Tree”²: セグメント木の英語の概要です。具体的な利用方法について詳しく書かれています。

セグメント木の可視化

• “Segment Tree のお勉強(1)”³, “Segment Tree のお勉強(2)”⁴: 2べきでない場合、モノイドが可換でない場合も含め、セグメント木と遅延セグメント木で演算をしたときの様子が可視化されています。

データ構造と代数的構造の整合性

• “Testing Calibration in Nearly-Linear Time”⁵: この論文では双対セグメント木に対してデータ構造を具体的に構成した後、代数的構造との整合性を証明しています。この記事の議論の構成はこちらの記事から大きく影響を受けています。