<style> .reveal .slides { text-align: left; font-size:30px } </style> ## 高維偏序問題 & 持久化資料結構 ---- - CDQ分治 - 二維資節 - 2D BIT - 2D 線段樹 - 持久化 - 持久化線段樹 - K-th Number - 樹上持久化 - 可復原並查集 - 時間線段樹 --- ## CDQ 分治 IOI 2008 金牌得主陈丹琦 (Dan-qi Chen)提出 用來解決偏序問題，加入資料結構後(BIT)也可以解決三維偏序問題 ---- ## 一維偏序問題 給集合 $s$，對於集合內的每個元素 $a$， 有多少元素 $b\in s$ 小於 $a$ ---- ## 二維偏序問題 給二維空間上 $n$ 個點 $(x_i, y_i)$ 求出有多少點對符合 $i\neq j$, $x_i < x_j$, $y_i < y_j$ ---- 會發現這個問題和逆序數對問題很像 逆序數對為給定一個序列 $a$，求有多少數對符合 $i < j$ 且 $a_i > a_j$ ---- 把 $n$ 個點 $(x_i, y_i)$ 先照 $x_i$ 排好後， 就和逆敘數對的序列的 index 一樣是升序的 接下來的問題就和逆序數對相似 ---- 要解決二維偏序問題 先將第一個維度排序後，接下來有以下幾種統計第二個維度的方法 : 1. merge sort 2. BIT 等資料結構 而二維的 CDQ 分治，他的實作代碼和 merge sort 差不多， 也是遞迴 $[l,mid]$ 和 $[mid+1,r]$ 去解決子問題後， 計算左區間對右區間的影響（貢獻） ---- 遞迴 $[l,mid]$ 和 $[mid+1,r]$ 去解決分別的子問題 計算左區間對右區間的影響（貢獻） ```cpp= void cdq(int l, int r){ if(l == r) return; int mid = (l+r)/2; cdq(l, mid); cdq(mid+1, r); merge(l, r); } ``` ---- merge sort 的過程中，計算左區間對右區間的貢獻 已知第一個維度 $x$ 已經排序好了，也就是保證左區間 $x\le$ 右區間的 $x$  ---- 而第二個維度 $y$ 可以分別在子區間排序， 對於右區間的每個元素，計算左區間有多少元素的 $y$ 小於自己的 $y$  做完後順便用雙指針照 $y$ 合併排序 ---- merge sort 的過程中，順便計算左區間對右區間的貢獻 ```cpp= int x[MXN], y[MXN], tmp[MXN]; vector<int> ord; void cdq(int l, int r){ if (l == r) return; int mid = (l+r)/2, i = l, j = mid+1, tid=0; cdq(l, mid); cdq(mid+1, r); for (; j <= r; ++j){ while (i <= mid && y[ord[i]] <= y[ord[j]]) tmp[tid++] = ord[i++]; ans += i - l; tmp[tid++] = ord[j]; } while(i <= mid) tmp[tid++] = ord[i++]; copy(tmp, tmp+r-l+1, ord.begin() + l); } int main(){ cin >> n; for(int i = 0; i < n; i++) cin >> x[i]; for(int i = 0; i < n; i++) cin >> y[i]; ord.resize(n); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&](int lhs, int rhs){ if(x[lhs] != x[rhs]) return x[lhs] < x[rhs]; return y[lhs] < y[rhs]; }); cdq(0, n-1); cout << ans << endl; } ``` ---- ## 三維偏序問題 求 $x_i < x_j, y_i < y_j, z_i < z_j, i\neq j$ 的數量 ---- 一樣遞迴 $[l,mid]$ 和 $[mid+1,r]$ 去解決子問題後， 計算左區間 $[l,mid]$ 對右區間 $[mid+1,r]$ 的影響（貢獻） ---- 照第一維 sort 後，左區間的 $x\le$ 右區間的 $x$ 第二維左右區間各自照 y 排序，把 z 用資料結構維護 ---- 使用資料結構維護 對於左區間在 $z_l$ 加值 右區間的點為詢問左邊有幾個點 $z_l < z_r$ ---- 每輪做完後要把 BIT 清空 記得不能直接跑過 BIT 的每個位置清空 要看左區間用到哪些位置就清空那些就好 ---- 總複雜度遞迴 $\log N$ 層 每層 $O(N\log N)$ 維護 總複雜度 $O(N\log^2 N)$ ---- 只要能把題目轉換成偏序問題，就可以用 cdq 分治解掉。 ---- ```cpp= int CDQ (int l, int r) { if (l == r) return; int mid = (l + r)/2; CDQ(l, mid), CDQ(mid+1, r); vector<int> tmp; for (int i = l, j = mid+1; i <= mid or j <= r; ) { while (i < mid and (j == r or y[ord[i]] <= y[ord[j]])) { bit.add(z[ord[i]], 1); tmp.push_back(ord[i]); i++; } if (j <= r) { ans[ord[j]] += bit.que(z[ord[j]]); tmp.push_back(ord[j]); j++; } } for (int i = l; i <= mid; i++) bit.add(z[ord[i]], -1); copy(tmp.begin(), tmp.end(), ord.begin() + l); }; ``` --- ## 二維資料結構 - 2D BIT - 2D Segment Tree ---- ## 經典題 2D 版 給 $n\times m$ 的矩陣，$q$ 筆操作，每次為以下其中一種 1. 左上 $(l, u)$ 到右下 $(r, d)$ 的子矩陣，每個元素加值 $v$ 2. 詢問左上 $(l, u)$ 到右下 $(r, d)$ 的子矩陣總和 <br><br> - $1\le n, m\le 5000$ - $1\le q\le 10^5$ ---- 開 $n$ 顆線段樹分別維護長度為 $m$ 的區間 ? <span>$\to$ $O(q\cdot n \log m)$<br><!-- .element: class="fragment" data-fragment-index="1" --></span> <span>$\to$ $6\cdot 10^9$<br><!-- .element: class="fragment" data-fragment-index="2" --></span> <span>$\to$ TLE :\(<br><!-- .element: class="fragment" data-fragment-index="3" --></span> ---- $\to$ 2D Data Structure ! ---- ## 2D Binary Indexed Tree ---- 對於 1D BIT，第 $i$ 個位置維護的是區間 $(i-lowbit(i), i]$ 的值。 query(i) 求的是 $1\sim i$ 的前綴總和 ```cpp= ll query(int x){ ll ret = 0; while(x){ ret += bit[x]; x -= lowbit(x); } return ret; } ``` ---- ## 求出前綴總和  求出前綴區間 a[1..11] 從 11 開始， 11 儲存區間長度為 1$\to$ a[11..11] 得到 $a_{11}$，往前求出位置 10 儲存的總和 $\to$ a[9..10] 得到 $a_{[9..10]}$，往前求出位置 8 儲存的總和 $\to$ a[1..8] prefix$_{11} = a[1..8] + a[9..10] + a[11..11]$ ---- 而 2D BIT，第 (i, j) 個位置維護的是區間 (i-lowbit(i), i]$\times$ (j-lowbit(j), j] 的值 並且 query(x, y) 得到的是左上到 (x, y) 的二維前綴區間總和 ---- ## query(x, y) 透過加總 BIT[x][y] + BIT[x][y-lowbit(y)] + BIT[x][(y-lowbit(y)) - lowbit(y-lowbit(y))] +... ```cpp= ll tot = 0; while(y){ tot += BIT[x][y]; y -= lowbit(y); } cout << tot << endl; ``` 可以得到區間 (x-lowbit(x), x] $\times$ [1, y] 的區間總和 ---- ## query(x, y) 使用兩個迴圈遍歷兩個維度，不斷 -lowbit(x) 跳到下一個區間，總共 $\log^2 n$ 個區間 可以得到 $[1, x]\times [1, y]$ 的區間總和 單筆操作複雜度 $O(\log n\log m)$ ---- ```cpp= ll query(int x, int y){ ll ret = 0; for(int i = x; i; i -= lowbit(i)){ for(int j = y; j; j -= lowbit(j)){ ret += BIT[i][j]; } } return ret; } ``` ---- ## update(x, y) 同理，每次使用 +lowbit(x) 遍歷到下一個區間更新 總共 $O(\log n\log m)$ 個區間 ---- ```cpp= void update(int x, int y, int v){ for(int i = x; i <= n; i+=lowbit(i)){ for(int j = y; j <= m; j+=lowbit(j)){ BIT[i][j] += v; } } } ``` ---- 要得到區間 (l, u) ~ (r, d) 的總和， 使用排容 query(r, d) - query(r, u-1) - query(l-1, d) + query(l-1, u-1) 可以得到 ---- $O(q\cdot \log n\log m$) $\to$ $1.5\times 10^7$ ---- ## 二維線段樹 對於二維總和問題使用 2D BIT 可以做到， 但如果把詢問區間總和換成詢問區間最大值則需要換線段樹處理。 ---- 為了方便解說二維線段樹， 接下來的例子一樣使用求 2D 區間總和。 ---- ## 作法 線段樹裡再開線段樹，也就是第一層的線段樹的每個節點都是一棵線段樹 第一層放第一個維度 $r$，第二層放第二個維度 $c$ ---- 遞迴時先遞迴第一個維度 $r$(第一層線段樹)， 每次詢問/修改先遞迴到第一個維度的區間， 接著遞迴第二個維度 $c$ (第二層線段樹)，在第二層遞迴到指定的區間求解 ----  figure modify from https://usaco.guide/CPH.pdf#page=274 ---- ### 功能 - 2維區間詢問 - 單點修改 ### 函數 ```cpp void build(idx, idy, lx, ry, lx, ry); void update(idx, idy, lx, ry, lx, ry, pos, val); int query(idx, idy, lx, ry, lx, ry); ``` ### 線段樹大小 $16 \cdot N\cdot M$ ---- ## build 先遞迴第一個維度 $x$，再對於每個 $x$ 的區間， 遞迴第二層 $y$ 的區間，算出第二層每個子區間的總和 ---- ```cpp= #define cl(x) (x<<1)+1 #define cr(x) (x<<1)+2 void build_y(int idx, int idy, int lx, int rx, int ly, int ry){ if(ly == ry){ tree[idx][idy] = arr[lx][ly]; return; } int my = (ly+ry)/2; build_y(idx, cl(idy), lx, rx, ly, my); build_y(idx, cr(idy), lx, rx, my+1, ry); tree[idx][idy] = tree[idx][cl(idy)] + tree[idx][cr(idy)]; } void build_x(int idx, int lx, int rx){ if(lx != rx){ int mx = (l+r)/2; build_x(cl(idx), lx, mx); build_x(cr(idx), mx+1, rx); } build_y(idx, 0, lx, rx, 0, m-1); } ``` ---- ## query 詢問區間 $(qxl, qyl)\sim (qxr, qyr)$ 的區間和 一樣先遞迴第一個維度 $x$，遞迴到 $x$ 符合的詢問區間再遞迴 $y$ 的詢問區間 ```cpp= int query_y(int idx, int idy, int ly, int ry, int qly, int qry){ if(qly <= ly && ry <= qry){ return tree[idx][idy]; } int my = (ly+ry)/2, ret = 0; if(qy <= my) ret += query_y(idx, cl(idy), ly, my, qly, qry); if(qy > my) ret += query_y(idx, cr(idy), my+1, ry, qly, qry); return ret; } int query_x(int idx, int lx, int rx, int qlx, int qly, int qrx, int qry){ if(qlx <= lx && rx <= qrx){ return query_y(idx, 0, 0, m-1, qly, qry); } int mx = (lx + rx)/2, ret = 0; if(qlx <= mx) ret += query_x(cl(idx), lx, mx, qlx, qly, qrx, qry); if(qrx > mx) ret += query_x(cr(idx), mx+1, qrx, qlx, qly, qrx, qry); return ret; } ``` ---- ## update 更新 a[x][y] = p 所有有被遞迴到的區間都有子區間被更新 因此有遞迴到的區間都繼續遞迴下一個維度 ```cpp= void update_y(int idx, int idy, int lx, int rx, int ly, int ry, int qy, int val){ if(ly == ry){ if(lx == rx) tree[idx][idy] = val; else tree[idx][idy] = tree[cl(idx)][idy] + tree[cr(idx)][idy]; return; } int my = (ly+ry)/2; if(qy <= my) update_y(idx, cl(idy), lx, rx, ly, my, qy, val); else update_y(idx, cr(idy), lx, rx, my+1, ry, qy, val); tree[idx][idy] = tree[idx][cl(idy)] + tree[idx][cr(idy)]; } void update_x(int idx, int lx, int rx, int qx, int qy, int val){ if(lx != rx){ int mx = (lx + rx)/2; if(qx <= mx) update_x(cl(idx), lx, mx, qx, qy, val); else update_x(cr(idx), mx+1, rx, qx, qy, val); } update_y(idx, 0, lx, rx, 0, m-1, qy, val); } ``` ---- ## 2D線段樹複雜度 單筆操作 $O(\log N\log M)$ 空間複雜度 $O(16NM)$ 會發現空間複雜度非常高，因此通常第二個維度都是用動態開點去實作 以節省複雜度 ### d 維複雜度 單筆操作時間複雜度 $O(\log^dN)$ 空間複雜度 $O((4N)^d)$ ---- 對於二維的資料結構問題，如果只維護 $n$ 個一維資料結構複雜度可以過，則不需要毒瘤使用二維資節。 雖然複雜度較好，但實作較複雜容易出錯。 --- ## 可持久化資料結構 可持久化資料結構（Persistent data structure）是一種能夠在修改之後其保留歷史版本（即可以在保留原來數據的基礎上進行修改 --- 比如增添、刪除、賦值）的資料結構。這種資料結構實際上是不可變對象，因為相關操作不會直接修改被保存的數據，而是會在原版本上產生一個新分支 --wikipedia ---- - 可持久化線段樹 - 可復原並查集 --- ## 可持久化線段樹 由於引入者黃嘉泰姓名的縮寫與前中共中央總書記、國家主席胡錦濤(H.J.T.)相同，因此這種資料結構也被稱為「主席樹」 ---- ### 功能 修改值，詢問值，回復歷史版本 如以下操作 1. **單點**修改第 $i$ 格的值為 $v$ 2. 詢問區間 $[l,r]$ 的總和為多少 3. 將序列變回第 $k$ 次操作之前的版本 ---- 當有數值修改，如果每次都重新把整棵線段樹重新存一遍， 則會花費過多的空間與時間 操作 $k$ 次，則有 $k$ 個版本，複雜度為 $O(nk)$ ---- 觀察下面的圖會發現，如果修改一個點的值，最多只會更新 $\log N$ 個點 其他點不影響，所以其實如果有修改只需要儲存那 $\log N$ 個點就好 <div style="position: absolute; right: 60%; top:100%;">  </div> <div style="position: absolute; left: 57%; top:100%;">  </div> ---- 如下圖為例，一樣修改第 3 格的值，則將有變動到的節點重新存一遍，沒變動到的區間直接指向原本的地方 <div style="position: absolute; right: 60%; top:100%;">  </div> <div style="position: absolute; left: 57%; top:100%;">  </div> ---- 原本線段樹的節點使用 index 來找左右子節點， 但持久化後每個版本的節點都會不同 因此我們可以改用指標來實作 ```cpp= struct node{ ll val; node *l, *r; }; ``` ---- 而每次更新版本時，我們需要再儲存新版本的根節點位置， 方便之後回復版本時找到那棵線段樹  ```cpp= void add_ver(int x,int v){ //修改位置 x 的值為 v ver.push_back(update_ver(ver.back(), 0, n-1, x, v)); } ``` ---- ### 實作細節 使用指標實作 ```cpp= struct node{ ll val; node *l, *r; }; vector<node *> ver; //用一個vector紀錄全部版本的根節點 void build(node *now_ver, l, r); ll query(node *now_ver, l, r, ql, qr); node *update_ver(node *pre_ver,int l,int r,int pos,int v); //回傳新建的節點 void add_ver(int x,int v){ //修改位置 x 的值為 v ver.push_back(update_ver(ver.back(), 0, n-1, x, v)); } ``` ---- ### 建新版本 ```cpp= node *update_ver(node *pre_ver, node *x, int l, int r, int pos, int v){ node *x = new node(); //當前位置建立新節點 if(l == r){ x->val = v; return x; } int mid = (l+r)>>1; if(pos <= mid){ //更新左邊 x->l = update(pre_ver->l, x->l, l, mid, pos, v); //左邊節點連向新節點 x->r = pre_ver->r; //右邊連到原本的右邊 } else{ //更新右邊 x->l = pre_ver->l; //左邊連到原本的左邊 x->r = update(pre_ver->r, x->r, mid+1, r, pos, v); //右邊節點連向新節點 } x->val = x->l->val + x->r->val; return x; } ``` ---- ### 用途 上面的舉例為裸的操作， 而持久化線段樹還有很大的用途 通常是用來解決 **兩個維度** 以上的較複雜的問題。 因此通常需要自己分析題目所需，轉換為持久化線段樹實作。 ---- ### 例題 給定長度為 $n$ 的序列 $a$， $q$ 筆詢問，每次問 **區間 [l, r]** 之間，第 **$k$** 大的數字 $1 \le n, q \le 2 \cdot 10^5$ $1 \le a_i \le 10^9$ <span>$\to$ 區間 [l, r]<!-- .element: class="fragment" data-fragment-index="1" --></span> <span>$\to$ 第 k 大<br><!-- .element: class="fragment" data-fragment-index="2" --></span> <span>兩個維度的問題 !<br><!-- .element: class="fragment" data-fragment-index="3" --></span> ---- ## 暴力的作法 每筆詢問使用 nth_element 花 O(n) 時間找第 k 大， 總複雜度 $O(nq)$ <span>會發現這個複雜度好像似曾相似? <!-- .element: class="fragment" data-fragment-index="1" --></span> <span>持久化線段樹的暴力版 O(nk)! <!-- .element: class="fragment" data-fragment-index="2" --></span> ---- 把一個其中一個維度使用持久化的概念 ! - 區間 [l, r] - 第 k 大 ---- ### 區間 [l, r] 使用持久化處理 從第一個數字開始依序加入進線段樹 每更新一個數字，當成多一個版本 線段樹內的每個節點儲存區間 [l, r] 內的數字出現數量 第 $i$ 棵線段樹儲存前綴 $i$ 個元素 ---- ### 第 k 大 要求出線段樹上第 $k$ 小的數字， 可以在線段樹上二分搜。 ```cpp= //val 儲存當前節點的數量 int query(node *x, int l, int r, int k){ if(l == r) return l; int mid = (l+r)>>1; if(x->l->val <= k) return query(x->l, l, mid, k); else return query(x->l, mid+1, r, k - x->l->val); } ``` ---- ### 區間第 k 大 而使用第 $r$ 個版本的數量 - 第 $l-1$ 個版本求出來的數量 即可求出區間 [l, r] 內第 $k$ 小的數字 ```cpp= // pre 為第 l-1 個版本, now 為第 r 個版本 int query(node *pre, node *now, int l, int r, int k){ if(l == r) return l; int mid = (l+r)>>1; int l_num = now->l->val - pre->l->val; if(k <= l_num) return query(pre->l, now->l, l, mid, k); else return query(pre->l, now->l, mid+1, r, k - l_num); } ``` ---- 由於數字範圍很大，記得要先離散化 總複雜度 $O(q\log n)$ ---- ### 樹上求路徑第 k 大 給一棵樹，每個點有點權 q 筆詢問，每次給你 `u v k`，求出點 u 到點 v 的路徑中，權重第 k 大的點權是多少? ---- 可能會想到 LCA ? 還有呢? ---- 序列上求區間第 k 大是第 r 個版本 - 第 l 個版本的數量去求第 k 大 而樹上的問題選一個點當根，當前版本由父節點轉移過來，記錄從祖先到自己總共有那些數字 ---- 如此一來，要求 u 到 v 路徑的數量，等價於 (u 到 lca) + (v 到 lca) - (lca) 的數量就能轉換成相似的問題去做了。 --- ## 可復原並查集 ### Rollback DSU 可復原並查集支援以下功能 1. 查詢元素所在集合 2. 合併兩個集合 3. 回復上一步合併操作 ---- 1. 查詢元素所在集合 2. 合併兩個集合 前兩個操作就是一般的並查集 3. 回復上一步合併操作 第三個操作要如何回復? ---- ### 使用啟發式合併維護 由於路徑壓縮會破壞節點之間的關係， 因此維護並查集時只使用啟發式合併維護，不用路徑壓縮 ```cpp= int f[MXN], sz[MXN]; int find(int x){ return f[x] == x ? x : find(f[x]); } void merge(int x, int y){ x = find(x); y = find(y); if(x == y) return; if(sz[x] > sz[y]){ sz[x] += sz[y]; f[y] = x; } else{ sz[y] += sz[x]; f[x] = y; } } ``` ---- ### 紀錄每次合併前的狀態 可以觀察到每次合併時，改變的為 sz[x], f[y] 因此記錄起來，需要回覆上一個合併操作時，直接設為原本的值即可 ```cpp= vector<tuple<int, int, int, int>> ver; void merge(int x, int y){ x = find(x); y = find(y); if(sz[x] < sz[y]) swap(x, y); ver.push_back(make_tuple(x, sz[x], y, f[y])); if(x != y){ sz[x] += sz[y]; f[y] = x; } } ``` ---- ### Undo 回覆上一個合併操作時，直接設為原本的值即可 ```cpp= void undo(){ auto [x, szx, y, fy] = ver.back(); ver.pop_back(); sz[x] = szx; f[y] = fy; } ``` ---- 由於使用啟發式合併維護並查集，複雜度為 $O(\log n)$ 而記錄版本與回復的時間複雜度為 $O(1)$ 總複雜度為 $O(q\log n)$ ---- ### 時間線段樹 穿越時空來解決動態連通性的問題 ---- ### 經典例題 --- [Dynamic Connectivity](https://cses.fi/problemset/task/2133) 給定一張 $N$ 個點的無向圖，一開始圖上有 $M$ 條邊。 現在有 $Q$ 個操作，每個操作會是以下兩種中的一種： 1. 增加一條連接著編號 $A_i$ 與編號 $B_i$ 的邊。 2. 刪除一條連接著編號 $A_i$ 與編號 $B_i$ 的邊（保證這條邊是存在的）。 每次操作完後請輸出當前的連通塊數量。 - $1 \le N, Q \le 10^5$ - $1 \le A_i, B_i \le N$ ---- 如果只有第一個操作 1. 增加一條連接著編號 $A_i$ 與編號 $B_i$ 的邊。 每次操作完後請輸出當前的連通塊數量。 ---- 使用一般並查集好好維護連通塊大小即可 ---- 如果只有第二個操作 2. 刪除一條連接著編號 $A_i$ 與編號 $B_i$ 的邊（保證這條邊是存在的）。 每次操作完後請輸出當前的連通塊數量。 ---- 先把最後的圖儲存起來 可以反著從最後一個刪除操作做回來，就變成只有加邊的問題了 ---- 而原問題...加邊/刪邊同時... <span>還是不會做 :P <!-- .element: class="fragment" data-fragment-index="1" --></span> ---- ### 時間線段樹 ! 離線作法 把每條邊的生存時間當成區間儲存在線段樹上。 ---- 假設依序有 8 個事件，把每個事件當成一個時間點 1. add 1 3 2. add 2 5 3. query 3 4. remove 1 3 5. add 4 2 6. query 2 7. remove 4 2 8. add 1 2 1 3 這條邊的生存時間為時間 1~4 2 5 這條邊的生存時間為時間 2~8 4 2 這條邊的生存時間為時間 5~7 1 2 這條邊的生存時間為時間 8~8 ---- 把邊放到線段樹上 1 3(1~4), 2 5(2~8), 4 2(5~7), 1 2(8~8)  ---- 把每條邊(event) 依序加入到線段樹上儲存 ```cpp= vector<pair<int, int>> tree[MXN<<2]; void insert(int i, int l, int r, int ql, int qr, pair<int, int> event){ if(ql <= l && r <= qr){ tree[i].push_back(event); return; } int mid = (l+r)>>1; if(ql <= mid) insert(cl(i), l, mid, ql, qr, event); if(qr > mid) insert(cr(i), mid+1, r, ql, qr, event); } ``` ---- 接著只需要遍歷這顆線段樹! 每走到一個節點時，把當前節點上的邊使用並查集合併 往下遞迴子節點，走到一個詢問時儲存連通塊大小到答案中 離開當前節點時，把當前節點上的邊回復 ---- 走到最深時，判斷當前時間是否有詢問，有的話將答案儲存起來 ```cpp= void traversal(int i, int l, int r){ if(l == r){ if(query[l]) ans[query[l]] = component_num; return; } for(pair<int, int> event : tree[i]) merge(event.first, event.second); int mid = (l+r)>>1; traversal(cl(i), l, mid); traversal(cr(i), mid+1, r); for(int i = 0; i < tree[i].size(); i++) undo(); } ``` ---- ### 複雜度 - 插入一個事件進線段樹上複雜度為 $O(\log n)$ - 合併為 $O(\log n)$ - 回復為 $O(1)$ - 遍歷線段樹為 $O(n+q)$ 總複雜度 $O(q\log n)$