鮮花

一些鮮花放在前面，平衡樹學了很久，但是每學一遍都忘，原因就在於我只能 70% 理解 + 30% 背板子，所以每次都忘。這次我採取了截然不同的策略，自己按照自己的理解打一遍，大獲成功（？），大概打 20 min，調 10 min 結束，然後寫下了這篇文章。

雖然但是，感覺 Treap 還是很強的，程式碼好寫好調，而且可以解決很多問題（下面將會提到），好像說是常數大一點？無傷大雅吧……

Treap

首先，從 Treap 的定義開始。Treap 實際上是一種笛卡爾樹（笛卡爾樹可以看這篇文章，每個點有兩個資訊 \((v_u,p_u)\)，分別表示點 \(u\) 的權值與優先度。\(v_u\) 形成一個二元搜尋樹（左兒子的值 \(\leq\) 自己的值 \(\leq\) 右兒子的值），\(p_u\) 形成一個大根堆（自己的值 \(\geq\) 左右兒子的值）。

你可以利用 Treap 做很多有用的操作，但是 Treap 有一個缺點，就是如果被卡成鏈怎麼辦？

FHQ Treap

這時候就需要用到 FHQ Treap，它基於 Treap 的基礎上對每個點的 \(p\) 值都進行了隨機化操作，這樣就可以達到平衡的目的了。為什麼？因為隨機出來不平衡的概率很小，大多亂數都是無規律的，這樣通過大根堆的性質就可以使它達到平衡，這樣樹高期望就是 \(O(\log n)\) 層的了，並且無法卡掉，因為亂數是程式生成的，並非資料所決定。

系統隨機函數若以 srand(time(0)) 為隨機種子，效果不佳，推薦使用 mt19937 rnd(233)，生成亂數更加均勻。

FHQ Treap 又叫無旋 Treap，它只需要兩個核心操作 merge() 和 split() 即可完成所有的複雜操作，就像玩拼圖一樣把一棵樹拆開再拼起來一樣。下面就來具體介紹一下這兩個函數到底是如何實現的。

關於 upd 函數的說明

（這個可以學完下面的再看）upd 函數，即重新整理一個節點大小的函數。在 split() 中，在分裂完子樹後最後應該重新整理，不然可能大小資訊已經被更改而不知道。同理，在 merge() 中，合併子樹後也應當重新整理，調不出來一定要檢查一下是否因忘記重新整理而錯誤。

split 函數

split 函數實現的功能是把一棵樹按照權值大小拆分成兩棵樹，具體來說，split(int cur,int k,int &x,int &y) 表示將以 cur 為根的子樹拆分成兩棵樹 \(x\) 和 \(y\)，其中 \(x\) 裡的權值都 \(\leq k\)，\(y\) 裡的權值都 \(>k\)。

怎麼寫呢？首先，為了方便返回，直接將要拆分成的兩棵子樹參照定義在函數引數中。先特判一下，如果要拆分的樹為空，則拆分出來的兩棵樹也為空。不然就判斷樹根是否 \(\leq k\)，如果是，則樹左子樹都 \(\leq k\)，即屬於 \(x\)，那麼只要分裂右子樹即可，反之亦然。

程式碼

void split(int cur,int k,int &x,int &y)
{
    if(!cur)
    {
        x=y=0;
        return;
    }
    if(tree[cur].val<=k)
    {
        x=cur;
        split(tree[x].rs,k,tree[x].rs,y);
    }
    else
    {
        y=cur;
        split(tree[y].ls,k,x,tree[y].ls);
    }
    upd(cur);
}

merge 函數

merge 函數就是把兩個樹 \(x,y\) 合併，保證所有 \(x\) 中的 \(v\) 都 \(\leq\) 所有 \(y\) 中的 \(v\)，具體來說，就是 int merge(int x,int y)。

寫法就是判斷 \(x,y\) 中是否有空樹，有的話直接返回另一個即可。不然比較兩者根的有先值，如果第一個大，根據大根堆性質，顯然應該合併 \(x\) 的右子樹和 \(y\)，反之亦然。

程式碼

int merge(int x,int y)
{
    if(!x||!y)
        return x+y;
    if(tree[x].key>=tree[y].key)
    {
        tree[x].rs=merge(tree[x].rs,y);
        upd(x);
        return x;
    }
    else
    {
        tree[y].ls=merge(x,tree[y].ls);
        upd(y);
        return y;
    }
}

其他操作的實現

下面來看看 FHQ Treap 能實現哪些操作吧，請看模板題普通平衡樹。（下面全部內容為筆者自己發揮，若有更好做法請在評論區留言或私信筆者）

