学习心得 - 数据结构 - FHQ Treap

· · 算法·理论

哦不终于学会 FHQ Treap 了。

FHQ Treap 的本质

这个东西其实就是 Treap 的一种实现。它通过对树的拆分和合并完成 Treap 能实现的几乎所有操作，操作又简单。每一次可以把原树拆分成以 rtl 和 rtr 为根两颗子树。然后再查询其中的一些信息做到成功维护信息。

维护信息 \tt PushUp

我们需要维护的信息是节点权值（随机）、节点信息和节点大小。那么，我们的 \tt pushup 其实就是直接更新 sz，也就是 a_p.sz=a_{a_p.ls}.sz+a_{a_p.rs}+1。

::::success[参考代码]{open}

void pushup(int p){ 
    a[p].sz=a[a[p].ls].sz+a[a[p].rs].sz+1;
    return;
}

::::

拆分树 \tt Split

这个操作就是把树切开，切成以 rtl 和 rtr 为根两颗子树，如图：

这样切割，就可以拆分成两颗以 2、5 为根的子树。

切割后：

具体看代码：

::::success[参考代码]{open}

void split(int p,int val,int &rtl,int &rtr){
    if(!p){ // 特别的，在插入第一个数的时候是空树
        rtl=rtr=0;
        return;
    }
    if(a[p].val<val) // 更大，往右走
        rtl=p,split(a[p].rs,val,a[p].rs,rtr);
    else // 否则，往左走
        rtr=p,split(a[p].ls,val,rtl,a[p].ls);
    pushup(p); // 合并
    return ;
}

::::

合并树 \tt Merge

::::warning[警告]{open} 合并必须要保证值域不重复。否则合并就需要使用启发式合并，可是这可以卡到 \mathcal O(n\log n)。这就需要把树分成尽量小的段再合并，又称有交合并。

具体的，我们需要维护一个最小端点 minval_i，每一次维护就给左中右合并一下，然后每一次快速合并，复杂度是 \mathcal O(n\log^2 n)。

其实这个东西就是给每一个节点赋一个随机权值，然后像启发式合并一样合并。

::::success[参考代码]{open}

int merge(int u,int v){
    if(!u||!v) // 合并空树
        return u|v;
    if(a[u].rnd<a[v].rnd){ // 看随机权值大小
        a[u].rs=merge(a[u].rs,v),pushup(u); // 递归合并
        return u; // 返回合并新根
    }else{
        a[v].ls=merge(u,a[v].ls),pushup(v); // 递归合并
        return v; // 返回合并新根
    }
}

::::

扩展操作

然后就这样我们可以通过组合它们进行操作。

void insert(int val){
    Node(val); // 建立新点
    int rtl,rtr;
    split(rt,val,rtl,rtr); // 把树直接从根节点往下剖开
    rt=merge(merge(rtl,tot),rtr); // 然后插进去（？）
    return;
}
void del(int val){
    int rtl,rtr,rta,rtb;
    split(rt,val,rtl,rtr); // 剖开
    split(rtr,val+1,rta,rtb); // 剖开
    rta=merge(a[rta].ls,a[rta].rs); // 合并，并把 val 抛弃
    rt=merge(rtl,merge(rta,rtb));
}
int rnk(int val){
    int rtl,rtr,res;
    split(rt,val,rtl,rtr);
    res=a[rtl].sz+1; // 左子树的大小其实是 <val 的数的个数，然后 +1 就是具体排名
    rt=merge(rtl,rtr); // 搞完放回去
    return res;
}
int kth(int k){ // 这个没有方法了，按照普通平衡树的方法找即可
    int p=rt;
    while(p){
        if(k==a[a[p].ls].sz+1) // 找到了
            return a[p].val;
        if(k<=a[a[p].ls].sz) // 应当在左侧
            p=a[p].ls;
        else  // 右侧
            k-=a[a[p].ls].sz+1,
            p=a[p].rs;
    }
    return -1;
}
// 经典操作
int pre(int val){ 
    return kth(rnk(val)-1);
}
int nxt(int val){
    return kth(rnk(val+1));
}

参考代码（加强版）

