セグメント木(Segment-Tree)
説明
完全2分木である。モノイド に対する区間への様々な演算が$O(\log N)$ で実現できる。
モノイド は次の条件を満たす代数的構造である。
- 結合率を満たす。つまり $S$ の各元 $a, b, c$ に対して, $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ が満たされる。
- 単位元をもつ。つまり $S$ の任意の元 $a$ をとってきたときに $a \cdot e = e \cdot a = a$ なる $e$ が存在する。
実装では木を 1-indexed の配列で実現している。ノード $k$ について, 親ノードは $\frac {k} {2}$, 子ノードは $2k+0, 2k+1$ である。
使い方
- $\mathrm{SegmentTree}(n, f, M1)$: サイズ $n$ のセグ木の初期化。$f$ は $2$ つの要素をマージする二項演算, $M1$ は単位元である。
- $\mathrm{set}(k, x)$: $k$ 番目の要素に $x$ をセットする
- $\mathrm{build}()$: 構築する
- $\mathrm{query}(l, r)$: 区間 $[l, r)$ に対して二項演算をした結果を返す
- $\mathrm{update}(k, x)$: $k$ 番目の要素を $x$ に変更する
計算量
- build: $O(N)$
- query, update: $O(\log N)$
実装例
例えば区間 min をしたいときは次のようにする。
SegmentTree< int > seg(N, [](int a, int b){ return min(a, b); }, INT_MAX);また区間 sum とりたいときは次のようにする。
SegmentTree< int > seg(N, [](int a, int b){ return a + b; }, 0);応用 1: 遅延評価
遅延評価というテクがある。遅延評価を使うと, 区間に対する演算操作の幅が大きく広がる。
この場合はコンストラクタに対し追加で作用素の情報も与える。$g$ は要素と作用素のマージ, $h$ は作用素と作用素のマージ, $p$ は作用素を下に降ろすときに行う演算(第一引数は作用素のもとの値, 第二引数は降ろした後の区間の長さ), $OM0$ は作用素の単位元である。
例えば区間 add 区間 min をとりたいときは次のようにする。
auto f = [](int a, int b) { return min(a, b); };
auto g = [](int a, int b) { return a + b; };
auto h = [](int a, int b) { return a + b; };
auto p = [](int a, int b) { return a; };
LazySegmentTree< int > seg(N, f, g, h, p, INT_MAX, 0);また区間 add 区間 sum をとりたいときは次のようにする。
auto f = [](int a, int b) { return a + b; };
auto p = [](int a, int b) { return a * b; };
LazySegmentTree< int > seg(N, f, f, f, p, 0, 0);応用 2: 2Dセグメント木
セグメント木のノードに平衡二分探索木をのせた 2Dセグメント木も可能(但し定数倍がかなり重い)。 以下の実装では長方形内の点の個数を求めるクエリと, 点の追加削除のクエリをサポートしている。静的な場合であれば応用4のフラクショナルカスケーディングを用いてlogを1個落とすことができる。
(クエリを先読みするなどして)構造が静的な場合であれば, 座標圧縮してセグ木にBITをのせたりできる。補助のために関数 prequery() と preadd() を用意している(prequery()は場合によっては使わなくても良い)。実際にセグ木を構築する際に, これからくるクエリの引数を予め把握しておくことで, 縦方向の座標圧縮が可能となる。build() の呼び出しを忘れないように注意すること。
応用 3: フラクショナルカスケーディング
静的な場合に, 次元を1個落とすテク。コードを見たほうが早い気がする。セグ木を下る時に縦方向の範囲をいい感じに計算しておくことで毎回の二分探索が不要となっている。(たぶんAOJのDSLでverified(MLEやが))
応用 4: 二分探索
セグメント木 + 二分探索は愚直に実装すると $O(\log^2 N)$ かかるが, ほとんどの場合セグメント木上を二分探索することで $O(\log N)$ に落とすことができる。
応用 5: 永続セグメント木
やるだけ。メモリ使用量に注意。定数倍に注意。
参考: ARC033_C - データ構造 #2138279
問題例
- 検証済AOJ DSL_2_A Range Minimum Query (RMQ)
- 検証済(応用3)CF #404 E. Anton and Permutation(Submittion: #25528699)