| 1 | #include "segment_tree_node.cpp" |
| 2 | struct segment_tree { |
| 3 | int n; |
| 4 | vector<node> arr; |
| 5 | segment_tree() { } |
| 6 | segment_tree(const vector<ll> &a) : n(size(a)), arr(4*n) { |
| 7 | mk(a,0,0,n-1); } |
| 8 | node mk(const vector<ll> &a, int i, int l, int r) { |
| 9 | int m = (l+r)/2; |
| 10 | return arr[i] = l > r ? node(l,r) : |
| 11 | l == r ? node(l,r,a[l]) : |
| 12 | node(mk(a,2*i+1,l,m),mk(a,2*i+2,m+1,r)); } |
| 13 | node update(int at, ll v, int i=0) { |
| 14 | propagate(i); |
| 15 | int hl = arr[i].l, hr = arr[i].r; |
| 16 | if (at < hl || hr < at) return arr[i]; |
| 17 | if (hl == at && at == hr) { |
| 18 | arr[i].update(v); return arr[i]; } |
| 19 | return arr[i] = |
| 20 | node(update(at,v,2*i+1),update(at,v,2*i+2)); } |
| 21 | node query(int l, int r, int i=0) { |
| 22 | propagate(i); |
| 23 | int hl = arr[i].l, hr = arr[i].r; |
| 24 | if (r < hl || hr < l) return node(hl,hr); |
| 25 | if (l <= hl && hr <= r) return arr[i]; |
| 26 | return node(query(l,r,2*i+1),query(l,r,2*i+2)); } |
| 27 | node range_update(int l, int r, ll v, int i=0) { |
| 28 | propagate(i); |
| 29 | int hl = arr[i].l, hr = arr[i].r; |
| 30 | if (r < hl || hr < l) return arr[i]; |
| 31 | if (l <= hl && hr <= r) |
| 32 | return arr[i].range_update(v), propagate(i), arr[i]; |
| 33 | return arr[i] = node(range_update(l,r,v,2*i+1), |
| 34 | range_update(l,r,v,2*i+2)); } |
| 35 | void propagate(int i) { |
| 36 | if (arr[i].l < arr[i].r) |
| 37 | arr[i].push(arr[2*i+1]), arr[i].push(arr[2*i+2]); |
| 38 | arr[i].apply(); } }; |
| 39 | // vim: cc=60 ts=2 sts=2 sw=2: |