<style> .reveal .slides { text-align: left; font-size:35px; } </style> ## 線段樹(2) Introduction to Competitive Programming 2/17 ---- - 懶人標記 - 基礎區間修改應用 - 更多變化應用 --- ### 區間更新區間詢問 給一長度為 n 的整數序列，和 m 筆操作 操作分兩種 1. $\text{update l r v}$，將序列的區間 [l, r] 加值 v 2. $\text{query l r}$，詢問序列的區間 [l, r] 總和 $n,m<10^5$ ---- ### 使用單點修改線段樹 單點修改 [l , r] 範圍 時間複雜度最差的情況下，如果每次都加值整個序列， 為 $O(n\log n)$ 修改 m 次，時間複雜度 $O(mn\log n)$， 比直接修改原陣列 $O(mn)$ 還差！ ---- ### 懶人標記 lazy tag 懶人標記的思想就是，如果所在的區間被修改的區間完全覆蓋的話，就在當前的區間打一個標記，代表這個區間以及下面所有區間都需要修改。  如果加值[0,6] 可以發現 [0,3] [4,5] [6,6] 以下的區間都要修改 ---- 多開一個陣列 tag 紀錄這個區間以及以下都要加值 ```cpp= void update(int id,int l,int r,int ql, int qr, int v){ if(ql <= l && r <= qr){ //如果當前區間被更新區間完全覆蓋到 tag[id] += v; //就打標記紀錄以下區間都要更新 return; } int mid=(l+r)>>1; if(ql <= mid) update(cl(id),l,mid); if(qr > mid) update(cr(id),mid+1,r); pull(id, l, r); } ``` ---- ### 懶人標記 lazy tag 可以發現使用懶人標記的修改會變的跟本來的查詢很像，都是所在區間被要求的區間完全覆蓋時，就打標記 $\to$ 回傳，所以 code 其實也差不多。 ---- ### push 函數 打上標記之後，下次經過這些節點時再更新節點， 並且將標記往下推。 因此在 update, query 函數最前面多一行 push ```cpp= void push(int i, int l, int r) { if(tag[i]) { seg[i] += tag[i] * (r - l + 1); // 更新區間 [l, r] if(l != r) { // 把標記往下推 tag[cl(i)] += tag[i]; tag[cr(i)] += tag[i]; } tag[i] = 0; // 更新完區間後，把標記歸 0 } } void update(int id,int l,int r,int ql, int qr, int v){ push(id, l, r); ... } int query(int id,int l,int r,int ql,int qr){ push(id, l, r); ... } ``` ---- 但這樣會發現上面的節點(紅色)也需要更新， 而更新就在 `update` 函數打完標記之後，回傳時順便更新即可  ---- ### pull 函數更新區間 ```cpp= void update(int id,int l,int r,int ql, int qr, int v){ if(ql <= l && r <= qr){ tag[id] += v; return; } int mid=(l+r)>>1; if(ql <= mid) update(cl(id),l,mid, ql, qr, v); if(qr > mid) update(cr(id),mid+1,r, ql, qr, v); pull(id, l, r); // 更新所有遍歷到的區間 } ``` ---- ### pull 函數 更新當前節點，則需要先把左右子節點都更新 再拿來更新自己 ```cpp= void pull(int i, int l, int r) { int mid = (l+r)>>1; push(cl(i), l, mid); push(cr(i), mid + 1, r); seg[i] = seg[cl(i)] + seg[cr(i)]; } ``` ---- ### 更新範例程式碼 ```cpp= void update(int i, int l, int r, int ql, int qr, int v){ push(i, l, r); // 懶標下推 if(ql <= l && r <= qr) { tag[i] += v; return; } int mid = (l + r)>>1; if(ql <= mid) update(cl(i), l, mid, ql, qr, v); if(qr > mid) update(cr(i), mid + 1, r, ql, qr, v); pull(i, l, r); // 更新當前區間的總和 } ``` ---- ### 查詢 對於查詢其實操作是跟單點修改線段樹差不多的， 只是記得每次詢問前先記得把懶人標記更新並往下推。 ---- 跟單點修改線段樹相比 多一行 ```push``` 函數來更新節點並把懶人標記往下推 ```cpp= int query(int i, int l, int r, int ql, int qr) { push(i, l, r); if(ql <= l && r <= qr) { return seg[i]; } int mid = (l + r) / 2, ret = 0; if(ql <= mid) ret += query(cl(i), l, mid, ql, qr); if(qr > mid) ret += query(cr(i), mid + 1, r, ql, qr); return ret; } ``` --- ## 例題時間 ---- 使用線段樹通常有兩個條件 - 當前節點維護的資訊可以從左右子節點得到 - 操作有結合率 就能用線段樹維護 ---- ### 例題：[CSES: Polynomial Queries](https://cses.fi/problemset/task/1736/) 給一個長度為 n 的整數序列，和 m 筆操作 操作分兩種 * $\text{0 l r}$ : 將區間 [l, r] 範圍的元素 $a_l$ 加 1， $a_{l+1}$ 加 2 ... 以此列推 * $\text{1 l r}$ : 詢問區間 [l, r] 的總和 至於這題要如何維護呢？ 🥴 ---- 詢問為求區間總和， 因此只需要把等差加值好好的處理就做完了 ---- 可以發現，我們對區間的加值會是一個從 1 開始、公差為 1 的等差數列，我們便可以維護這個性質，因為只要有首項、項數、公差，就可以在 $O(1)$ 時間算出等差數列的總和（高中數學）。 ---- 項數就是那個區間的大小，而當一個等差數列疊加到另外一個等差數列上時 ```cpp 1 2 3 4 5 6 + 1 2 3 4 5 6 _______________________ 1 3 5 7 9 11 6 ‾ ‾ ‾ ‾ ‾‾ ``` 可以發現重疊的部分的首項跟公差就會變成兩者相加了！ 中間重疊部分的公差直接就變成 2，我們只需要維護這些，就可以解出這題了。 ---- ### 懶人標記下推 下推時，右子區間的首項要再加上左子區間的長度*公差 first 陣列紀錄當前區間第一個元素(首項)要加值多少 diff 陣列紀錄公差 ```cpp= int diff[MXN<<2], first[MXN<<2], seg[MXN<<2]; void push(int id, int l, int r){ if(diff[id]){ // (首項+末項) * 項次 / 2 seg[id] += (first[id]*2 + (r-l)*diff[id]) * (r-l+1) / 2; if(l != r){ diff[cl(id)] += diff[id]; diff[cr(id)] += diff[id]; first[cl(id)] += first[id]; first[cr(id)] += first[id] + ((l+r)/2 - l + 1) * diff[id]; } diff[id] = first[id] = 0; } } ``` ---- ### 區間更新 --- 打懶人標記 由於每次加的首項固定是 1，因此遞迴時不需要傳遞加值的參數 打懶人標記時，再判斷跟加值左界差多少即可 ```cpp= void update(int i, int l, int r, int ql, int qr){ push(i, l, r); // 懶標下推 if(ql <= l && r <= qr) { first[i] += (l - ql + 1); // 區間首項加的值為當前左界 - 詢問左界 + 1 diff[i]++; return; } int mid = (l + r)>>1; if(ql <= mid) update(cl(i), l, mid, ql, qr); if(qr > mid) update(cr(i), mid + 1, r, ql, qr); pull(i, l, r); // 更新當前區間的總和 } ``` ---- ### 區間詢問 跟一般的總和線段樹沒什麼差別 seg 陣列一樣是儲存區間總和 不特別贅述 ---- ## [Range Updates and Sums](https://cses.fi/problemset/task/1735) 給一長度為 n 的整數序列，和 m 筆操作 操作分**三種** 1. $\text{update l r v}$，將序列的區間 [l, r] 加值 v 2. $\text{update l r v}$，將序列的區間 [l, r] 都設值成 v 3. $\text{query l r}$，詢問序列的區間 [l, r] 總和 $n,m<10^5$ 多了一個區間設值 ---- 兩種操作單獨出現都可以解掉，但同時出現時要好好處理。 由於需要維護兩種懶標，我們還需要考慮同時有兩個懶標存在的情況。 ---- 兩個懶人標記 setTag 和 addTag 分別維護區間設值與區間加值 在維護標記時，可以分為 3 種情況 1. 本來沒有任何標記，現在再加值/設值 2. 本來有加值/設值標記，現在再加值 3. 本來有加值/設值標記，現在再設值 ---- ### 1. 本來沒有任何標記，現在再加值/設值 那就跟一般加值/設值線段樹一樣 打上加值或設值標記就好 ---- ### 2. 本來有加值/設值標記，現在再加值 - 本來有加值標記，那再加值有疊加性，不影響 - 本來有設值標記再加值，可以先設值完之後再加值 ---- ### 3. 本來有加值/設值標記，現在再設值 區間設值則之前所有的標記都要不用理他了 直接把原本的加值/設值都清空，設上新的值 ---- 綜合以上的 case，只需要好好處理以下情況 1. 更新區間時，同時有設值/加值標記時，先設值再加值 2. 有設值操作時，到覆蓋的區間先把原有的設值/加值標記先清空，再放上設值標記 其他跟一般線段樹相同 ! ---- 把這份講義的內容好好理解完能自己刻出來的話， 理論上線段樹實做就不會有什麼問題了 夠熟的話也能跟講師一樣，無腦三分鐘內刻完區間修改線段樹 ---- 剩下的就是應付各種題目的題目變化 題目主要有兩種 1. 轉換題意，配合基礎的加值/求區間總和或極值(題單的D) 2. 維護的東西與平常不同，好好維護懶人標記以及合併(題單的C,E) ---- 而 BIT 的 code 比 segment tree 短很多， 遇到資料結構題時，請先想一下 BIT 是否可做(區間修改/單點詢問 or 單點詢問/區間修改) 如果可以的話請不要沒事亂砸線段樹 實作量較大，bug 可能也比較多 ---- [題單](https://vjudge.net/contest/604328)