插入 \(x\)：將根以 \(x\) 值分裂，在中間建一個新的點合併回去即可，比較容易。
刪除 \(x\)：將根分別以 \(x-1,x\) 分裂，中間一個樹就是權值為 \(x\) 的樹，把這個樹替換為它左右子樹合併的結果即可（因為只要刪一個，相當於把根節點給刪了。
查詢 \(x\) 的排名：這個非常容易，直接按 \(x-1\) 分裂並輸出第一個子樹大小 +1 即可。
查詢排名為 \(x\) 的數：這個可以從根節點開始，不停地判斷應該往左子樹走還是右子樹走，判斷方式就是看當前點地左子樹大小 +1 和 \(x\) 的大小關係，若相等則直接退出。
查詢 \(x\) 的前驅：筆者做法比較暴力，直接將數按 \(x-1\) 分裂，第一棵樹的最後一個就是，最後一個求可以查詢排名為數大小的數，用之前的函數可以求出。
查詢 \(x\) 的後繼：同前驅做法，按 \(x\) 分裂，第二棵樹的第一個就是，同樣查詢排名為 1 的樹即可，使用之前的函數。

具體的還是看程式碼吧。

程式碼

#include <bits/stdc++.h>
#define TIME 1e3*clock()/CLOCKS_PER_SEC
using namespace std;
// stay organized
mt19937 rnd(233);
const int maxn=1e5+10;
struct Node
{
    int ls,rs;
    int siz;
    int val,key;
}tree[maxn];
int rt=0,tot=0;
int newnode(int val)
{
    tot++;
    tree[tot].ls=tree[tot].rs=0;
    tree[tot].siz=1;
    tree[tot].val=val;
    tree[tot].key=rnd();
    return tot;
}
void upd(int x)
{
    tree[x].siz=tree[tree[x].ls].siz+1+tree[tree[x].rs].siz;
}
void split(int cur,int k,int &x,int &y)
{
    if(!cur)
    {
        x=y=0;
        return;
    }
    if(tree[cur].val<=k)
    {
        x=cur;
        split(tree[x].rs,k,tree[x].rs,y);
    }
    else
    {
        y=cur;
        split(tree[y].ls,k,x,tree[y].ls);
    }
    upd(cur);
}
int merge(int x,int y)
{
    if(!x||!y)
        return x+y;
    if(tree[x].key>=tree[y].key)
    {
        tree[x].rs=merge(tree[x].rs,y);
        upd(x);
        return x;
    }
    else
    {
        tree[y].ls=merge(x,tree[y].ls);
        upd(y);
        return y;
    }
}
int x,y,z;
void ins(int val)
{
    split(rt,val,x,y);
    rt=merge(merge(x,newnode(val)),y);
}
void del(int val)
{
    split(rt,val-1,x,y);
    split(y,val,y,z);
    y=merge(tree[y].ls,tree[y].rs);
    rt=merge(merge(x,y),z);
}
int rnk(int val)
{
    split(rt,val-1,x,y);
    int ans=tree[x].siz+1;
    rt=merge(x,y);
    return ans;
}
int kth(int now,int k)
{
    while(tree[tree[now].ls].siz+1!=k)
    {
        if(tree[tree[now].ls].siz+1>k)
            now=tree[now].ls;
        else
        {
            k-=tree[tree[now].ls].siz+1;
            now=tree[now].rs;
        }
    }
    return tree[now].val;
}
int pre(int val)
{
    split(rt,val-1,x,y);
    int ans=kth(x,tree[x].siz);
    rt=merge(x,y);
    return ans;
}
int suf(int val)
{
    split(rt,val,x,y);
    int ans=kth(y,1);
    rt=merge(x,y);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    int opt,x;
    while(t--)
    {
        cin>>opt>>x;
        if(opt==1)
            ins(x);
        else if(opt==2)
            del(x);
        else if(opt==3)
            cout<<rnk(x)<<'\n';
        else if(opt==4)
            cout<<kth(rt,x)<<'\n';
        else if(opt==5)
            cout<<pre(x)<<'\n';
        else cout<<suf(x)<<'\n';
    }
    return 0;
    // you should actually read the stuff at the bottom
}

/* stuff you should look for
    * int overflow, array bounds
    * clear the arrays?
    * special cases (n=1?),
    * WRITE STUFF DOWN,
    * DON'T GET STUCK ON ONE APPROACH
*/

完結撒花 owo~

FHQ Treap 詳解

鮮花

Treap

FHQ Treap

split 函數

merge 函數

其他操作的實現