::::success[参考代码]

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1e6+10;
default_random_engine rander;
uniform_int_distribution<int>rnd(1,(int)1e9);
struct FhqTreap{
    struct node{
        int val,sz,ls,rs,rnd;
    }a[N<<2];
    int tot=0,rt=0;
    void Node(int val){
        ++tot;
        a[tot]={val,1,0,0,rnd(rander)};
        return;
    }
    void pushup(int p){
        a[p].sz=a[a[p].ls].sz+a[a[p].rs].sz+1;
        return;
    }
    void split(int p,int val,int &rtl,int &rtr){
        if(!p){
            rtl=rtr=0;
            return;
        }
        if(a[p].val<val)
            rtl=p,split(a[p].rs,val,a[p].rs,rtr);
        else
            rtr=p,split(a[p].ls,val,rtl,a[p].ls);
        pushup(p);
        return ;
    }
    int merge(int u,int v){
        if(!u||!v)
            return u|v;
        if(a[u].rnd<a[v].rnd){
            a[u].rs=merge(a[u].rs,v),pushup(u);
            return u;
        }else{
            a[v].ls=merge(u,a[v].ls),pushup(v);
            return v;
        }
    }
    void insert(int val){
        Node(val);
        int rtl,rtr;
        split(rt,val,rtl,rtr);
        rt=merge(merge(rtl,tot),rtr);
        return;
    }
    void del(int val){
        int rtl,rtr,rta,rtb;
        split(rt,val,rtl,rtr);
        split(rtr,val+1,rta,rtb);
        rta=merge(a[rta].ls,a[rta].rs);
        rt=merge(rtl,merge(rta,rtb));
    }
    int rnk(int val){
        int rtl,rtr,res;
        split(rt,val,rtl,rtr);
        res=a[rtl].sz+1;
        rt=merge(rtl,rtr);
        return res;
    }
    int kth(int k){
        int p=rt;
        while(p){
            if(k==a[a[p].ls].sz+1)
                return a[p].val;
            if(k<=a[a[p].ls].sz)
                p=a[p].ls;
            else 
                k-=a[a[p].ls].sz+1,
                p=a[p].rs;
        }
        return -1;
    }
    int pre(int val){
        return kth(rnk(val)-1);
    }
    int nxt(int val){
        return kth(rnk(val+1));
    }
}T;
int n,m,a[N],lastans,ans;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    rander.seed(time(0));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        T.insert(a[i]);
    }
    for(int i=1;i<=m;i++){
        int op,x;
        cin>>op>>x;
        x^=lastans;
        if(op==1)
            T.insert(x);
        else if(op==2)
            T.del(x);
        else if(op==3)
            ans^=(lastans=T.rnk(x));
        else if(op==4)
            ans^=(lastans=T.kth(x));
        else if(op==5)  
            ans^=(lastans=T.pre(x));
        else
            ans^=(lastans=T.nxt(x));
    }
    cout<<ans;
    return 0;
}

::::

可持久化

就是维护多个 rt，每一次只更新有更新的节点，因为 FHQ 的优秀性质，所以维护这一点不难，具体的我可以把我的代码放出来，与原版比对就可以学会了。

::::success[参考代码]

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,M=3e7+10;
const int INF=2147483647;
default_random_engine rander;
uniform_int_distribution<int>rnd(1,(int)1e9);
struct FhqTreap{
    struct node{
        int val,sz,ls,rs,rnd;
    }a[M];
    int tot=0,rt[N];
    int Node(int val){
        ++tot;
        a[tot]={val,1,0,0,rnd(rander)};
        return tot;
    }
    void pushup(int p){
        if(!p)
            return;
        a[p].sz=a[a[p].ls].sz+a[a[p].rs].sz+1;
        return;
    }
    void split(int p,int val,int &rtl,int &rtr){
        if(!p){
            rtl=rtr=0;
            return;
        }
        int np=++tot;
        a[np]=a[p];
        if(a[p].val<=val)
            rtl=np,split(a[p].rs,val,a[rtl].rs,rtr),
            pushup(rtl);
        else
            rtr=np,split(a[p].ls,val,rtl,a[rtr].ls),
            pushup(rtr);
        return ;
    }
    int merge(int u,int v){
        if(!u||!v)
            return u|v;
        int np=++tot;
        if(a[u].rnd<a[v].rnd){
            a[np]=a[u];
            a[np].rs=merge(a[np].rs,v);
        }else{
            a[np]=a[v];
            a[np].ls=merge(u,a[np].ls);
        }
        pushup(np);
        return np;
    }
    void insert(int &p,int val){
        int np=Node(val);
        if(!p){
            p=tot;
            return;
        }
        int rtl,rtr;
        split(p,val,rtl,rtr);
        p=merge(merge(rtl,np),rtr);
        return;
    }
    void del(int &p,int val){
        int rtl,rtr,rtb;
        split(p,val,rtl,rtr);
        split(rtl,val-1,rtl,rtb);
        if(rtb){
            int np=merge(a[rtb].ls,a[rtb].rs);
            p=merge(rtl,merge(np,rtr));
        }else
            p=merge(rtl,rtr);
    }
    int rnk(int p,int val){
        if(!p)
            return 0;
        if(val<a[p].val)
            return rnk(a[p].ls,val);
        else
            return rnk(a[p].rs,val)+a[a[p].ls].sz+1;
    }
    int kth(int p,int k){
        if(k<=a[a[p].ls].sz)
            return kth(a[p].ls,k);
        if(k==a[a[p].ls].sz+1)
            return a[p].val;
        return kth(a[p].rs,k-a[a[p].ls].sz-1);
    }
    int pre(int p,int val){
        if(!p)  
            return -INF;
        if(a[p].val<val)
            return max(a[p].val,pre(a[p].rs,val));
        return pre(a[p].ls,val);
    }
    int nxt(int p,int val){
        if(!p)  
            return INF;
        if(a[p].val>val)
            return min(a[p].val,nxt(a[p].ls,val));
        return nxt(a[p].rs,val);
    }
}T;
int n,m,a[N],lastans,ans;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    rander.seed(time(0));
    cin>>m;
    T.rt[0]=0;
    for(int i=1;i<=m;i++){
        int op,ver,x;
        cin>>ver>>op>>x;
        T.rt[i]=T.rt[ver];
        if(op==1)
            T.insert(T.rt[i],x);
        else if(op==2)
            T.del(T.rt[i],x);
        else if(op==3)
            cout<<T.rnk(T.rt[i],x-1)+1<<"\n";
        else if(op==4)
            cout<<T.kth(T.rt[i],x)<<"\n";
        else if(op==5)  
            cout<<T.pre(T.rt[i],x)<<"\n";
        else
            cout<<T.nxt(T.rt[i],x)<<"\n";
    }
    return 0;
}

::::