Segment Tree (Bottom Up)
결합법칙이 성립하는 operator * 가 있을 때, 한 원소의 값을 업데이트 하거나 a[l] * a[l+1] * … * a[r-1] * a[r] 을 빠르게 구할 때 쓰는 자료구조이다.
- 공간 복잡도 : O(n)
- 시간 복잡도
- 한 점 업데이트 : O(logn)
- 구간값 쿼리 : O(logn)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| template <typename T> | |
| struct Segtree { | |
| int bs; | |
| vector<T> tree; | |
| const T initVal; | |
| function<T (T, T)> op; | |
| // constructor | |
| // n : number of elems, init : initial value | |
| // op : associative operator | |
| // O(n) | |
| Segtree(int n, T init, function<T (T, T)> _op) | |
| : initVal(init), op(_op) { | |
| for (bs = 1; bs < n; bs <<= 1); | |
| tree.resize(bs * 2, initVal); | |
| } | |
| // fill initial value in all nodes | |
| // O(n) | |
| void clear() { | |
| fill(tree.begin(), tree.end(), initVal); | |
| } | |
| // make tree with prepared leaf values | |
| // O(n) | |
| void build() { | |
| for (int x = bs - 1; x > 0; --x) | |
| tree[x] = op(tree[x << 1], tree[x << 1 | 1]); | |
| } | |
| // get value of [s, e] | |
| // 0 <= s, e < bs | |
| // O(log(n)) | |
| T query(int s, int e) { | |
| T ret0 = initVal, ret1 = initVal; | |
| for (s |= bs, e |= bs; s <= e; s = (s + 1) >> 1, e = (e - 1) >> 1) { | |
| if (s & 1) ret0 = op(ret0, tree[s]); | |
| if (!(e & 1)) ret1 = op(tree[e], ret1); | |
| } | |
| return op(ret0, ret1); | |
| } | |
| // update value of x | |
| // 0 <= x < bs | |
| // O(log(n)) | |
| void update(int x, T val) { | |
| for (tree[x |= bs] = val; x >>= 1; ) | |
| tree[x] = op(tree[x << 1], tree[x << 1 | 1]); | |
| } | |
| // apply val to x | |
| // 0 <= x < bs | |
| // O(log(n)) | |
| void apply(int x, T val) { | |
| x |= bs; | |
| for (tree[x] = op(tree[x], val); x >>= 1; ) | |
| tree[x] = op(tree[x << 1], tree[x << 1 | 1]); | |
| } | |
| }; |
구간 업데이트 & 한 점 쿼리
구현을 약간 응용하면 구간 업데이트 및 한 점 쿼리를 하는 경우에도 사용할 수 있다.