淺談 FHQ-Treap

本文同步發表在洛谷博客。

什么是 FHQ-Treap？

平衡樹上存放兩個信息，權值 \(val\) 以及隨機索引 \(key\)。值滿足二叉搜索樹性質，隨機值索引滿足堆的性質，通過結合二叉搜索樹和二叉堆的性質來使樹平衡。至于這里用的是大根堆還是小根堆，不重要。

當權值 \(val\) 的數值情況不可控時，如果保證索引 \(key\) 為隨機，樹的期望深度為 \(\log n\)。

通常的平衡樹維護平衡的方法是旋轉，而 FHQ-Treap 則是用分裂和合并來實現的。

詳解 FHQ-Treap

FHQ-Treap 存放的節點信息

首先，有必不可少的權值 \(val\) 和隨即索引 \(key\)。其次為了維護樹的結構，肯定要有左節點編號 \(ls\) 以及右節點編號 \(rs\)。當然，為了求排名之類的東西，我們還會維護一個子樹大小 \(sz\)。由于要維護的信息較多，這里采用結構體進行維護。

struct FHQ_Trp{int ls,rs,val,key,sz;}tree[N];

當然，你還需要 \(cnt\) 和 \(root\)，分別表示當前節點個數（也就是最大的編號）以及當前這棵平衡樹的根節點 \(root\)。

FHQ-Treap 需要用到的操作

創建新節點

很簡單。首先將 \(cnt \gets cnt+1\) 然后讓這個節點的編號為 \(cnt\)。給定這個節點的 \(val\) 值，為傳參進來的 \(k\)，然后再用 mt19937 隨機生成索引 \(key\)，以及要記得初始化子樹大小為 \(1\) 哦。

mt19937 num(998244353);
int New_node(int k){
    ++cnt;
    tree[cnt].val=k;
    tree[cnt].key=num();
    tree[cnt].sz=1;
    return cnt;
}

分裂操作

分裂，即 Split，是 FHQ-Treap 中必不可少的一環。

分裂方法有兩種：

按值分裂：把樹拆成兩棵樹，拆出來的一棵樹的值全部小于等于給定的值，另外一棵樹的值全部大于給定的值。
按大小分裂：把樹拆成兩棵樹，拆出來的一棵樹的值全部等于給定的大小，剩余部分在另外一顆樹里。

通常來說，當 FHQ-Treap 作為正常平衡樹使用時，采用按值分裂；維護區間信息時，用按大小分裂。

這里用按值分裂舉例。其實很簡單的，根據二叉搜索樹的性質，如果當前節點的權值小于等于這個分裂的值，那么左子樹肯定都穩了，可右子樹還確定不了，因此這個時候就往右邊遞歸；同理，如果當前節點的權值大于這個分裂的值，那么右子樹也肯定都穩了，左子樹不確定，這個時候就往左遞歸。更新迭代的時候不要忘了更新分裂出來的兩棵樹的情況，以及它們的根哦。當然，在更新完成之后需要對當前節點進行一次 upd，因為樹的結構會隨著分裂的操作而變化，子樹大小需要重新維護。

void upd(int u){
    tree[u].sz=tree[tree[u].ls].sz+tree[tree[u].rs].sz+1;return;
}
void Split(int u,int k,int &x,int &y){
    if(!u){x=0,y=0;return;}
    else if(tree[u].val<=k){
        x=u;
        Split(tree[u].rs,k,tree[u].rs,y);
    }else{
        y=u;
        Split(tree[u].ls,k,x,tree[u].ls);
    }upd(u);return;
}

合并操作

合并操作，很簡單的，就是把兩棵分別以 \(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;
    }
}

值得注意的是，當你的平衡樹的分裂操作做的是按大小分裂的時候，即你維護區間情況的時候，一定要注意，\(\text{Merge}(x,y)\) 和 \(\text{Merge}(y,x)\) 是在干兩件不同的事情哦！本人被狠狠坑過。

