Data Structure - HackMD

<style> .reveal .slides { text-align: left; font-size:28px; } </style> # Data Structure Introduction to Competitive Programming 3/22 ---- ## Outline - Binary Indexed Tree - Policy-Based Data Structures - cc_hash_table - gp_hash_table - tree - Treap --- ## Binary Indexed Tree (BIT) 又稱 Fenwick tree，樹狀數組 ---- ## 操作 - 計算動態前綴總和 (區間總和) - 動態單點更新似乎跟線段樹差不多? <span>- 查詢線段樹區間 [1..p] 總和</span> <span>- 更新線段樹位置 p 的值為 v</span> ---- | | Binary Indexed Tree | Segment Tree | | ---- | ------- | ----- | | 空間 | `N` :crown: | `4N` | | 常數 | 較小(迴圈) :crown: | 較大(遞迴) | | 實作量 | 較短(18行) :crown: | 較長(45行) | | 功能 | 只支援有「结合律且有逆運算」的操作(`+`vs`-`, `xor` vs `xor`) | 大部分動態區間問題都可以做 :crown: | ---- 長度為 $N$ 的序列，$Q$ 筆操作，每次為以下其中一種 : - 詢問序列前綴總和 ($[1..p]$ 的總和) - 單點更新 (修改位置 $p$ 的值為 $v$) ---- ## O(1) update, O(N) query - 詢問序列前綴總和 ( $[1..p]$ 的總和) - 單點更新 (修改位置 $p$ 的值為 $v$ ) <span>就是原題 ?</span> ![](https://i.imgur.com/62zCW2b.png =400x)  ---- ## O(N) update, O(1) query - 詢問序列前綴總和 ($[1..p]$ 的總和) $\to$ 輸出 prefix[p] - 單點更新 (修改位置 $p$ 的值為 $v$ ) $\to$ 更新從位置 p 到位置 n 的所有前綴總和 如果把序列改成儲存前綴總和 ? ---- 長度為 $N$ 的序列，$Q$ 筆操作，每次為以下其中一種 : - 詢問序列前綴總和 ($[1..p]$ 的總和) - 單點更新 (修改位置 $p$ 的值為 $v$) $1\le N, Q\le 10^5$ ~~O(1) update, O(N) query~~ ~~O(N) update, O(1) query~~ $\to$ TLE Binary Indexed Tree $\to O(\log N)$ update, $O(\log N)$ query ---- ## Binary Indexed Tree 想法求出前綴區間 a[1..7] 的總和為 $a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7$ 而如果已知 $a_{[1..4]}, a_{[5..6]}, a_{[7..7]}$ 的區間總和則只需要 3 次即可得到前綴區間 [1..7] 的總和 BIT 即為運用此想法在每次詢問時，只需查詢最多 $\log N$ 個區間降低複雜度 ---- ## BIT 結構 ![](https://i.imgur.com/YlOUTEr.png =500x) 第 2 個儲存的為 1-2 的總和第 4 個儲存的為 1-4 的總和第 6 個儲存的為 5-6 的總和第 8 個儲存的為 1-8 的總和第 10 個儲存的為 9-10 的總和其他第 $i$ 格儲存的為第 $i$ 格自己的值 ---- ## BIT 儲存區間 ![](https://i.imgur.com/YlOUTEr.png =500x) 第 $p$ 格儲存的區間長度為 $2^{trailing\ zero\ length}$ trailing zero length: 二進位結尾 0 的個數 $20$ 為例，換成二進位 101<span style="color:red">00</span>$_{2}$ 結尾 0 的個數為 $2\to 2^2 = 4$ $6$ 為例，換成二進位 11<span style="color:red">0</span>$_{2}$ 結尾 0 的個數為 $1\to 2^1 = 2$ $7$ 為例，換成二進位 111$_{2}$ 結尾 0 的個數為 $0\to 2^0 = 1$ ---- ## 求出前綴總和 ![](https://i.imgur.com/yFuFw9m.png =500x) 求出前綴區間 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]$ ---- ## 求出前綴總和 ![](https://i.imgur.com/NJthzyR.png =500x) 求出前綴區間 a[1..7] 從 7 開始， 7 儲存區間長度為 1$\to$ a[7..7] 得到 $a_{7}$，往前求出位置 6 儲存的總和 $\to$ a[5..6] 得到 $a_{[5..6]}$，往前求出位置 4 儲存的總和 $\to$ a[1..4] prefix$_{7} = a[1..4] + a[5..6] + a[7..7]$ ---- ## 實作求出前綴區間 [1..p] 的總和如何得到每個數字 $x$ 的儲存區間長度 ? ---- ## lowbit(x) 求出正整數 x 換成二進位最右邊的 1 的值 $20_{10}$為例，換成二進位 10<span style="color:red">100</span>$_{2}$ 最右側的 1 為的值為 $4_{10}$ $6_{10}$為例，換成二進位 1<span style="color:red">10</span>$_{2}$ 最右側的 1 為的值為 $2_{10}$ **lowbit(x) 即為當前位置 x 所儲存的區間長度** ---- ## 得到 lowbit(x) 根據位元運算的知識 lowbit(x) 可以透過 `x&-x` 得到因此我們可以在程式碼一開始把它 define 起來 ```cpp #define lowbit(x) (x&-x) ``` ---- ## query 實作 ![](https://i.imgur.com/yFuFw9m.png =500x) 知道當前位置 x 長度，即可每次加上當前位置的總和後從當前位置 x 跳到 x - lowbit(x) 的位置，直到 0 為止 11 為例， 11 - lowbit(11) = 11 - 1 $\to$ 10 10 - lowbit(10) = 10 - 2 $\to$ 8 8 - lowbit(8) = 8 - 8 $\to$ 0 ---- ## 程式碼 ```cpp= #define lowbit(x) (x&-x) long long query(int x){ long long ret = 0; while(x){ ret += bit[x]; x -= lowbit(x); } return ret; } ``` 複雜度 $O(\log N)$ ---- ## 求出區間總和 ? 可以在 $O(\log N)$ 得到前綴總和如果想得到區間 a[l..r] 的總和即為 a[1..r] 減去 a[1..l-1] 的總和因此直接 query(r) - query(l-1) 即可 ---- ## BIT 的性質 ![](https://i.imgur.com/YlOUTEr.png =500x) - BIT 是一個樹狀結構 - 每個位置都是一個節點 - 每個節點 x 的父節點 f[x]，x < f[x] - 從位置 x 往父節點一直往上走，所有祖先都會包括自己的值 ---- ## BIT 每個位置的父節點 ![](https://i.imgur.com/YlOUTEr.png =500x) 5 = 101$_{2}$，f[5] = 6 = 110$_{2}$ 12 = 1100$_{2}$，f[12] = 16 = 10000$_{2}$ x 的父節點的值為 x + lowbit(x) ---- ## 單點修改位置 $p$ 的值加值 $v$ ![](https://i.imgur.com/YlOUTEr.png =500x) 自己以及所有祖先節點的值都會被加值 ---- ## update 實作 1. 更新當前節點的值 2. 跳到父節點更新父節點的值 3. 直到超過範圍，或者回到第一步 ![](https://i.imgur.com/YlOUTEr.png =500x) ---- ## update code ```cpp= void update(int x, int v){ while(x <= n){ bit[x] += v; x += lowbit(x); } } ``` 複雜度 $O(\log N)$ ---- ## 完整程式碼 (感謝 Zihan 提供) ```cpp= #define lowbit(x) (x&-x) struct FenwickTree{ int n; vector<long long> bit; void init(int _n){ n = _n; bit = vector<long long>(n+1,0); } void update(int x,int v){ for(; x<=n; x+=lowbit(x)){ bit[x] += v; } } long long query(int x){ long long ret = 0; for(; x; x-=lowbit(x)){ ret += bit[x]; } return ret; } long long query(int l, int r){ return query(r) - query(l-1); } }BIT; int main(){ //example int n = 10; BIT.init(n); BIT.update(3, 10); cout << BIT.query(5) << endl; } ``` ---- 所以 BIT 支援單點修改，區間查詢反過來也可以做區間修改，單點查詢 ---- ## 裸題給長度為 $N$ 的序列，Q 筆詢問 1. 區間 [l, r] 加值 $v$ 2. 詢問位置 $p$ 的值 $N, Q\le 10^5$ BIT ? ---- 對於單點修改位置 $p$ 的值則位置 $p$, $p+1$, $p+2$..., $N-1$, $N$ 的前綴和都會被影響對於區間 [l, r] 加值 $v$ 對於 BIT 操作 update(l, v) update(r+1, -v) 即為前綴差分 ---- update(l, v) update(r+1, -v) 會被影響的前綴和為 l, l+1,..., r-1, r 這些區間的前綴和直接把這些前綴和當成序列來操作即可實現區間加值每次詢問位置 $p$ 的前綴和即為單點詢問位置 $p$ 的值 ---- ```cpp= void range_update(int l, int r, int v){ update(l, v); update(r+1, -v); } ``` ---- ## 再比較一次 | | Binary Indexed Tree | Segment Tree | | ---- | ------- | ----- | | 空間 | `N` :crown: | `4N` | | 複雜度 | $O(\log N)$ | $O(\log N)$ | 常數 | 較小(迴圈) :crown: | 較大(遞迴) | | 實作量 | 較短(18行) :crown: | 較長(45行) | | 功能 | 只支援有「结合律且有逆運算」的操作(`+`vs`-`, `xor` vs `xor`) | 大部分動態區間問題都可以做 :crown: | 只要不是區間修改+區間詢問，且结合律且有逆運算的操作通常都會寫 BIT ---- 看起來只需要兩分鐘，orZihan ![](https://i.imgur.com/0rBQdzp.png =600x) ---- 記得 BIT 一定要是 1-base，0 不具有 lowbit 由於 code 非常好記相信各位等等就可以背起來了 更新 += lowbit(x) 詢問 -= lowbit(x) ---- ## 逆序數對給定一個長度為 $n$ $(1 \le n \le 2 \cdot 10^5)$ 的序列 $a$$(-10^9 \le a_i \le 10^9)$，求有數列中有多少組逆序數對? 如果一組 $(i, j)$ 是逆序數對，則滿足以下公式 $1 \le i < j \le n，a[i] > a[j]$ ---- a = [4, 1, 3, 2, 5] 有四組逆序數對則其中 (4,1), (4,3), (4,2), (3,2) 為逆序數對 ---- ## 作法在每個位置儲存每個數字出現個數我們可以知道 BIT 可以算出前綴和 ---- 對於數字 `x` ，我們只需要 `query(x-1)` 即可得到所有小於 `x` 的數字有幾個 ---- 逆序數對數量，對於每個 `a[i]` 後面有幾個比 `a[i]` 小總和即為答案 a = [4, 1, 3, 2, 5] `a[0] (4)` 後面有 `3` 個比 `a[0]` 小 `a[1] (1)` 後面有 `0` 個比 `a[1]` 小 `a[2] (3)` 後面有 `1` 個比 `a[2]` 小 `a[3] (2)` 後面有 `0` 個比 `a[3]` 小 `a[4] (5)` 後面有 `0` 個比 `a[4]` 小 `3+0+1+0+0 = 4` ---- ## 作法一開始 BIT 內為空的從最後一項倒著做回來，依序詢問比自己小的數字個數詢問後把自己加進 BIT 裡 a = [4, 1, 3, 2, 5] num = [0, 0, 0, 0, 0] ```cpp ans += query(5-1); // +0 update(5); ``` ---- a = [4, 1, 3, 2, 5] num = [0, 0, 0, 0, 1] ```cpp ans += query(2-1); // +0 update(2); ``` ---- a = [4, 1, 3, 2, 5] num = [0, 1, 0, 0, 1] ```cpp ans += query(3-1); // +1 update(3); ``` ---- a = [4, 1, 3, 2, 5] num = [0, 1, 1, 0, 1] ```cpp ans += query(1-1); // +0 update(1); ``` ---- a = [4, 1, 3, 2, 5] num = [1, 1, 1, 0, 1] ```cpp ans += query(4-1); // +3 update(4); ``` ---- ## 複雜度 $N$ 個數字，每個數字花 $O(log N)$ 求小於自己的元素數量並更新總複雜度 $O(N\log N)$ ---- ## 離散化會發現數字範圍很大 $-10^9 \le a_i \le 10^9$ 但只會出現最多 $2\cdot 10^5$ 種數字把所有出現過的數字離散化即可做 ---- ```cpp= ind = a; sort(ind.begin(), ind.end()); ind.resize(unique(ind.begin(), ind.end()) - ind.begin()); for(int i = 0; i < n; i++){ a[i] = lower_bound(ind.begin(), ind.end(), a[i]) - ind.begin(); } ``` --- ## Policy-Base Data Structure (PBDS)(平板電視) - cc_hash_table - gp_hash_table - tree - ~~rope~~ - ~~priority_queue~~ ---- ## hash - cc_hash_table - gp_hash_table 類似 STL map 只是用 hash 實作(可能更快可能更慢，看資料大小與類型) 用法跟 map 差不多，但因為不是平衡樹沒有由小排到大的功能只能用來插入、刪除、查詢某個值存不存在或者key對應到的value是多少只有支援基本型態當key，如果使用pair或自己寫的struct需要自己寫hash function STL 也有內建的 hash map 叫 unordered_map ---- ## 用法需引入額外函式庫(不在 bits/stdc++.h 裡) ```#include <bits/extc++.h>``` 並且使用 namespace __gnu_pbds ```using namespace __gnu_pbds;``` ```cpp= #include <bits/extc++.h> using namespace __gnu_pbds; gp_hash_table<int, int> mp; cc_hash_bable<int, int> mp2; int main(){ mp[3] = 12; cout << mp.size() << endl; if(mp.find(123) == mp.end()){ cout << "Not found" << endl; } } ``` ---- ## 複雜度搜尋新增刪除等期望複雜度為 O(1)，但在資料量大的時候可能會變O(N) ### 測試速度比較 https://codeforces.com/blog/entry/60737 ---- ## 名次樹 Ordered Set : tree\<int, null_type, `less<int>`, rb_tree_tag, tree_order_statistics_node_update\>; Ordered Multiset : tree\<int, null_type, `less_queal<int>`, rb_tree_tag, tree_order_statistics_node_update\>; ---- ## 引入例題 [ZJ d794: 世界排名](https://zerojudge.tw/ShowProblem?problemid=d794) [ZJ d788: 排名順序](https://zerojudge.tw/ShowProblem?problemid=d788) $Q$ $( Q\le 10^5 )$ 筆操作，每次新增一個數字並輸出當前值是第幾大的? ---- 會發現內建函式 set/multiset 只能求出比當前元素大於等於當前的第一個元素 - lower_bound/ upper_bound 不能求出某個數字是第幾大的。 ---- 或者使用把所有數字離散化後，建立線段樹紀錄每種數字出現的個數，在線段樹上二分搜即可在 $O(\log N)$ 做到查詢元素是第幾大 ---- ## 名次樹在 $O(\log N)$ 求當前集合中第 $k$ 大的值，求當前值第幾大等功能用法跟 set 差不多，一樣會將元素由小到大照順序放 - insert(x) 插入元素 x - erase() 刪除元素 x - clear() 把整個容器清空 - find(x) 找尋 x 在容器中的位置 - find_by_order(k) 找出第 k 大的值的位置 - order_of_key(val) 找出 val 在容器中是第幾大 ---- ## sample code ```cpp= #include <bits/extc++.h> using namespace __gnu_pbds; tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> s; int main(){ // Insert some entries into s. s.insert(12); s.insert(505); // The order of the keys should be: 12, 505. assert(*s.find_by_order(0) == 12); assert(*s.find_by_order(3) == 505); // The order of the keys should be: 12, 505. assert(s.order_of_key(12) == 0); assert(s.order_of_key(505) == 1); // Erase an entry. s.erase(12); // The order of the keys should be: 505. assert(*s.find_by_order(0) == 505); // The order of the keys should be: 505. assert(s.order_of_key(505) == 0); cout << s.size() << endl; } ``` ---- 其中使用 less\<int\> 同樣值的元素只能只放一個 ```cpp= tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> s; ``` 如果想要放很多個則須改成 ```cpp= tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> s; ``` 如同 set 與 multiset 的差別 ---- ## 複雜度跟 set 的操作複雜度都一樣，$O(\log N)$ ### 測試速度比較 https://codeforces.com/blog/entry/11080 --- ## 樹堆 (Treap) Treap 是一顆平衡二元樹如 STL set 底層為紅黑樹實作出來的因此 Treap 也是用來儲存資料，並且處理內建資料結構無法處理的問題 ---- Treap = <span>binary tree(二元樹)</span> + heap(堆積) 兩種資料結構的合體 ---- ### Binary Search Tree 如下圖，每個節點會包括 value, left, right value: 當前節點儲存的值 left: 左子節點位置 right: 右子節點位置 ![](https://i.imgur.com/V0GFlz8.png =450x) ---- ### Binary Search Tree 性質 - 左子樹的所有節點值都小於等於自己 - 右子樹的所有節點值都大於等於自己 - 每個節點最多往下連兩個節點，也就是左右子節點 ![](https://i.imgur.com/zzHqILU.png =500x) ---- Treap = binary tree(二元樹) + <span>heap(堆積)</span> 兩種資料結構的合體 ---- ### Heap 如下圖，與線段樹相似，通常會用陣列實作每個位置會有一個值左子節點為當前位置 *2 右子節點為當前位置 *2+1 ![](https://i.imgur.com/Li6oNUu.png) ---- ### Heap 性質 - 整個子樹的值都小於等於自己 - 每個節點最多往下連兩個節點，也就是左右子節點 - Priority_queue 底層實作即為 Heap，每次取最小/大值 ![](https://i.imgur.com/Li6oNUu.png) ---- ### Treap Treap = binary tree(二元樹) + heap(堆積) 每個節點有兩個重要的值：key, priority ![](https://i.imgur.com/uoo0w5Y.png =500x) ---- ### Treap 結構 - key 符合 BST 的性質 - 左子樹的 key 都小於等於自己 - 右子樹的 key 都大於等於自己 - priority 符合 Heap 的性質 - 整棵子樹的 priroity 都小於等於自己 ![](https://i.imgur.com/uoo0w5Y.png =500x) ---- 使用指標實作 key 為儲存節點的值 priority 為隨機產生出來的值，用來維護 treap 的平衡 ```cpp= mt19937 gen(chrono::steady_clock::now().time_since_epoch().count()); // C++ randomizer struct Treap{ int key, pri, sz; //key, priority, size Treap *l, *r; //左右子樹 Treap(){} Treap(_key):key(_key), pri(gen()), sz(1){ l = r = nullptr; } }; ``` ---- Treap 滿足以下性質 1. 左子樹的 key 小於等於自己，右子樹的 key 大於等於自己 (tree) 2. 父節點的 priority 大於其子節點的 priority (heap) 3. 左右子樹也分別是一顆 Treap 4. 給定 $n$ 個節點的 key, priority 的大小關係，那麼這棵 Treap 的**形狀唯一** ---- ### 做法 Treap分為旋轉式跟非旋轉式這邊會介紹非旋轉式 Treap，也就是 merge- Treap 它易實作、期望複雜度好、靈活性高幾乎每個操作都是 $O(\log N)$ 而主要有兩個函式 --- split 跟 merge split 將一棵 Treap 分成兩顆 merge 將兩棵 Treap 合併成一棵 ---- 將根節點為 a 和根節點為 b 的 Treap 合併成一棵，並且回傳根節點位置 ```cpp Treap* merge(Treap *a,Treap *b){} ``` 將根節點為 x 的 Treap 分成兩棵 a, b，分成左邊那棵所有小於節點的值等於 k 右邊那棵所有節點的值大於 k ```cpp void splitByKey(Treap *x,int k,Treap*& a,Treap*& b){} ``` 將根節點為 x 的 Treap 分成兩棵 a, b，分成左邊那棵節點節點數量恰好為 k 右邊那棵節點數量為 n-k ```cpp void splitByKth(Treap *x,int k,Treap*& a,Treap*& b){} ``` ---- ### 建 Treap 一開始有 $N$ 個節點，如何把這 $N$ 個節點合併成一棵 Treap ? ![](https://i.imgur.com/4YoOQIm.png) ---- 單一節點也是一棵 Treap，符合所有 Treap 的性質因此要合併所有節點，等價於有 $N$ 棵 Treap 要合併成一棵使用 merge 函式合併 $N-1$ 次 ```cpp= int arr[MXN]; Treap *root = nullptr; void build(){ for(int i = 0; i < n; i++){ root = merge(root, new Treap(arr[i])); } } ``` 為了方便維護，要保證合併時左邊那棵 Treap 的 key 都小於等於右邊那棵因此建樹時會從 key 小的依序加入，以維護二元樹的性質 ---- <div style="position: absolute; right: 60%;"> 1. ![](https://i.imgur.com/1FlEIzc.png =300x190) 2. ![](https://i.imgur.com/5iUxt3z.png =300x190) </div> <div style="position: absolute; right: 20%;"> 3. ![](https://i.imgur.com/EJgD7KD.png =300x190) 4. ![](https://i.imgur.com/Ui6AWfs.png =300x190) </div> ---- ### merge 將兩棵 Treap 合併成一棵 Treap 保證合併時，左邊那棵 Treap 的 key 都小於等於右邊那棵的 value 否則會打亂二元樹的順序 ![](https://i.imgur.com/DBFLHnz.png =x190) $\to$ ![](https://i.imgur.com/Ui6AWfs.png =x190) ---- 合併時，priority 最大的必為根節點兩棵 Treap 其 priority 較大的為合併的根節點 ![](https://i.imgur.com/DBFLHnz.png =x190) $\to$ ![](https://i.imgur.com/Ui6AWfs.png =x190) 上圖為例，右邊那棵 priority 較大，為根節點 ---- 分成兩種 case 1. 左邊那棵為根節點根節點左子樹不會變 合併當前根節點右子樹&右邊那棵樹成為右子樹 2. <span>右邊那棵為根節點</span> 根節點右子樹不會變  合併當前根節點右子樹&右邊那棵樹成為左子樹  <div style="position: absolute; right: 0%; top:-15%;"> ![](https://i.imgur.com/DBFLHnz.png =x190) </div> ---- 繼續合併子樹? 使用遞迴 ! ![](https://i.imgur.com/MNCrWhQ.png) 合併 3 為根節點的 Terap 與 5 為根節點的 Treap 3 為根節點的 Treap 其 priority 比較大為根節點 ---- 分成兩種 case 1. <span>左邊那棵為根節點</span> 根節點左子樹不會變合併當前根節點右子樹&右邊那棵樹成為右子樹 2. 右邊那棵為根節點根節點右子樹不會變合併當前根節點右子樹&右邊那棵樹成為左子樹 <div style="position: absolute; right: -5%; top:10%;"> ![](https://i.imgur.com/60EDi1z.png) </div> ---- 根節點左子樹不會變合併當前根節點右子樹 & 右邊那棵樹 ![](https://i.imgur.com/60EDi1z.png) 這時發現當前根節點右子樹為空 $\to$ 直接把右邊那棵樹當成右子節點，遞迴結束 ! ---- ## 步驟 1. 挑選 priority 較大的當成根節點，分成兩種 case: 1. 左邊那棵為根節點根節點左子樹不會變合併當前根節點右子樹&右邊那棵樹成為右子樹 2. 右邊那棵為根節點根節點右子樹不會變合併當前根節點右子樹&右邊那棵樹成為左子樹 2. 遞迴下去繼續合併 3. 直到要合併的兩棵 Treap 中，其中一棵為空為止 ---- ## pull() 函式每次更新 Treap 後，要記得維護 Treap 的子樹大小把他寫在 pull 函式裡 ```cpp= int Size(Treap *x){ return x ? x->sz : 0; } void pull(Treap *x){ x->sz = Size(x->l) + Size(l->r) + 1; } ``` 自己的大小 = 左子樹大小 + 自己 + 右子樹大小記得求左右子樹大小時要先記得判斷是否存在，否則存取到空指標會造成 Runtime-error ---- ## 範例程式碼 ```cpp= Treap* merge(Treap *a,Treap *b){ if(!a || !b) return a ? a : b; //其中一棵 Treap 為空則回傳另一個當成根 if(a->pri > b->pri){ //如果 a 的 pri 比較大則 a 為合併的根節點 a->r = merge(a->r,b); //將 a 的右子樹跟 b 合併 pull(a); return a; } else{ //如果 b 的 pri 比較大則 b 為合併的根節點 b->l = merge(a,b->l); //將 b 的左子樹跟 a 合併 pull(b); return b; } } ``` ---- ## 複雜度一直往下遞迴合併，直到其中一棵 Treap 到最底部因此複雜度為 $O(樹高)$ ---- ### split 將一棵Treap分成兩棵 - <span>split by key</span> key 小於等於 k 的分到左邊那棵 Treap a，其他分到右邊那棵 Treap b - split by k-th 左邊那棵 Treap a 的節點數有 k 個，右邊那棵 Treap b 節點數為 n-k 個用途：集合中有幾個值為 k 的元素、刪除所有值在 $[l, r]$ 區間內的所有元素 ---- ### split by key Treap 滿足二元樹的性質，左子樹 <= 自己，右子樹 >= 自己要分成 $\le k$ 以及 $> k$ 的兩棵 Treap 一樣使用遞迴實做 ---- 從根節點開始，判斷根節點是否 $\le k$ 如果$\le k$，則根節點會分到左邊那棵 Treap，左子樹也是而右子節點可能會有值 $> k$ ，分到右邊那棵 Treap ，因此繼續往右遞迴如果大於則分到右邊，遞迴左子樹直到遞迴到最深為止 ---- ### 實作把 Treap x 分成兩堆 a ($\le k$), b ($> k$) ```cpp= void splitByKey(Treap *x,int k,Treap*& a,Treap*& b){ if(!x){ a = b = nullptr; } // 遞迴到最深結束遞迴 else if(x->val<=k){ // 當前節點以及左子樹屬於左邊那棵 a a = x; splitByKey(x->r, k, a->r, b); // 遞迴右子樹 pull(a); // 更新子樹大小 } else{ // 當前節點以及右子樹屬於右邊那棵 b b = x; splitByKey(x->l, k, a, b->l); // 遞迴左子樹 pull(b); // 更新子樹大小 } } ``` ---- ### split by size 把當前這棵 Treap 分成兩棵 a, b 左邊那棵 Treap a 的節點數有 k 個，右邊那棵 Treap b 節點數為 n-k 個用途：求出第 k 小元素，刪除第 l 大到第 r 大的所有元素等等 ---- 這時會發現我們維護 Treap 的子樹大小之前都沒用到現在可以終於有用了 split by key 每次判斷自己是否小於等於 key split by size 則是判斷自己是否在左半 (前 k 小) ---- 從根節點開始，判斷根節點是否自己加上左子數數量 $\le k$ 如果$\le k$，則根節點會分到左邊那棵 Treap，左子樹也是而自己+左子數數量可能不足 k 個，因此繼續往右遞迴，找到 k 個如果大於則分到右邊，遞迴左子樹直到遞迴到最深為止 ---- - 自己為前 k 個 $\to$ 往右遞迴，並且扣掉自己以及左子樹數量 - 自己為大於 k 個 $\to$ 往左遞迴，找出前 $k$ 個 ```cpp= int Size(Treap *x){ return x ? x->sz : 0; } void splitByKth(Treap *x,int k,Treap*& a,Treap*& b){ if(!x){ a = b = nullptr; } //遞迴到最深為止 else if(Size(x->l) + 1 <= k){ a = x; //如果左子樹+自己的 size 小於等於 k 則左子樹跟自己為k個以內 splitByKth(x->r, k - Size(x->l) - 1, a->r, b); pull(a); // 記得每次都要更新子樹大小 } else{ b = x; //如果左子樹+自己的size大於k個則右子樹跟自己會分到右邊 splitByKth(x->l, k, a, b->l); pull(b); // 記得每次都要更新子樹大小 } } ``` ---- 有以上 split 跟 merge 操作之後就可以完成大部分了! 像是插入元素或刪除都是在 split 和 merge 的基礎下操作 (記得左右順序要處理好!) - insert(x) - erase(x) ---- ### insert(x) 新增一個大小為 $x$ 的元素放到 Treap 裡 ---- 因此要把原本的 Treap 與新的元素 merge 起來但會是好的嗎 ? ---- Treap *merge(Treap *a, Treap *b){} 需要保證合併左邊那棵 Treap a 所有元素小於等於 Treap b 因此不能直接合併 ---- 在新增大小為 x 的元素時需要先把 Treap 分成兩半，一半小於等於 x，一半大於 x 如此以來即可使用 merge 函數合併 ```cpp= void insert(int x){ Treap *left, *right; splitByKey(root, x, left, right); root = merge(left, merge(new Treap(x), right)); } ``` ---- ### erase(x) Treap 中刪除一個值為 $x$ 的元素 ---- 一樣使用 split & merge 函數即可完成 1. splitByKey 分成兩堆 Treap l (<= x) 以及 Treap r (> x) 的 2. splitByKey 把 l 再分成兩堆 Treap l (< x) 以及 Treap m (= x) 的這時我們就有三個樹堆 < x, = x, > x 如果要刪除全部值為 x 的元素，則直接 root = merge(l, r) 只刪除一個值為 x 的元素用以下寫法，合併 l (< x), r(> x), m 的左右子樹即為只刪除一個元素而已 root = merge(merge(l, merge(m->l, m->r)), r) ---- ```cpp= void erase(int val){ //移除一個值為 val 的元素 Treap *l, *mid, *r; splitByKey(root, val, l, r); //把小於等於 val 的丟到 l splitByKey(l, val-1, l, mid); //小於val的丟到 l, 等於 val 的就會在 mid 裡 root = merge(merge(l, merge(m->l, m->r)), r); //將除了節點 m 以外的合併 } ``` ---- ### 使用 Treap 處理序列問題給定一個長度為 N 的序列，共有 Q 筆操作，每筆操作可能是 - 修改第 i 個位置的值成 x - 求 [L, R] 區間內的最小值 $1\le N, Q\le 2 \cdot 10^5$ ---- 原本使用 key (由左到右 key 的值遞增) 來維護二元樹的性質要處理區間問題則改成序列的 index 順序來維護並且需要多一個變數 mn 儲存區間內(整棵子樹) 的最小值 ![](https://i.imgur.com/69aqZKB.png =500x) ---- 建構記得把自己設為最小值 ```cpp= struct Treap{ int key, pri, sz, mn; //key, priority, size Treap *l, *r; //左右子樹 Treap(){} Treap(_key):key(_key), mn(_key), pri(gen()), sz(1){ l = r = nullptr; } }; ``` ---- 更新節點除了更新子樹大小多維護一個子樹區間的最小值左右子樹最小值以及自己的值取 min ```cpp= int Size(Treap *x){ return x ? x->sz : 0; } int getMn(Treap *x){ return x ? x->mn : 0; } void pull(Treap *x){ x->sz = Size(x->l) + Size(x->r) + 1; x->mn = min(min(getMn(x->l), getMn(x->r)), x->key); } ``` ---- ## 序列建立 Treap 原本的 Treap 是由 key 小到大序列則是由 index 小到大 ```cpp= int arr[MXN]; Treap *root = nullptr; for(int i = 0; i < n; i++){ root = merge(root, Treap(arr[i])); } ``` ---- ### 修改第 i 個位置的值成 x 使用 split by size 與 merge 先把第 i 個位置拉出來 ```cpp= Treap *l, *m *r; splitByKth(root, i, l, r); splitByKth(l, i-1, l, m); ``` 存在 m 裡面，接著把 m->val, m->mn 都改成新的值並且存回去 ```cpp= m->val = m->mn = newValue; root = merge(l, merge(m, r)); ``` ---- ### 求 [L, R] 區間內的最小值一樣，先把 [L, R] 的區間拉出來，要修改/詢問哪裡就 split 哪裡 ```cpp= Treap *l, *m *r; splitByKth(root, R, l, r); splitByKth(l, L-1, l, m); cout << m->mn << endl; ``` 接著合併回去 ```cpp= root = merge(l, merge(m, r)); ``` ---- ## 懶人標記把單點修改變成區間修改 - 將 [L, R] 區間內的值加上 x - 求 [L, R] 區間的值總和 ---- 做法與線段樹差不多，多紀錄一個懶人標記在要修改的 Treap 區間打上標記 ```cpp= Treap *l, *m *r; splitByKth(root, R, l, r); splitByKth(l, L-1, l, m); m->tag += v; root = merge(l, merge(m, r)); ``` ---- 之後走到更新節點資訊，並且往下推包成 push 函式 ```cpp= void push(Treap *x){ if(x->tag){ x->key += x->sz * x->tag; if(x->l) x->l->tag += x->tag; if(x->r) x->r->tag += x->tag; x->tag = 0; } } ``` ---- 每次操作經過的節點，順便更新懶人標記並往下推 ```cpp= Treap* merge( Treap *a , Treap *b ){ if( !a || !b ) return a ? a : b; if( a->pri > b->pri ){ push( a ); a->r = merge( a->r , b ); pull( a ); return a; }else{ push( b ); b->l = merge( a , b->l ); pull( b ); return b; } ``` ---- 每次操作經過的節點，順便更新懶人標記並往下推 ```cpp= void splitByKey(Treap *x,int k,Treap*& a,Treap*& b){ if(!x){ a = b = nullptr; return; } push(x); if(k<=x->val){ b = x; split_key(x->l,k,a,b->l); pull(b); } else{ a = x; split_key(x->r,k,a->r,b); pull(a); } } ``` ---- ### [區間移動](https://cses.fi/problemset/task/2072) 給一個長度為 $N$ 的序列，$Q$ 筆操作每次選一段區間剪下移動到序列的最後面，求出做完所有操作後序列長怎樣 - $N, Q\le 2\cdot 10^5$ ---- 相信看完前面的例題後，本題就非常簡單直接把翻轉區間 [l, r] 使用 split 函式拉出來然後交換位置即可 ---- 把序列分成三段 [1, l-1], [l, r], [r+1, n] 然後把中間跟後面那段交換位置即可 ```cpp= void cutAndPaste(int ql, int qr){ Treap *l, *m, *r; splitByKth(root, qr, l, r); splitByKth(l, ql-1, l, m); root = merge(l, merge(r, m)); } ``` ---- ### [區間反轉](https://cses.fi/problemset/task/2074/) - 將 [L, R] 區間內的元素反轉, a[L] 與 a[R] 交換, a[L+1] 與 a[R-1] 交換... - 求 [L, R] 區間的值總和 ---- 如何使用 Treap ? 一樣先把區間 [L, R] 的 Treap 拆出來把這個區間的 Treap 每個節點左右子樹交換即可翻轉整個區間 ![](https://i.imgur.com/MBH3tKB.png =450x) $\to$ ![](https://i.imgur.com/qtnkcmh.png =450x) ---- 但如果每次翻轉操作都暴力轉好，複雜度為 $O(N)$ 一樣使用懶人標記，每次把這段區間的根節點打上標記即可做到均攤 $O(\log N)$ ---- 使用變數 rev_tag 紀錄是否反轉這棵 Treap ```cpp= struct Treap{ int key, pri, sz, rev_tag; //key, priority, size Treap *l, *r; //左右子樹 Treap(){} Treap(_key):key(_key), pri(gen()), sz(1), rev_tag(0){ l = r = nullptr; } }; void push(Treap *x){ if(x->rev_tag){ swap(x->l, x->r); if(x->l) x->l->rev_tag ^= 1; if(x->r) x->r->rev_tag ^= 1; x->rev_tag = 0; } } ``` ---- ## 複雜度分析單次操作複雜度為樹的高度在使用 random 產生的 priority 下，期望複雜度為 $O(\log N)$ | build | split | merge | | --------- | -------- | -------- | | $O(NlgN)$ | $O(lgN)$ | $O(lgN)$ | 但由於是 random 的產出的 Treap 有時可能走到深度較深的節點，加上使用遞迴因此常數很大一般的區間加值/詢問建議還是使用線段樹只需求出第 k 大、當前元素是第幾大等等，使用內建資料結構排名樹其他需要區間反轉、把序列整個區間移動位置等等才會用到 Treap  --- ### Next Week: Mock Contest 2 Topic: Number Theory, DS(Segment Tree, BIT, Treap), D&C Time : 3/29 18:30-21:30 You can carry the following items: - at most 25 A4 single pages codebook - Dictionary - Stationary - Mascot ---- ### Homework and Practice deadline: 3/29 link: https://vjudge.net/contest/548434 challenge: https://codeforces.com/gym/102787