（简记）FHQ Treap

TBSF_0207 · 2025-03-05 16:32:19 · 算法·理论

补题总是发现不想写旋转 Treap，今天终于重学了一遍 FHQ Treap 大法，特此总结（并不）。

FHQ Treap

FHQ Treap 通过不断的分裂和合并操作维护一个 BST（一个 BST 是一颗二叉树，每个节点具有优先级 \text{pri} 和键值 \text{key}，其中键值要满足 t[ls].key\le t[p].key \le t[rs].key，优先级满足大根堆性质即 t[p].pri\geq t[ls].pri,t[p].pri\geq t[rs].pri）。

基本操作

Split

分裂指将以 p 为根节点的 BST 分为根为 L,R 的两棵 BST，使得 L 树上所有点的键值都 \le x，R 树上的所有点键值都 >x。

分裂成两棵树的操作函数十分简单：

void Split(int p,int x,int &L,int &R){
    if(!p){L=R=0;return ;}
    if(t[p].key<=x){
        L=p;
        Split(t[p].rs,x,t[p].rs,R);
    }
    else {
        R=p;
        Split(t[p].ls,x,L,t[p].ls);
    }
    pushup(p);
}

代码中引用传递的L,R分别代表以 p 为根的树分裂后得到的左树和右树的根。分类讨论即可。注意每层函数的L,R的意义不尽相同，需要分开考虑。

Merge

int Merge(int L,int R){
    if(!L||!R)return L|R;
    if(t[L].pri>t[R].pri){
        t[L].rs=Merge(t[L].rs,R);
        pushup(L);
        return L;
    }
    else {
        t[R].ls=Merge(L,t[R].ls);
        pushup(R);
        return R;
    }
}

同样的，把两棵树并起来的过程，考虑每层的节点谁优先值更大就当父亲，根据优先顺序把另一个点接上去，可以想象理想状态下两棵形态完全相同的树一个节点变成两个节点（这样的比喻好像不太合适，但只是方便理解）。

时间分析

通过上述代码我们可以看出，由于 BST 的期望高度为 O(\log n)（为什么？随机生成一棵高 log n 的树），且上述操作每一层都是 O(1) 的，我们有很好的理由相信一次操作的总时间就是 O(\log n) 的。

例题

针对一般平衡树维护，我们在每个节点多维护一个表示子树大小的 size，然后简单加以灵活应用即可。由于这是一篇简记而不是笔记，就不详细展开了。

下面给出P3369 【模板】普通平衡树的 FHQ Treap 完整代码。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int ncnt,root,n;
struct Node{
    int ls,rs;
    int key,pri;
    int size;
}t[N];
inline int newNode(int x){
    ncnt++;
    t[ncnt].key=x;
    t[ncnt].pri=rand();
    t[ncnt].size=1;
    return ncnt;
}
inline void pushup(int p){
    t[p].size=1+t[t[p].ls].size+t[t[p].rs].size;
}
void Split(int p,int x,int &L,int &R){
    if(!p){L=R=0;return ;}
    if(t[p].key<=x){
        L=p;
        Split(t[p].rs,x,t[p].rs,R);
    }
    else {
        R=p;
        Split(t[p].ls,x,L,t[p].ls);
    }
    pushup(p);
}
int Merge(int L,int R){
    if(!L||!R)return L|R;
    if(t[L].pri>t[R].pri){
        t[L].rs=Merge(t[L].rs,R);
        pushup(L);
        return L;
    }
    else {
        t[R].ls=Merge(L,t[R].ls);
        pushup(R);
        return R;
    }
}
void Insert(int x){
    int L,R;
    Split(root,x,L,R);
    root=Merge(Merge(L,newNode(x)),R);
}
void Delete(int x){
    int L,R,p;
    Split(root,x,L,R);
    Split(L,x-1,L,p);
    p=Merge(t[p].ls,t[p].rs);
    root=Merge(Merge(L,p),R);
}
int Rank(int x){
    int L,R,p,res;
    Split(root,x-1,L,R);
    res=t[L].size+1;
    Merge(L,R);
    return res;
}
int kth(int p,int k){
    if(t[t[p].ls].size+1==k)return t[p].key;
    if(k<=t[t[p].ls].size)return kth(t[p].ls,k);
    return kth(t[p].rs,k-t[t[p].ls].size-1);
}
int pre(int x){
    int L,R,res;
    Split(root,x-1,L,R);
    res=kth(L,t[L].size);
    Merge(L,R);
    return res;
}
int suc(int x){
    int L,R,res;
    Split(root,x,L,R);
    res=kth(R,1);
    Merge(L,R);
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    srand(time(NULL));
    cin>>n;
    for(int i=1;i<=n;i++){
        int opt,x;
        cin>>opt>>x;
        if(opt==1)Insert(x);
        else if(opt==2)Delete(x);
        else if(opt==3)cout<<Rank(x)<<'\n';
        else if(opt==4)cout<<kth(root,x)<<'\n';
        else if(opt==5)cout<<pre(x)<<'\n';
        else cout<<suc(x)<<'\n';
    }
    return 0;
}