如何維護 FHQ-Treap

插入節點

假設我們要插入的節點的權值為 \(k\)。首先我們要分裂這棵平衡樹，把它分裂成兩個部分，一個部分的權值 \(\le k\)，還有一個部分的權值 \(>k\)，即執行 \(\text{Split}(root,k,x,y)\) 操作，其中 \(x\) 和 \(y\) 是你設定的兩個變量，用于存儲分裂后的樹的兩個根節點。接著，我們考慮新建一個節點村上這個要插入的值，然后將其和以 \(x\) 為根的樹合并，最后再和以 \(y\) 為根的樹合并。這樣，你就完美地實現了一個插入的過程！

void Insert(int k){
    int x=0,y=0;
    Split(root,k,x,y);
    root=Merge(Merge(x,New_node(k)),y);
    return;
}

刪除節點

同樣假設我們要刪除的節點的權值為 \(k\)。首先，仍然對樹進行分裂，不過這一次我們將把樹分裂成三部分：以 \(x\) 為根節點的部分，所有節點權值 \(< k\)；以 \(y\) 為根節點的部分，所有節點權值 \(=k\)；以 \(z\) 為根節點的部分，所有節點權值 \(>k\)。這個時候，我們只需要從以 \(y\) 為根節點的樹里面刪掉一個節點，最后把大家全都合并起來就可以了。如何刪掉 \(y\) 中的一個節點？很簡單，由于權值都是 \(k\)，沒多大區別，因此直接把根節點刪掉，讓 \(y\) 的左子樹和右子樹合并起來就行了。如果題目特殊要求，說如果存在多個全部刪掉，那么最后就只需要合并 \(x\) 和 \(z\) 了，\(y\) 直接扔掉不管就行。

void Delete(int k){
    int x=0,y=0,z=0;
    Split(root,k,x,z);
    Split(x,k-1,x,y);
    y=Merge(tree[y].ls,tree[y].rs);
    root=Merge(Merge(x,y),z);
    return;
}

給定數值查詢排名

即根據具體值的大小情況查詢排名，如有重復則存在并列情況。假設這個值為 \(k\)。

很簡單啦，同樣對樹進行分裂，不同于以往的 \(\le k\) 以及 \(> k\)，這次為了方便求排名我們是按照 \(<k\) 和 \(\ge k\) 去分裂的，然后得到 \(<k\) 的這一部分樹的大小，加上一就是答案。最后記得要把樹合并回來。

int Get_rank(int k){
    int x=0,y=0,rk=0;
    Split(root,k-1,x,y);
    rk=tree[x].sz+1;
    Merge(x,y);return rk;
}

給定排名查詢數值

很簡單，從根節點開始往下搜索，如果左子樹大小 \(+1\) 恰好等于傳參進來的 \(rk\)（也就是排名），那么說明當前 \(u\) 就是答案，直接返回即可；否則根據左子樹的大小是否足夠，判斷現在 \(u\) 是移動向左子樹還是右子樹，同時如果往右子樹移的話要注意將 \(rk\) 的值減少對應數量。如果到最后都還沒找到就返回 \(-1\)，但除非這個排名越界了，否則都是會找到的啦！

int Get_number(int rk){
    int u=root;
    while(u){
        if(tree[tree[u].ls].sz+1==rk)return tree[u].val;
        else if(tree[tree[u].ls].sz>=rk)u=tree[u].ls;
        else rk-=tree[tree[u].ls].sz+1,u=tree[u].rs;
    }return -1;
}

查詢數值前驅

數值 \(k\) 的前驅定義為最大的 \(<k\) 的數的具體值，\(k\) 不一定要在樹中出現過。

依然很簡單，與上面相同的，把樹拆成 \(< k\) 和 \(\ge k\) 的兩部分，然后從 \(<k\) 的那部分樹的根節點找起，只要有右節點，就一直往右邊跑（因為這樣才能得到最大值），直到沒得跑了，直接返回就行了，不過要注意把樹合并回來。

