<style> .reveal .slides { text-align: left; font-size:35px; } </style> ## 線段樹 - 2 Introduction to Competitive Programming 4/3 ---- - 懶人標記 - 基礎區間修改應用 - 更多變化應用 --- ### 區間更新區間詢問 給一長度為 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 懶人標記的思想就是，如果所在的區間被修改的區間完全覆蓋的話，就在當前的區間打一個標記，代表這個區間以及下面所有區間都需要修改。 ----  如果加值[2,6] 可以發現 [2,3] [4,5] [6,6] 區間都要打標記 ---- 為了維護好每個節點的Info，若是走到有打 lazy tag 的節點，必須把這個 tag 往下傳遞一層 ---- $\texttt{info}$ $\to$ 當前節點的總和 $\texttt{len}$ $\to$ 當前節點的長度 $\texttt{tag}$ $\to$ 當前節點的標記 $L_{\text{tag}}$ $\to$ 左子節點的標記 $R_{\text{tag}}$ $\to$ 右子節點的標記 如果是區間總和的線段樹 $\text{tag}$ 代表區間要被加值多少 $\texttt{info += tag * len}$ $L_{\text{tag}} = R_{\text{tag}} = \text{tag}$ $\text{tag} = 0$ $\text{tag}$設為0代表不用加值 ---- ### Push 函數 一個把tag往下傳遞的函數 維護總和的Push 函數 ```cpp! void push(int p, int l, int r) { if (tag[p] != 0) { info[p] += tag[p] * (r - l); if (r - l != 1) { // 如果是葉節點 -> 沒有左右子節點 (沒判會RE) tag[cl(p)] = tag[cr(p)] = tag[p]; } tag[p] = 0; } } ``` ---- ### Pull 函數 一個往上合併兩個節點資訊的函數 因為合併需要用到兩個子節點 所以要先把兩個子節點的tag往下傳遞 ```cpp= void pull(i32 p, i32 l, i32 r) { i32 m = (l + r) >> 1; push(cl(p), l, m); push(cr(p), m, r); info[p] = info[cl(p)] + info[cr(p)]; } ``` ---- ### 更新範例程式碼 ```cpp= void rangeModify(i32 p, i32 l, i32 r, i32 x, i32 y, i64 v) { push(p, l, r); if (l >= x && r <= y) { tag[p] += v; return; } i32 m = (l + r) >> 1; if (x < m) rangeModify(cl(p), l, m, x, y, v); if (y > m) rangeModify(cr(p), m, r, x, y, v); pull(p, l, r); } ``` ---- ### 查詢 對於查詢其實操作是跟單點修改線段樹差不多的， 只是要記得把走過的節點的懶人標記往下傳遞。 ---- 跟單點修改線段樹相比 多一行 ```push``` 函數來更新節點並把懶人標記往下傳遞 ```cpp= i64 rangeQuery(i32 p, i32 l, i32 r, i32 x, i32 y) { push(p, l, r); if (l >= y || r <= x) return 0; if (l >= x && r <= y) return info[p]; i32 m = (l + r)>> 1; return rangeQuery(cl(p), l, m, x, y) + rangeQuery(cr(p), m, r, x, y); } ``` --- ## 例題時間 ---- - 當前節點維護的資訊可以從左右子節點得到 通常只要資訊有這個性質 就能用線段樹維護 ---- ### 例題：[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。 只需要維護首項還有公差，就可以算出總和了。 ---- ### 懶人標記下推 a是首項, d是公差 要注意的是右子區間的首項要小算一下。 ```cpp= void push(i32 p, i32 l, i32 r) { // need compelete if (tag[p].a != 0) { i32 len = r - l; i32 m = (r + l) >> 1; info[p].sum += (((2 * tag[p].a) + (len - 1) * tag[p].d) * len) / 2;; if (r - l != 1) { tag[cl(p)].a += tag[p].a; tag[cr(p)].a += tag[p].a + (m - l) * tag[p].d; tag[cl(p)].d += tag[p].d; tag[cr(p)].d += tag[p].d; } tag[p].a = 0; tag[p].d = 0; } } ``` ---- ### 區間更新 --- 打懶人標記 由於每次加的首項固定是 1，因此遞迴時不需要傳遞加值的參數 特別要注意的是，每個區間的首項要計算一下，不要直接設成1 ```cpp= void rangeModify(i32 p, i32 l, i32 r, i32 x, i32 y) { push(p, l, r); if (l >= x && r <= y) { tag[p].d++; tag[p].a += (l - x + 1); return; } i32 m = (l + r) >> 1; if (x < m) rangeModify(cl(p), l, m, x, y, v); if (y > m) rangeModify(cr(p), m, r, x, y, v); pull(p, l, r); } ``` ---- ## [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. 有設值操作時，到覆蓋的區間先把原有的設值/加值標記先清空，再放上設值標記 其他跟一般線段樹相同 ! ---- BIT 的 code 比 segment tree 短很多， 遇到資料結構題時，請先想一下 BIT 是否可做(區間修改/單點詢問 or 單點詢問/區間修改) 如果可以的話請不要沒事亂砸線段樹 實作量較大，bug 可能也比較多 ---- [題單](https://vjudge.net/contest/706717)