可持久化版本

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int ncnt,root[N],n,ver,id;
struct Node{
    int ls,rs;
    int key,pri;
    int size;
}t[N*50];
inline int newNode(int x){
    ncnt++;
    t[ncnt].key=x;
    t[ncnt].pri=rand();
    t[ncnt].size=1;
    return ncnt;
}
inline void pushup(int p){
    t[p].size=1+t[t[p].ls].size+t[t[p].rs].size;
}
void Split(int p,int x,int &L,int &R){
    if(!p){L=R=0;return ;}
    if(t[p].key<=x){
        L=newNode(0);
        t[L]=t[p];
        Split(t[L].rs,x,t[L].rs,R);
        pushup(L);
    }
    else {
        R=newNode(0);
        t[R]=t[p];
        Split(t[R].ls,x,L,t[R].ls);
        pushup(R);
    }
}
int Merge(int L,int R){
    if(!L||!R)return L|R;
    if(t[L].pri>t[R].pri){
        int rt=newNode(0);
        t[rt]=t[L];
        t[rt].rs=Merge(t[rt].rs,R);
        pushup(rt);
        return rt;
    }
    else {
        int rt=newNode(0);
        t[rt]=t[R];
        t[rt].ls=Merge(L,t[rt].ls);
        pushup(rt);
        return rt;
    }
}
void Insert(int x){
    int L,R;
    Split(root[ver],x,L,R);
    root[id]=Merge(Merge(L,newNode(x)),R);
}
void Delete(int x){
    int L,R,p;
    Split(root[ver],x,L,R);
    Split(L,x-1,L,p);
    p=Merge(t[p].ls,t[p].rs);
    root[id]=Merge(Merge(L,p),R);
}
int Rank(int x){
    int L,R,p,res;
    Split(root[ver],x-1,L,R);
    res=t[L].size+1;
    root[id]=Merge(L,R);
    return res;
}
int kth(int p,int k){
    if(t[t[p].ls].size+1==k)return t[p].key;
    if(k<=t[t[p].ls].size)return kth(t[p].ls,k);
    return kth(t[p].rs,k-t[t[p].ls].size-1);
}
int pre(int x){
    int L,R,res;
    Split(root[ver],x-1,L,R);
    if(!L)return -(1ll<<31)+1;
    res=kth(L,t[L].size);
    root[id]=Merge(L,R);
    return res;
}
int suc(int x){
    int L,R,res;
    Split(root[ver],x,L,R);
    if(!R)return (1ll<<31)-1;
    res=kth(R,1);
    root[id]=Merge(L,R);
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    srand(time(NULL));
    cin>>n;
    for(id=1;id<=n;id++){
        int opt,x;
        cin>>ver>>opt>>x;
        if(opt==1)Insert(x);
        else if(opt==2)Delete(x);
        else if(opt==3)cout<<Rank(x)<<'\n';
        else if(opt==4)root[id]=root[ver],cout<<kth(root[ver],x)<<'\n';
        else if(opt==5)cout<<pre(x)<<'\n';
        else cout<<suc(x)<<'\n';
    }
    return 0;
}