int Find_pre(int k){
    int x=0,y=0;Split(root,k-1,x,y);
    int u=x;while(tree[u].rs)u=tree[u].rs;
    Merge(x,y);return u;
}

查詢數值后繼

數值 \(k\) 的后繼定義為最小的 \(>k\) 的數的具體值，\(k\) 不一定要在樹種出現過。

和查詢前驅是一樣的，不同的是，這里是把樹拆成 \(\le k\) 和 \(>k\) 兩部分，然后從 \(>k\) 的那部分樹的根節點找起。當然了，這里是一直往左邊跑，因為這樣才能得到最小值嘛！同樣要記得把樹合并回來。

int Find_nxt(int k){
    int x=0,y=0;Split(root,k,x,y);
    int u=y;while(tree[u].ls)u=tree[u].ls;
    Merge(x,y);return u;
}

【模版】普通平衡樹

來看板子題，https://www.luogu.com.cn/problem/P3369。

由于其要求支持插入、刪除、查詢排名、查詢數值、查詢前驅后繼這些操作，正好就是上面所提到的，所以把上面的那些零零散散的代碼拼在一起就過了！

為了方便我還是放個完整代碼在這里吧。

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
using namespace std;
const int N = 1e5+5;
mt19937 num(998244353);
int Q,cnt,root;
struct FHQ_Trp{int ls,rs,val,key,sz;}tree[N];
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
int New_node(int k){
    ++cnt;
    tree[cnt].val=k;
    tree[cnt].key=num();
    tree[cnt].sz=1;
    return cnt;
}
void upd(int u){
    tree[u].sz=tree[tree[u].ls].sz+tree[tree[u].rs].sz+1;return;
}
void Split(int u,int k,int &x,int &y){
    if(!u){x=0,y=0;return;}
    else if(tree[u].val<=k){
        x=u;
        Split(tree[u].rs,k,tree[u].rs,y);
    }else{
        y=u;
        Split(tree[u].ls,k,x,tree[u].ls);
    }upd(u);return;
}
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;
    }
}
void Insert(int k){
    int x=0,y=0;
    Split(root,k,x,y);
    root=Merge(Merge(x,New_node(k)),y);
    return;
}
void Delete(int k){
    int x=0,y=0,z=0;
    Split(root,k,x,z);
    Split(x,k-1,x,y);
    y=Merge(tree[y].ls,tree[y].rs);
    root=Merge(Merge(x,y),z);
    return;
}
int Get_rank(int k){
    int x=0,y=0,rk=0;
    Split(root,k-1,x,y);
    rk=tree[x].sz+1;
    Merge(x,y);return rk;
}
int Get_number(int rk){
    int u=root;
    while(u){
        if(tree[tree[u].ls].sz+1==rk)return tree[u].val;
        else if(tree[tree[u].ls].sz>=rk)u=tree[u].ls;
        else rk-=tree[tree[u].ls].sz+1,u=tree[u].rs;
    }return -1;
}
int Find_pre(int k){
    int x=0,y=0;Split(root,k-1,x,y);
    int u=x;while(tree[u].rs)u=tree[u].rs;
    Merge(x,y);return u;
}
int Find_nxt(int k){
    int x=0,y=0;Split(root,k,x,y);
    int u=y;while(tree[u].ls)u=tree[u].ls;
    Merge(x,y);return u;
}
int main(){
    Q=read();
    while(Q--){
        int opt=read(),x=read();
        if(opt==1)Insert(x);
        else if(opt==2)Delete(x);
        else if(opt==3)cout<<Get_rank(x)<<"\n";
        else if(opt==4)cout<<Get_number(x)<<"\n";
        else if(opt==5)cout<<tree[Find_pre(x)].val<<"\n";
        else cout<<tree[Find_nxt(x)].val<<"\n";
    }
    return 0;
}

