# Iterative-SegmentTree [by OmeletWithouEgg](https://omeletwithoutegg.github.io/2019/12/07/Iterative-SegmentTree/) ###### tags: `Algorithm` --- ## 例題 RMQ 給出序列, 支援幾個操作 * 查詢區間最大值 query(l,r) * 區間加值 modify(l,r,x) ----  --- ## construct  ---- ```cpp const int N = 1<<18; int tr[N<<1], n; ``` * root := *1* * left node:= *i<<1* * right node:= *i<<1|1* * parent:= *i>>1* * brother:= *i^1* * leaf:= n~2n-1 * others:= 1~n-1 ---- ## build ```cpp void build(int v[]) { for(int i = 0; i < n; i++) tr[i+n] = v[i]; for(int i = n-1; i > 0; i--) tr[i] = max(tr[i<<1], tr[i<<1|1]); } ``` ---- ## modify 從底部開始 ```cpp void modify(int p, int x) { for(tr[p+=n] = x; p > 1; p>>=1) tr[p>>1] = max(tr[p],tr[p^1]); } ``` ---- ## query without recursive * 從底部開始 (l>>=1, r>>=1) * `query [l,r)` * l 是右子樹 * `res += tr[l++]` * r 是左子樹 * `res += tr[--r]` ---- ```cpp int query(int l, int r) { // [l,r) int res = -1e9; for(l+=n,r+=n; l<r; l>>=1,r>>=1) { if(l&1) res = max(res, tr[l++]); if(r&1) res = max(res, tr[--r]); } return res; } ``` --- ## Lazy tag lazy tag 顧名思義懶得做 那就把改變先記起來 等到有需要在做 ---- #### Modify: 0. 先把要更新的區域的 tag 往下推掉(push) * push(l+n), push(r-1+n) 2. 一直拆分更新區域, 直到完全覆蓋更新區域 3. 之後直接更新該節點的值, 並且在該點標上 lazy tag, 代表子節點還沒加上去的值 4. 往上把更新值後, 受影響的父節點更新掉(pull) ---- #### Query 0. 先把要詢問的區域的 tag 往下推掉 * push(l+n), push(r-1+n); 2. 直接查詢 ---- ### 實作 ---- ### upd (int i, int x) 改變值且更新 LazyTag ```cpp void upd(int p, int x) { tr[p] += x; if(p < n) tag[p] += x; } ``` ---- ### push (int i) 由上往下把 tag 都推下來 ```cpp void push(int p) { for(int h = __lg(n); h >= 0; h--) { int i = p>>h; // hth ancestor of p if(!tag[i>>1]) continue; upd(i, tag[i>>1]); upd(i^1, tag[i>>1]); tag[i>>1] = 0; } } ``` ---- ### pull (int i) 由下往上把更新過後的值 拿去更新父節點 ```cpp void pull(int p) { while(p > 1) { // do not forget the tag[p>>1] term tr[p>>1] = max(tr[p],tr[p^1])+tag[p>>1]; p >>= 1; } } ``` ---- ### query (int l, int r) ```cpp int query(int l,int r) { push(l+n), push(r-1+n); int res = -1e9; for(l+=n,r+=n; l<r; l>>=1,r>>=1) { if(l&1) res = max(res, tr[l++]); if(r&1) res = max(res, tr[--r]); } return res; } ``` ---- ### modify (int l, inr r, int x) ```cpp void modify(int l,int r, int d) { int tl = l, tr = r; push(l+n), push(r-1+n); for(l+=n,r+=n; l<r; l>>=1,r>>=1) { if(l&1) upd(l++, d); if(r&1) upd(--r, d); } // uses tl,tr here for l,r changed pull(tl+n), pull(tr-1+n); } ```