<style> .reveal .slides { text-align: left; font-size:30px } </style> ## 樹堆 (Treap) Treap 是一顆平衡二元樹 如 STL set 底層為紅黑樹實作出來的 因此 Treap 也是用來儲存資料，並且處理內建資料結構無法處理的問題 ---- Treap = <span><!-- .element: class="fragment highlight-red" -->binary search tree(二元搜尋樹)</span> + heap(堆積) 兩種資料結構的合體 ---- ### Binary Search Tree 如下圖，每個節點會包括 value, left, right value: 當前節點儲存的值 left: 左子節點位置 right: 右子節點位置  ---- ### Binary Search Tree 性質 - 左子樹的所有節點值都小於等於自己 - 右子樹的所有節點值都大於等於自己 - 每個節點最多往下連兩個節點，也就是左右子節點  ---- Treap = binary search tree(二元搜尋樹) + <span><!-- .element: class="fragment highlight-red" -->heap(堆積)</span> 兩種資料結構的合體 ---- ### Heap 每個位置會有一個值 左子節點為當前位置 *2 右子節點為當前位置 *2+1  ---- ### Heap 性質 - 整個子樹的值都小於等於自己 - 每個節點最多往下連兩個節點，也就是左右子節點 - Priority_queue 底層實作即為 Heap，每次取最小/大值  ---- ### Treap Treap = binary search tree(二元搜尋樹) + heap(堆積) 每個節點有兩個重要的值：key, priority  ---- ### Treap 結構 - key 符合 BST 的性質 - 左子樹的 key 都小於等於自己 - 右子樹的 key 都大於等於自己 - priority 符合 Heap 的性質 - 整棵子樹的 priroity 都小於等於自己  ---- 使用指標實作 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 大於等於自己 (BST) 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 ?  ---- 單一節點也是一棵 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.  2.  </div> <div style="position: absolute; right: 20%;"> 3.  4.  </div> ---- ### merge 將兩棵 Treap 合併成一棵 Treap 保證合併時，左邊那棵 Treap 的 key 都小於等於右邊那棵的 value 否則會打亂二元樹的順序  $\to$  ---- 合併時，priority 最大的必為根節點 兩棵 Treap 其 priority 較大的為合併的根節點  $\to$  上圖為例，右邊那棵 priority 較大，為根節點 ---- 分成兩種 case 1. 左邊那棵為根節點 根節點左子樹不會變<!-- .element: class="fragment" data-fragment-index="1" --> 合併當前根節點右子樹&右邊那棵樹成為右子樹<!-- .element: class="fragment" data-fragment-index="2" --> 2. <span><!-- .element: class="fragment highlight-red" -->右邊那棵為根節點</span> 根節點右子樹不會變 <!-- .element: class="fragment" data-fragment-index="1" --> 合併當前根節點右子樹&右邊那棵樹成為左子樹 <!-- .element: class="fragment" data-fragment-index="2" --> <div style="position: absolute; right: 0%; top:-15%;">  </div> ---- 繼續合併子樹? 使用遞迴 !  合併 3 為根節點的 Terap 與 5 為根節點的 Treap 3 為根節點的 Treap 其 priority 比較大為根節點 ---- 分成兩種 case 1. <span><!-- .element: class="fragment highlight-red" -->左邊那棵為根節點</span> 根節點左子樹不會變 合併當前根節點右子樹&右邊那棵樹成為右子樹 2. 右邊那棵為根節點 根節點右子樹不會變 合併當前根節點右子樹&右邊那棵樹成為左子樹 <div style="position: absolute; right: -5%; top:10%;">  </div> ---- 根節點左子樹不會變 合併當前根節點右子樹 & 右邊那棵樹  這時發現當前根節點右子樹為空 $\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><!-- .element: class="fragment highlight-red" -->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 儲存區間內(整棵子樹) 的最小值  ---- 建構記得把自己設為最小值 ```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 每個節點左右子樹交換 即可翻轉整個區間  $\to$  ---- 但如果每次翻轉操作都暴力轉好，複雜度為 $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 <!-- [sample code](https://github.com/jakao0907/contest/blob/master/dataStructure/treap_split_key%26kth.cpp) -->