【模版】文藝平衡樹

就是 https://www.luogu.com.cn/problem/P3391 啦！

這里維護的是區間，所以在上面分裂那里要按大小分裂。

問題在于……不管你維護的什么，這里的翻轉操作我也不會弄啊！不過其實沒多難，就是把左右子樹交換 swap 一下。

可是這么暴力弄都是 \(O(n \times m)\) 的，不超時才怪呢。咋搞？

還記得線段樹是如何讓區間操作的時間復雜度降下來的？你說對了——懶標記！這里也是一樣的道理！

在結構體 FHQ_Trp 里多加 \(tag\) 一維，表示這里的標記，每次需要修改，我們就把 \(tag\) 進行反轉。涉及子樹修改的情況下，我們再進行 push_down 下傳標記。

當然了，我們要進行拆樹（不然你給誰標記呢？），拆成 \([1,l-1]\)、\([l,r]\)、\([r+1,n]\) 三個部分，然后需要翻轉的當然就是中間 \([l,r]\) 的那一部分啦！最后別忘了并回去。

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
using namespace std;
const int N = 1e5+5;
mt19937 num(998244353);
int n,m,cnt,root;
struct FHQ_Trp{int ls,rs,val,key,sz;bool tag;}tree[N];
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
int New_node(int k){
    ++cnt;
    tree[cnt].val=k;
    tree[cnt].key=num();
    tree[cnt].sz=1;
    return cnt;
}
void push_down(int u){
    if(!tree[u].tag)return;
    swap(tree[u].ls,tree[u].rs);
    tree[tree[u].ls].tag^=1;
    tree[tree[u].rs].tag^=1;
    tree[u].tag=0;return;
}
void upd(int u){
    tree[u].sz=tree[tree[u].ls].sz+tree[tree[u].rs].sz+1;return;
}
void Split(int u,int k,int &x,int &y){
    if(!u){x=0,y=0;return;}
    push_down(u);
    if(tree[tree[u].ls].sz+1<=k){
        x=u;
        Split(tree[u].rs,k-tree[tree[u].ls].sz-1,tree[u].rs,y);
    }else{
        y=u;
        Split(tree[u].ls,k,x,tree[u].ls);
    }upd(u);return;
}
int Merge(int x,int y){
    if(!x||!y)return x+y;
    if(tree[x].key>tree[y].key){
        push_down(x);
        tree[x].rs=Merge(tree[x].rs,y);
        upd(x);return x;
    }else{
        push_down(y);
        tree[y].ls=Merge(x,tree[y].ls);
        upd(y);return y;
    }
}
void Insert(int k){
    int x=0,y=0;
    Split(root,k,x,y);
    root=Merge(Merge(x,New_node(k)),y);
    return;
}
void Delete(int k){
    int x=0,y=0,z=0;
    Split(root,k,x,z);
    Split(x,k-1,x,y);
    y=Merge(tree[y].ls,tree[y].rs);
    root=Merge(Merge(x,y),z);
    return;
}
void Sol(int l,int r){
    int x=0,y=0,z=0;
    Split(root,r,x,z);
    Split(x,l-1,x,y);
    tree[y].tag^=1;
    root=Merge(Merge(x,y),z);
    return;
}
void DFS(int u){
    if(!u)return;
    push_down(u);
    DFS(tree[u].ls);
    cout<<tree[u].val<<" ";
    DFS(tree[u].rs);
    return;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)Insert(i);
    for(int i=1;i<=m;i++){
        int l=read(),r=read();
        Sol(l,r);
    }DFS(root);cout<<"\n";
    return 0;
}

posted @ 2025-10-29 17:44 嘎嘎喵閱讀(14) 評論(0) 收藏舉報

刷新頁面返回頂部

嘎嘎喵

嘎嘎嘎？喵喵喵！（