セグメント木 / SegmentTree
Last updated：2018-04-16 03:25:49
Tweet
Category:データ構造,
Tag：
セグメント木
概要
$N$ 個の数の列について，次のクエリを処理する:
- $\mathrm{update}(i, x)$ : $i$番目の値を$x$で置き換える
- $\mathrm{add}(i, x)$ : $i$番目の値に$x$を加える (optional)
- $\mathrm{query}(l, r)$ : 区間$[l, r)$の最小値/最大値/合計を取得する
計算量
- $\mathrm{update}$: $O(\log N)$
- $\mathrm{add}$: $O(\log N)$
- $\mathrm{query}$: $O(\log N)$
使い方
コンストラクタには，長さ，演算の単位元，演算のラムダ式を指定します．
// 長さnの区間minを取るセグ木を初期化
SegmentTree<int> st(n, (1LL<<31)-1, [](T& l, T& r) {return (l < r) ? l : r; });
ただ記述量が多いため，最小値,最大値,合計のエイリアスを用意しています．
SegmentTree<int> st(n, MIN); // 区間最小値
SegmentTree<int> st(n, MAX); // 区間最大値
SegmentTree<int> st(n, SUM); // 区間合計
// i番目の要素を配列a[i]の値とする
for(int i = 0; i < n; ++i) st.update(i, a[i]);
// 2番目の要素をに10を加える
st.add(2, 10);
// 区間[l, r)の最小値を取得する
int l = 1, r = 5;
int mi = st.query(l, r);
実装例