# 樹堆(Treap) Treap 是一個隨機平衡的二元搜尋樹，這裡所說的 Treap 是以 merge/split 的方式實作的，這樣實作的 Treap 有很多好處，我們先說明他的基本規則，以及 merge/split 函式(function)在做什麼，接著說明如何實作。 樹堆的名稱來由是 樹(Tree) 和 堆積(Heap) 結合而成，每個節點會至少存放兩個數值 val,pri ， val (也有人叫他 key)就是內容，而 pri 則是用以平衡。 ## 規則與前置作業 - 所有節點的 pri 值必須比他的左右子樹小(大也可以) - 樹上的 val 滿足 $``二元搜尋樹"$ 的性質 為了避免有人忘記什麼是 $"二元搜尋樹"$ 的性質，以下用一個我出過的題目說明。 ### Safe Sorter <img src="https://live.staticflickr.com/65535/51821755725_f3cbcbed1f_o.png" width="714" height="579" alt="pic"> - 如果該節點還沒有任何保險箱，此保險箱就會佔據該節點 - 否則若這個要放入的保險箱裡面的金塊比在該節點的保險箱還要多，他會被往右邊送 - 否則就往左邊送 - 必須送到他占用一個節點為止 以上圖為例 - 第一個放進來的保險箱有 8 個金塊 - 第二個有 10 個，因此他被放在右邊 - 第三個有 14 個，因此第一步會先往右送，發現右邊的節點也有保險箱了，因而再次被往右送 - 第四個有 3 個，於是被放在左邊 - 其他依此類推 而所謂隨機平衡就是他的平衡方式來自所有節點被賦予的一個隨機的 pri 值。 --- Treap 當中最重要的就是以下兩種操作 - merge(a,b) : 將兩顆樹 a, b 合併。前提 : a, b 滿足所有在 a 裡面的節點所存放的值皆小於所有在 b 裡面的節點 - split(a,b,p) : 將一棵樹分成 a, b 並同時滿足 a 中的值皆小於等於 $(\le)$ p ， 而 b 中的值皆大於 $(>)$ p 兩者詳細步驟是依照遞迴定義的，如下。 ### Merge - 如果 a,b 至少其中一個是空指標，回傳非空的那一個 (兩個都空救回傳空指標) - 否則為了同時維持 BST 和 heap 的性質，我們先判斷哪一個的 pri(priority) 值更大，我的實作是將 pri 值小的放上面 (較接近樹根的位置) - 如果 a 的 pri 值較小，我們會回傳 a 作為呼叫此函數的樹的根，不過在此之前，我們要先決定 a 的右子樹 (因為 b 也還沒被合併完) ，所以要向下遞迴 - b 的情況剛好相反，因為 b 裡面的值都大於 a 裡面的值 #### 實作 ```cpp= node *merge(node *a,node *b){ if(!a || !b) return a ? a : b; if(a->pri < b->pri){ a->rch=merge(a->rch,b); return a; }else{ b->lch=merge(a,b->lch); return b; } } ``` ### Split split 較為複雜，因為同時要滿足 Treap 的兩種性質 - 若 T(要被分割的 Treap) 為空指標的話，代表整棵樹都被分完了，因此將 a,b 都設為空指標。 - 否則一樣要分成兩個條件 : T 的根結點的值小於等於 p ，和大於 p - 如果 T 的根結點的值小於等於 p ，選擇將 T 的根結點與他的左子樹給 a 並繼續向下分解 T 的右子樹給 a 的右子樹與 b - 否則將 T 的根結點與他的右子樹給 b 並繼續向下分解 T 的左子樹給 b 的左子樹與 a #### 實作 ```cpp= void split(node *T,node *&a,node *&b,int p){ if(!T){ a=b=nullptr; return; } if(T->key <= p){ a=T; split(T->rch,a->rch,b,p); }else{ b=T; split(T->lch,a,b->lch,p); } } ``` ### 名次樹 首先介紹一下名次樹，名次樹是透過在節點內多存一個數值 $\to$ 子樹大小(size)，以實現更多功能，例如 : k 在這棵樹裡面排第幾，刪除比 k 大的第一個數，還有排名第 k 的樹為何等。 為了在 Treap 中實現這個功能，我們要多實作兩個函數 $\to$ pull & SplitBySize(splitSz)。 首先，我先將節點完整的 struct ，還有尋找某個指標底下的樹的 size 的函式寫出來，方便後續講解。順帶一題，為了維持名次樹的正確性，每次只要樹有經過更動就要 執行 pull 。 ```cpp= struct node{ // key 是排序依據 // pri 是 heap 的依據 int key,pri,sz; node *lch,*rch; node(int _key){ key=_key; sz=1; lch=rch=nullptr; // RandomInt() 之後會實作 pri=RandomInt(); } void pull(){ // 自己也算 sz=1; // 判斷式相當於 lch!=nullptr // 要加上左右子樹的大小才是完整的 if(lch) sz+=lch->sz; if(rch) sz+=rch->sz; } }; int fs(node *a){ // 如果 a 為空指標則 sz(回傳值) 為 0 return a ? a->sz : 0; } ``` ### SplitBySize 這個函式會與 Split 有點像，差別在於分開的依據不同， SplitBySize 會將整棵樹分為 a, b ， 其中 a 存有前 s 小的所有數， b 則存剩下的。詳細步驟如下。 - 與 Split 相同，若 T 為空則表示分完，將 a,b 都設為空指標 - 否則如果 T 的左子樹的元素個數不到 s ，將 T 和他的左子樹都給 a ，然後繼續從 T 的右子樹當中切出 s-( T 的左子樹大小)-1( T 自己) 個元素給 a 的右子樹 - 否則將 T 和他的右子樹都給 b ，然後從 T 的左子樹當中切出 s 個元素給 a #### 實作 ```cpp= void splitSz(node *T,node *&a,node *&b,int s){ if(!T){ a=b=nullptr; return; } if(fs(T->lch)<s){ a=T; splitSz(T->rch,a->rch,b,s-fs(T->lch)-1); // 普通的 Split 中放 pull 的位置與他相同 a->pull(); }else{ b=T; splitSz(T->lch,a,b->lch,s); b->pull(); } } ``` ### 隨機數 C++ 本身就有內建隨機函式可供取用。就直接放在下面供大家參考。 ```cpp= // 簡單作法，但可能被 hack #include<crand> int RandomInt(){ return rand(); } ``` ```cpp= // 較長，但較不易被破解 #include<random> unsigned seed=chrono::steady_clock().now().time_since_epoch().count(); mt19937 rng(seed); int RandomInt(){ return rng(); } ``` ## 基本功能 有了這些函式之後，後面的大多數操作都會變很簡單，舉凡插入(insert)，刪除(erase)，尋找(find) 等等。因為他們都可以用 merge and split 湊出來。而且很多功能甚至不只有一種實作方法。讓我們看下去。 ### Insert insert 可以被簡單地分成幾個步驟。假設我要插入的數字為 v 。 - 將整棵樹(我都存在 rt 指標中) 切成小於等於 v 和大於 v 的兩棵樹 rt, b - 另外用 v new 一個節點 a(v) 出來 (不會動態記憶體分配的可以先去複習一下)。 - 合併 rt 和 a ，並將合併後的樹給 rt - 合併 rt 和 b ，並將合併後的樹給 rt #### 實作 ```cpp= void insert(int v){ node *a=new node(v),*b; split(rt,rt,b,v); rt=merge(rt,a); rt=merge(rt,b); } ``` ### Erase Erase 一樣可以被簡單地分成幾個步驟。假設我要刪除的數字為 v 。 #### 1. 刪除所有等於 v 的數(整數才可以) - 將整棵樹(我都存在 rt 指標中) 切成小於等於 v 和大於 v 的兩棵樹 rt, b - 再將 rt 指向的樹切成小於等於 v-1 和大於 v-1 的兩棵樹 rt, a - 刪除 a 整棵樹 - 合併 rt 和 b ，並將合併後的樹給 rt #### 2. 刪除一個等於 v 的數(整數才可以) - 將整棵樹(我都存在 rt 指標中) 切成小於等於 v-1 和大於 v-1 的兩棵樹 rt, b - 再將 b 指向的樹切成左邊一個元素，剩下都放右邊的 b, a - 刪除 b - 合併 rt 和 b ，並將合併後的樹給 rt #### 實作 ```cpp= // 這個函式是先刪除左右子樹，再刪除自己，並透過遞迴來刪掉整棵樹。 void delete_tree(node *n){ if(n->lch) delete_tree(n->lch); if(n->rch) delete_tree(n->rch); delete(n); } // erase all element between (v-1~v] -> 對應 1 void erase(int v){ node *a,*b; split(rt,rt,b,v); split(rt,rt,a,v-1);// or v-eps // it's better to use delete_tree function delete(a); rt=merge(rt,b); } // erase one element between (v-1~v] -> 對應 2 void erase(int v){ node *a,*b; split(rt,rt,b,v-1); splitSz(b,b,a,1); delete(b); rt=merge(rt,b); } ``` ### Count Count 還是可以被簡單地分成幾個步驟。假設我要數的數字為 v 。 - 將整棵樹(我都存在 rt 指標中) 切成小於等於 v 和大於 v 的兩棵樹 rt, b - 再將 rt 指向的樹切成小於等於 v-1 和大於 v-1 的兩棵樹 rt, a - 用一個變數將 a 的 size 存起來 - 合併 rt 和 a ，並將合併後的樹給 rt - 合併 rt 和 b ，並將合併後的樹給 rt #### 實作 ```cpp= int count(int v){ node *a,*b; split(rt,rt,b,v); split(rt,rt,a,v-1);// or v-eps int ret=fs(a); rt=merge(rt,a); rt=merge(rt,b); return ret; } ``` ### Kth Small Element 假設我要找第 p 小的數字。 - 將整棵樹(我都存在 rt 指標中) 切成左邊 p 個元素，剩下都放右邊的 rt, b - 再將 rt 指向的樹切成左邊 p-1 個元素，剩下都放右邊的 rt, a - 用一個變數將 a 的值存起來 - 合併 rt 和 a ，並將合併後的樹給 rt - 合併 rt 和 b ，並將合併後的樹給 rt #### 實作 ```cpp= int kth(int v){ node *a,*b; splitSz(rt,rt,b,p); splitSz(rt,rt,a,p-1); int ret=a->key; rt=merge(rt,a); rt=merge(rt,b); return ret; } ``` > [color=blue]你以為只是平衡樹嗎？不不不，祂可厲害了 ## 進階功能 如果我們將整棵樹的中序遍歷當成序列的順序的話(如下圖)，我們可以實現需多更強大的功能。可以說，線段樹能做到的事 Treap 都可以做到，但 Treap 甚至可以做到許多線段樹做不到的事。 <img src="https://live.staticflickr.com/65535/51903502674_6ba5e3979e_o.png" width="769" height="722" alt="Treap"> 而且，此時我們可以把 key 拔掉。然後只使用 splitSz 和 merge 。 ### Insert 假設我希望插入的數字位於第 p 個，且值為 v 。 - 將整棵樹(我都存在 rt 指標中) 切 p-1 個給 rt ，其他剩下的分給 b - 另外用 v new 一個節點 a(v) 出來 - 合併 rt 和 a ，並將合併後的樹給 rt - 合並 rt 和 b ，並將合併後的樹給 rt #### 實作 ```cpp= void insert(int p,int v){ node *a=new node(v),*b; splitSz(rt,rt,b,p-1); rt=merge(rt,a); rt=merge(rt,b); } ``` ### Erase 假設我要刪除第 p 個數 - 將整棵樹(我都存在 rt 指標中) 切 p-1 個給 rt ，其他給 b - 再將 b 指向的樹切一個給 b 剩下給 a - 刪除 a - 合併 rt 和 b ，並將合併後的樹給 rt #### 實作 ```cpp= void erase(int p){ node *a,*b; splitSz(rt,rt,b,p-1); splitSz(b,b,a,1); delete(b); rt=merge(rt,b); } ``` ### 區間操作 在介紹區間操作之前，我們還需要在節點上加入更多的資訊和函式，所以 node 裡面會有更多程式碼。 ```cpp= const int INF=0x3f3f3f3f struct Treap{ struct node{ // 此節點的值 int val; // 維持 Treap 的性質 int pri,sz; // 用在區間查詢 int sum,mx,mn; // 可以支援區間反轉 bool rev_tag; // 可以支援區間加值 int add_tag; // 左右子樹 node *lch,*rch; node(int _val){ val=sum=mx=mn=_val; lch=rch=nullptr; sz=1; pri=rng(); } void pull(){ sz=1; sum=mx=mn=val; if(lch){ sz+=lch->sz; sum+=lch->sum; mx=max(mx,lch->mx); mn=min(mn,lch->mn); } if(rch){ sz+=rch->sz; sum+=rch->sum; mx=max(mx,rch->mx); mn=min(mn,rch->mn); } } // 讓他底下的區間都反轉 void rev(){ rev_tag=!rev_tag; } // 再更改節點前用 void push(){ if(rev_tag){ swap(lch,rch); if(lch) lch->tag=true; if(rch) rch->tag=true; } if(lch) lch->add_tag+=add_tag; if(rch) rch->add_tag+=add_tag; add_tag=0; } }; }; ``` 同時，我們在原來的 merge/split 操作程式碼中，都要加上 push ，具體位置如下 ```cpp= struct Treap{ node *merge(node *a,node *b){ if(!a || !b) return a ? a : b; if(a->pri < b->pri){ a->push(); a->rch=merge(a->rch,b); return a; }else{ b->push(); b->lch=merge(a,b->lch); return b; } } void splitSz(node *T,node *&a,node *&b,int s){ if(!T){ a=b=nullptr; return; } T->push(); if(fs(T->lch)<s){ a=T; splitSz(T->rch,a->rch,b,s-fs(T->lch)-1); a->pull(); }else{ b=T; splitSz(T->lch,a,b->lch,s); b->pull(); } } }; ``` 接下來的操作都是把區間切下來，做完我要做的事，再接回去就可以了。 ### 區間查詢(極值、總和) 假設現在要查詢 l~r 的區間 - 從 rt 切下 r 個節點給 rt ，其它給 b - 接著從 rt 切下 l-1 個節點給 rt ，其餘給 a - 此時 a 就存有區間 $[ \; l, \, r \; ]$ ，而他上面的 sum, mx, mn 就會是這個區間的總和、最大值，以及最小值 - 最後先按照順序把它合併，再回傳答案即可 #### 實作 ```cpp= int query(int l,int r){ node *a,*b; splitSz(rt,rt,b,r); splitSz(rt,rt,a,l-1); // 下一行放 sum, mx, mn 看需求 int ret=a->sum; rt=merge(rt,a); rt=merge(rt,b); return ret; } // 單點查詢就用查詢長度為 1 的區間重復利用函式就可以了 int get(int p){ return query(p,p); } ``` ### 單點修改 先將所要修改的位置切下來，在修改完後記得要 push 。 ```cpp= void modify(int p,int v){ node *a,*b; splitSz(rt,rt,a,p-1); splitSz(a,a,b,1); a->val=v; rt=merge(rt,a); rt=merge(rt,b); } ``` ### 區間操作 假設現在要對 l~r 的區間進行操作 - 從 rt 切下 r 個節點給 rt ，其它給 b - 接著從 rt 切下 l-1 個節點給 rt ，其餘給 a - 此時 a 就存有區間 $[ \; l, \, r \; ]$ ，直接對他操作就可以了 - 最後先按照順序把它合併 #### 實作 ```cpp= // 區間反轉 void reverse(int l,int r){ node *a,*b; splitSz(rt,rt,b,r); splitSz(rt,rt,a,l-1); if(a) a->rev(); rt=merge(rt,a); rt=merge(rt,b); } // 區間加值 void add(int l,int r,int v){ node *a,*b; splitSz(rt,rt,b,r); splitSz(rt,rt,a,l-1); a->val+=v; a->push(); rt=merge(rt,a); rt=merge(rt,b); } ``` ## 特殊功能 ### Count $[ \; l, \, r \; ]$ 在一棵作為二元搜尋樹的 Treap 中，計算介於 l 到 r 的元素數量 基本上就跟上面區間查詢相同。只是切割依據不同。 #### 實作 ```cpp= int count(int l,int r){ node *a,*b; split(rt,rt,b,r); split(rt,rt,a,l-1); // 下一行依據要插尋的內容放 sz(數量) 或 sum(總和) int ret=a->sz; rt=merge(rt,a); rt=merge(rt,b); return ret; } ``` ### Sum $[ \; l, \, r \; ]$ (rank) 在一棵作為二元搜尋樹的 Treap 中，計算介於第 l 小到第 r 小的元素總和 同樣就跟上面區間查詢相同。只是元素排列方式不同。 #### 實作 ```cpp= int Sum(int l,int r){ node *a,*b; splitSz(rt,rt,b,r); splitSz(rt,rt,a,l-1); // 下一行依據要插尋的內容放 sum(總和) 或 xor 值 int ret=a->sum; rt=merge(rt,a); rt=merge(rt,b); return ret; } ``` ### 解構式 對於多筆測資，可能會需要釋放記憶體。由於 Treap 二元樹的特性，可以透過遞迴刪除整棵樹 ```cpp= struct Treap{ struct node{ int val; node *lch,*rch; } node *rt=nullptr; void DeleteTree(node *n){ if(n->lch) DeleteTree(n->lch); if(n->rch) DeleteTree(n->rch); delete(n); } ~Treap(){ if(rt) DeleteTree(n); } } ``` ### 重載輸入輸出 要前中後序都可以 ```cpp= void print(node *n,ostream &output){ n->push(); if(n->lch) print(n->lch,output); // 下面這一行放的位置會決定他是前中後序 output<<n->val<<" "; if(n->rch) print(n->rch,output); } friend ostream &operator<<(ostream &output,PowerfulArray &a){ a.print(a.rt,output); return output; } ``` ### 一些 STL 的常見函式 ```cpp= int size(){ return fs(rt); } bool empty(){ return size()==0; } void push_back(num v){ insert(size()+1,v); } void push_front(num v){ insert(1,v); } void pop_back(){ erase(size()+1); } void pop_front(){ erase(1); } void resize(int sz){ while(size()<sz){ push_back(0); } while(size()>sz){ pop_back(); } } void resize(int sz,num v){ while(size()<sz){ push_back(v); } while(size()>sz){ pop_back(); } } ``` ### 建構式 有了上述的 STL 常見函式之後，就可以很方便的寫建構式了。 ```cpp= Treap(){ } Treap(int sz){ resize(sz); } Treap(int sz,int v){ resize(sz,v); } ``` > **2022/3/10** > [name=mtmatt] [time=Thu, Mar 10, 2022 21:00 ] [color=#00eeff]