ei1333's page

ホーム > Wiki

セグメント木(Segment-Tree)

説明

完全2分木である。区間に対する様々な演算が$O(\log N)$で実現できるが, ここでは一般的な操作であるRMQを実装している。

実装では木を配列で実現している。ノード $k$ について, 親ノードは $\frac {k - 1} {2}$, 子ノードは $2k+1, 2k+2$ である。

使い方

計算量

実装例

応用 1: 区間加算

Starry-Sky-Tree と呼ばれる有名なセグメント木がある。このセグメント木では以下の $2$ つのクエリをサポートする。

ここではその区間に一様に加算される値を持つ add 配列と, 区間の最小値を持つ small 配列を持つことによって実現している。

応用 2: 遅延評価

遅延評価というテクがある。遅延評価を使うと, 区間に対する演算操作の幅が大きく広がる。

応用 3: 2Dセグメント木

セグメント木のノードに平衡二分探索木をのせた 2Dセグメント木も可能(但し定数倍がかなり重い)。 以下の実装では長方形内の点の個数を求めるクエリと, 点の追加削除のクエリをサポートしている。静的な場合であれば応用4のフラクショナルカスケーディングを用いてlogを1個落とすことができる。

(クエリを先読みするなどして)構造が静的な場合であれば, 座標圧縮してセグ木にBITをのせたりできる。補助のために関数 prequery() と preadd() を用意している(prequery()は場合によっては使わなくても良い)。実際にセグ木を構築する際に, これからくるクエリの引数を予め把握しておくことで, 縦方向の座標圧縮が可能となる。build() の呼び出しを忘れないように注意すること。

応用 4: フラクショナルカスケーディング

静的な場合に, 次元を1個落とすテク。コードを見たほうが早い気がする。セグ木を下る時に縦方向の範囲をいい感じに計算しておくことで毎回の二分探索が不要となっている。(たぶんAOJのDSLでverified(MLEやが))

モノイド

単位元を持つ半群(二項演算の結合律を満たす)はモノイドである。モノイドであればセグメント木にのせることができる。以下はRMQの場合である。(こっちのほうが色々定義しやすいし, 汎用性が高い気がする)

問題例

参考資料