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セグメント木も可能(但し定数倍がかなり重い)。 以下の実装では長方形内の点の個数を求めるクエリと, 点の追加削除のクエリをサポートしている。

問題例

参考資料