<style> .reveal .slides { text-align: left; font-size:35px } </style> # Segment Tree Introduction to Competitive Programming 2/8 ---- * 線段樹（單點修改） * 線段樹（區間修改） --- ## 線段樹 Segment Tree 單點修改區間查詢 ---- ### 例題：區間求和 給一長度為 n 的陣列，和 m 筆操作 操作分兩種 1. $\text{update i a}$，將陣列的第 i 個位置改成 a 3. $\text{query l r}$，詢問陣列 [l, r] 的總和 $n,m<10^5$ ---- 直接對陣列做操作 修改 O(1) 查詢 O(N) 複雜度：O(NM) TLE ---- ### 線段樹 線段樹是一顆二元樹，每個節點分別代表了一段區間，並記錄該區間的資訊。 若有個節點存 [L, R] 的資訊，他的中點 M 為 $\frac{L + R}{2}$，他的左子節點存的就會是 [L, M] 的資訊，右子節點存的是 [M + 1, R] 的資訊 ----  ---- ### 儲存 由於線段樹是一顆二元樹，因此我們可以用陣列的方式存，通常會開 n * 4 的陣列來存線段樹。 根節點是 1：節點 i 的左子節點是 i * 2，右子節點是 i * 2 + 1。 根節點是 0：節點 i 的左子節點是 i * 2 + 1，右子節點是 i * 2 + 2。 ---- ### 性質 線段樹會有 2n - 1 個節點，由於線段樹是完全二元樹，因此他的樹高會是 lgN <!-- 樹高 --> ---- ### 更新節點 更新這個節點的答案，也可以寫在後面的函式內。 ```cpp= #define cl(x) (x * 2) //左子節點index #define cr(x) (x * 2 + 1) //右子節點index void pull(int i) { seg[i] = seg[cl(i)] + seg[cr(i)]; } ``` ---- ### 初始化 將區間分割成兩個小區間，兩個小區間繼續遞迴，直到區間大小只剩一個 ---- 在 [3, 1, 2, 4, 5, 6, 1, 3] 建完後線段樹就會長成這樣  ---- 程式碼： ```cpp= void build(int i, int l, int r) { if(l == r) { seg[i] = arr[l]; return; } int mid = (l + r) / 2; build(cl(i), l, mid); build(cr(i), mid + 1, r); pull(i); } ``` 由於會遍歷過 2n - 1 個節點，複雜度 O(n)。 ---- ### 查詢 如果所在的區間被查詢的區間完整覆蓋，就回傳所在區間的資訊， 否則就確認左右子樹和查詢的區間是否有交集，往有交集的區間遞迴下去，並將回傳的結果合併並回傳。 ---- 我們如果要查詢 [2-5] 的範圍，也就是下圖的四個元素的和  ---- 從根節點遞迴 [1-8] 不在 [2-5] 內，向下遞迴  ---- [1,4] 不在區間 [2,5] 內 繼續往下遞迴  ---- [1,2] 不在區間 [2,5] 內 左子節點不在區間內，往右子節點遞迴  ---- [2,2] 在區間 [2,5] 內 更新當前答案  ---- [3,4] 在區間 [2,5] 內 更新當前答案  ---- [5,8] 不在區間 [2,5] 內 往左子節點遞迴，右子節點不在區間內  ---- [5,6] 不在區間 [2,5] 內 往左子節點遞迴，右子節點不在區間內  ---- [5,5] 在區間 [2, 5] 內 更新答案  ---- 區間 [2, 2], [3, 4], [5, 5] 的總和即為答案  ---- 程式碼實作： ```cpp= int query(int i, int l, int r, int nl, int nr) { if(nl <= l && r <= nr) { return seg[i]; } int mid = (l + r) / 2, ret = 0; if(nl <= mid) { ret += query(cl(i), l, mid, nl, nr); } if(mid < nr) { ret += query(cr(i), mid + 1, r, nl, nr); } return ret; } ``` 複雜度：O(lgN) ---- ### 修改 看要修改的點在左還是右子樹，就往那邊向下遞迴， 修改完後需要確認經過的點的答案是否需要被修改。 ---- 如果要將 a[3] 修改成 7，a[3] 在左子樹，因此往左子樹遞迴。  ---- a[3] 在右子樹，往右邊向下遞迴。  ---- a[3] 在左子樹，往左邊向下遞迴  ---- 發現已經到 a[3] 了，將 a[3] 修改成 7。  ---- 往回更新答案。  ---- 往回更新答案。  ---- 往回更新答案。  ---- 往回更新答案。  ---- 程式碼實作： ```cpp= void update(int i, int l, int r, int p, int v) { if(l == r) { seg[i] = v; return; } int mid = (l + r) / 2; if(p <= mid) { update(cl(i), l, mid, p, v); } else { update(cr(i), mid + 1, r, p, v); } pull(i); } ``` 複雜度：O($\log N$) ---- ### 完整程式碼 ```cpp= #define cl(i) i * 2 #define cr(i) i * 2 + 1 const int N; int seg[N << 2], arr[N]; void pull(int i) { seg[i] = seg[cl(i)] + seg[cr(i)]; } void build(int i, int l, int r) { if(l == r) { seg[i] = arr[l]; return; } int mid = (l + r) / 2; build(cl(i), l, mid); build(cr(i), mid + 1, r); pull(i); } int query(int i, int l, int r, int nl, int nr) { if(nl <= l && r <= nr) { return seg[i]; } int mid = (l + r) / 2; int ret = 0; if(nl <= mid) { ret += query(cl(i), l, mid, nl, nr); } if(mid < nr) { ret += query(cr(i), mid + 1, r, nl, nr); } return ret; } void update(int i, int l, int r, int p, int v) { if(l == r) { seg[i] = v; return; } int mid = (l + r) / 2; if(p <= mid) { update(cl(i), l, mid, p, v); } else { update(cr(i), mid + 1, r, p, v); } pull(i); } ``` ---- ### 例題：[區間最大值](https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/problem/A) 給一長度為 n 的陣列，和 m 筆操作 操作分兩種 1. $\text{update i a}$，將陣列的第 i 個位置改成 a 3. $\text{query l r}$，詢問陣列 [l, r] 的最大值 $n,m<10^5$ ---- 跟區間總和只插在計算答案還有查詢的部分。 ```cpp= void pull(int i) { seg[i] = max(seg[cl(i)], seg[cr(i)]); } ``` ---- ### 例題：Longest Increase Subsequence 就是早上教的 LIS， 給一個長度為 n 的陣列，問你這個陣列的 LIS 是多少。 $n \le 10^5,a_i\le 10^6$ ---- 可以發現本來的 $O(n^2)$ 沒辦法過了，因此我們需要優化 dp 的步驟， LIS 的優化有兩種方式，一種是資料結構的，另外一種是二分搜的方式，而這邊我們會介紹資料結構的方式。 ---- LIS 的 dp 式是 `dp[`$i$`]=max(dp[`$i$`],dp[`$j$`]+1)` 我們可以針對從陣列 1 ~ i - 1 的位置找可以轉移的地方做優化。 在這裡我們可以對值域開線段樹，葉節點存的是所在區間的 dp 值 ---- 這裡可以舉個例子 arr = {$1, 3, 2, 2, 4, 0$} 先將線段樹初始化，由於一開始還沒有數字，所以都是 0。 ---- 查詢線段樹的 arr[1] (1) 以下的範圍的 dp 值來轉移 arr[1]，由於線段樹都是 0，所以我們可以知道 dp[1] 的值為 0 + 1 = 1，然後就是將 dp[1] 插入到 arr[1]，這樣我們遇到比 arr[1] 大的數字時，我們就可以從 arr[1] 去做轉移。 ---- 接著查詢 arr[2] (3) 以下的範圍([0 - 2]) 來轉移 arr[2]，[0 - 2] 的範圍內有 1 可以被轉移，所以就在線段樹上 arr[2] 的位置插入 2(dp[2]) ---- 接下來就以此列推，每次查詢線段樹上哪些地方可以被轉移，再把轉移後的值插入到線段樹上，就可以以每次 $O(lgN)$ 的時間查詢、 $O(lgN)$ 的時間插入，總共複雜度 $O(NlgN)$ 的時間了！ ---- ---- ### 例題：區間最大連續和 給一長度為 n 的陣列，和 m 筆操作 操作分兩種 1. $\text{update i a}$，將陣列的第 i 項改成 a 2. $\text{query l r}$，詢問陣列 [l, r] 的最大連續和 * 最大連續和： 最大化 $a_i + a_{i + 1} + ... + a_{j}$ ，$l \le i \le j \le R$ ---- 可以發現這題是分治的經典題，分治的時候要維護的東西，我們就在線段樹上維護，就可以解掉這題了。 ---- 在分治時有四個東西需要維護，區間的總和、前綴連續最大和、後綴連續最大和以及該區間的連續最大和  於是我們就在線段樹上維護這些東西。 ---- 當我們要合併兩段區間時，下個區間的連續最大和有三個可能，左邊區間的連續最大和，右邊區間的連續最大和，跟穿過中間的連續最大和，而穿過中間的連續最大和會是左邊區間的後綴連續最大和加上右邊區間的前綴連續最大和。 ---- 而修改就跟一般線段樹的修改一樣，只是需要改四個值。 ---- 我們就可以寫出以下程式碼： ```cpp= struct node{ ll pre, suf, sum, cmax; }; node seg[N << 2]; ll arr[N]; node pull(node a, node b) { node ret; ret.sum = a.sum + b.sum; ret.pre = max({a.pre, a.sum + b.pre}); ret.suf = max({a.suf + b.sum, b.suf}); ret.cmax = max({a.cmax, b.cmax, a.suf + b.pre}); return ret; } void build(int i, int l, int r) { if(l == r) { seg[i].pre = seg[i].suf = seg[i].sum = seg[i].cmax = arr[l]; return; } build(cl(i), l, M); build(cr(i), M + 1, r); seg[i] = pull(seg[cl(i)], seg[cr(i)]); } void update(int i, int l, int r, int p, int v) { if(l == r) { seg[i].pre = seg[i].suf = seg[i].sum = seg[i].cmax = v; return; } if(p <= M) { update(cl(i), l, M, p, v); } else { update(cr(i), M + 1, r, p, v); } seg[i] = pull(seg[cl(i)], seg[cr(i)]); } node query(int i, int l, int r, int nl, int nr) { if(nl <= l && r <= nr) { return seg[i]; } node reta, retb; if(nl <= M) { reta = query(cl(i), l, M, nl, nr); } if(M < nr) { retb = query(cr(i), M + 1, r, nl, nr); } return pull(reta, retb); } ``` ---- ### 例題： 第 k 個 1 給一長度為 n 且只有 0 跟 1 的陣列，和 m 筆操作 操作分兩種 1. $\text{update i a}$，將陣列的第 i 項 1 改成 0，0 改成 1 2. $\text{query k}$，詢問詢問第 k 個 1 在陣列的哪個位置（保證 1 至少有 k 個）。 $n, m \le 10^5$ ---- 在 [1, 0, 1, 1, 1, 1, 0, 1] 上 首先可以觀察到，如果以 arr[i] 前面有幾個 1 來畫圖的話，可以畫出以下的圖。  ---- 由此我們可以對 i 做二分搜，目標是 arr[i] 前面有 k 個 1 的且arr[i] 的位置是 1。 這樣就可以用每次查詢 $O(log^2N)$，修改 $O(logN)$，全部複雜度 $O(Nlog^2N)$ 的複雜度通過這題了。 以下還有另外一個複雜度更好的做法。 ---- 我們可以用記錄總和的線段樹記錄一個區間有幾個 1，並用將查詢改一下，就可以找出第 k 個 1 了。 以下給出一個很直觀的例子： [1, 0, 1, 1, 1, 1, 0, 1] 中找出第 4 個 1。 ---- 建完記錄總和的線段樹會長成這樣。  ---- 紅色代表的是所在的區間，左邊的區間只有 3 個 1，所以我們會向右邊的區間遞迴。  ---- 前三個 1 在左邊的區間，我們要找到的變成右邊區間的第一個 1，左邊的區間有兩個 1，所以我們會往左邊的區間遞迴  ---- 目標一樣是找到所在區間的第一個 1，所以我們會往左邊遞迴。  ---- 發現到底了(l == r)，所以回傳這邊的位置。  ---- 這樣子通過判斷節點的值決定要往哪邊詢問的方式，也被稱作線段樹上二分搜。 ---- ### 實作程式碼 ```cpp= int query(int i,int l,int r,int k) { if(l == r) { return l; } if(seg[cl(i)] >= k) { return query(cl(i), l, M, k); } else { return query(cr(i), M + 1, r, k - seg[cl(i)]); } } ``` ---- ### 例題：區間第 k 個 1 問題跟上面的相似，只是從整個陣列第 k 個變成詢問 [l, r] 區間的第 k 個 1 (保證存在)。 ---- 解答：如果 [0, l - 1] 中有 x 個 1， 問題就可以轉化成詢問整個陣列的第 x + k 個 1，由於有保證答案存在，因此不用管下界 r。 ---- ### 例題：[區間不同數字數量 1](https://codeforces.com/edu/course/2/lesson/4/4/practice/contest/274684/problem/D) 給一個長度為 n 的陣列 a，跟 m 筆操作 * $1$ $l$ $r$，詢問 [l, r] 有幾個不同的數字 * $2$ $i$ $v$，將 $a_i$ 改成 $v$ $1 \le a_i \le 40$ ---- 由於 a_i 只有 40 種，所以就開 40 顆線段樹每次查詢 [l, r] 裡面有沒有某種數字 ---- 空間複雜度：40 顆 * 4 倍 * 100000 個元素 * 4 byte = 61 MB ---- long long 是 8 bytes = 64 bits 用每個 bit 去存那些值存在，更新答案時就可以用位元 and 完成 只需要開一顆線段樹 ---- ### 例題：[區間不同數字數量 2](https://cses.fi/problemset/task/1734) 給一個長度為 n 的陣列，跟 m 筆操作 每次詢問區間 [a, b] 有幾個相異數字 $1 \le a_i \le 10^9$ ---- 相異數字數量是沒有結合律的，沒辦法很好的用線段樹去維護，在這題我們要將詢問的順序調換，讓詢問彼此之間產生關聯，這種做法只有在題目沒有強制在線的時候才可以使用，因此也被稱作離線算法。 ---- 首先將詢問根據右界從小到大排序，再額外開一個陣列 cnt 維護每個值上一次出現在原陣列的哪個位置，對於每一個詢問 [L, R]，我們就可以用 $\sum\limits_{i = L}^{R} \text{cnt}_i$ 來知道這段有幾個相異元素。 以下用 arr = [2, 2, 1, 2, 3] Q = ([1, 3], [2, 5], [2, 3], [2 4], [1, 4])來舉個例 ---- 第一步，查詢 arr[1] 的數值在之前有沒有出現過，由於是第一個所以很顯然沒有，我們記錄 arr[1] (2) 最後在 1 的位置，並處理右界是 1 的詢問。  ---- 接下來查詢 arr[2] (2) 之前有沒有出現過，結果是有，於是就把 cnt[1] 的位置歸 0，將 cnt[2] 的位置更新成 1，並處理右界是 2 的詢問。  ---- 接下來查詢 arr[3] (1) 之前有沒有出現過，結果沒有，於是將 cnt[3] 的位置設成 1，並處理右界是 3 的詢問。 [1, 3] $\rightarrow$ $\sum\limits^3_{i = 1}\text{cnt}_i = 2$，這組詢問的答案就是 2。 [2, 3] $\rightarrow$ $\sum\limits^3_{i = 2}\text{cnt}_i = 2$  ---- 接下來查詢 arr[4] (2) 之前有沒有出現過，結果是有，於是就把 cnt[2] 的位置歸 0，將 cnt[4] 的位置更新成 1，並處理右界是 4 的詢問。 [1, 4] $\rightarrow$ $\sum\limits^4_{i = 1}\text{cnt}_i = 2$ [2, 4] $\rightarrow$ $\sum\limits^4_{i = 2}\text{cnt}_i = 2$  ---- 接下來查詢 arr[5] (3) 之前有沒有出現過，結果沒有，於是將 cnt[5] 的位置設成 1，並處理右界是 5 的詢問。 [2, 5] $\rightarrow$ $\sum\limits^5_{i = 2}\text{cnt}_i = 3$  ---- 可以來分析一下用線段樹記錄這個的複雜度 記錄數字之前的位置可以用 map，複雜度：$O(logN)$ 用線段樹維護 cnt，複雜度：$O(logN)$ 總共的複雜度就是 $O(NlogN)$ 至於在線做法會留到開學後的課程。 --- ## 線段樹 區間修改區間查詢 ---- ### 例題：區間求和 2 給一長度為 n 的陣列，和 m 筆操作 操作分兩種 1. $\text{update l r a}$，將陣列的 [l, r] 加上 a 2. $\text{query l r}$，詢問陣列 [l, r] 的總和 $n,m<10^5$ ---- ### 單點修改線段樹 單點修改 [l , r] 範圍 時間複雜度 O(nlogn) 做 m 次，時間複雜度 O(mnlogn)，比直接修改原陣列 O(mn) 還差！ ---- ### 懶人標記 lazy tag 懶人標記的思想就是，如果所在的區間要被修改的區間完全覆蓋的話，就在這邊打一個懶標，並在下次經過這個節點時再將其下推。 可以發現使用懶人標記的修改會變的跟本來的查詢很像，都是所在區間被要求的區間完全覆蓋時，就打標記/回傳，所以 code 其實也差不多。 ---- ### 儲存 跟前面的一樣，只是需要多存開一個 4 * n 的陣列存懶人標記。 ---- ### 修改 我們沿用之前已經建好的樹 [3, 1, 2, 4, 5, 6, 1, 3] 並對 [2,8] 加上 3。  ---- 從根節點開始遞迴，[1,8] 不在 [2,8] 內，向下遞迴  ---- [1,4] 不在區間 [2,8] 內 繼續往下遞迴  ---- [1,2] 不在區間 [2,4] 內 左子節點不在區間內，往右子節點遞迴  ---- [2,2] 在區間內，打下懶標，由於遞迴到底了，接著就回到上一層。  ---- [1, 2] 下面該走的都走過了，接下來就跟單點修改一樣，要將 [1,2] 的答案算出來，因此我們將 [1, 1], [2, 2] 的懶標下推。  ---- ### 計算答案 將左子節點跟右子節點的懶標下推，並算出所在區間的答案。 ```cpp= void pull(int i, int l, int r) { if(l == r) return; push(cl(i), l, M); push(cr(i), M + 1, r); seg[i] = seg[cl(i)] + seg[cr(i)]; } ``` ---- ### 標記下推 如果走到有標記的節點，就需要將值算出來，並將標記下推。 ```cpp= void push(int i, int l, int r) { if(lazy[i]) { seg[i] += lazy[i] * (r - l + 1); //[l,r] if(l != r) { lazy[cl(i)] += lazy[i]; lazy[cr(i)] += lazy[i]; } lazy[i] = 0; } } ``` ---- [3, 4] 在區間內，打下懶標，回到上一層。  ---- 更新 [1, 4] 答案，將 [1, 2]、[3, 4] 的懶標下推。 由於 [1, 2] 涵蓋區間的長度為 2，因此會加上 3 * 2  ---- [5, 8] 在區間內，打下懶標，回到上一層。  ---- 更新 [1, 8] 答案，將 [1, 4], [5, 8] 懶標下推。 由於 [5, 8] 涵蓋長度是 4 因此會加上 3 * 4。  ---- 遞迴結束，圖上的紫色就是剩下的懶標，之後查詢、更新遇到他們再將他們更新  ---- ### 範例程式碼 ```cpp= void update(int i, int l, int r, int nl, int nr, int v){ push(i, l, r); // 懶標下推 if(nl <= l && r <= nr) { lazy[i] = v; return; } int mid = (l + r) / 2; if(nl <= mid) { update(cl(i), l, mid, nl, nr, v); } if(mid < nr) { update(cr(i), mid + 1, r, nl, nr, v); } pull(i, l, r); // 更新答案 } ``` ---- ### 查詢 對於查詢其實操作是跟前面差不多的，只是從打下懶標變成直接回傳答案而已。 ---- ```cpp= ll query(int i, int l, int r, int nl, int nr) { push(i, l, r); if(nl <= l && r <= nr) { return seg[i]; } int ret = 0; int mid = (l + r) / 2; if(nl <= mid) { ret += query(cl(i), l, mid, nl, nr); } if(mid< nr){ ret += query(cr(i), mid + 1, r, nl, nr); } return ret; } ``` ---- ### 例題：區間設值、加值 給一長度為 n 的陣列，和 m 筆操作 操作分三種 * $\text{1 l r a}$，將陣列的 [l, r] 改成 a * $\text{2 l r a}$，將陣列的 [l, r] 加上 a * $\text{3 l r}$，詢問陣列 [l, r] 的總和 $n,m<10^5$ ---- 兩個修改的操作單獨出現都可以直接用區間修改的線段樹解掉，但是同時出現時會發生一點問題。 由於需要維護兩種懶標，我們還需要維護同時間有兩個懶標存在的情況。 ---- 在這題我們只需要額外維護一個地方，當改值的懶標下推時遇到加值的懶標，由於這種情況發生時，改值一定是比加值還晚的，因此改值會把加值覆蓋掉，底下是實作。 ```cpp= void push(int i, int l, int r){ if(seg[i].lazy1) { seg[i].val = (r - l + 1) * seg[i].lazy1; if(l != r) { seg[cl(i)].lazy1 = seg[i].lazy1; seg[cr(i)].lazy1 = seg[i].lazy1; seg[cl(i)].lazy2 = 0; seg[cr(i)].lazy2 = 0; } seg[i].lazy1 = 0; } if(seg[i].lazy2) { seg[i].val += seg[i].lazy2 * (r - l + 1); if(l != r) { seg[cl(i)].lazy2 += seg[i].lazy2; seg[cr(i)].lazy2 += seg[i].lazy2; } seg[i].lazy2 = 0; } } ``` <!-- ### 例題：區間開根號 給一個長度為 n 的陣列，和 m 筆操作 操作分兩種 * $\text{0 l r}$，將區間 [l, r] 的每個值 $a$ 都變成 $\sqrt{a}$ * $\text{1 l r}$，詢問區間 [l, r] 的總和 $n, m \le 10^5, a_i \le 10^9$ 看到區間修改，首先想到的就是懶標了。 不過對區間的元素開根號好像沒辦法只依據區間的值和他的子節點來直接的算出來。 懶標需要維護的東西有兩種 * 下推時候的疊加性 * 通過所在區間的資訊來直接算出這個節點之後的值 這題因為沒辦法維護通過所在區間的資訊來直接算出答案，所以沒辦法用懶標去維護對區間開根號... --> ---- ### 例題：[怪怪的區間加值](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)$ 時間算出等差數列的總和（高中數學）。 ---- 項數就是那個區間的大小，而當一個等差數列疊加到另外一個等差數列上時 $\,\,\,$ 1 2 3 4 5 6 +$\,\,\,\,$ 1 2 3 4 5 $\,$ 6 $\,\,\,$ 1 <span style="color: red;">3 5 7 9 11 </span>6 可以發現重疊的部分的首項跟公差就會變成兩者相加了！ 中間重疊部分的公差直接就變成 2，我們只需要維護這些，就可以順暢的解出這題了。 ---- ### 實作一下 ----