fhq_treap(无旋 treap) 学习笔记

发布于 22 天前  81 次阅读


fhq_treap(无旋 treap)

参考:远航之曲的博客

感觉比较意识流。

核心思想是平衡树分裂和合并。

类似于 Splay 把区间分离出来,fhq_treap 可以把平衡树进行分裂来提取需要的区间,再通过合并平衡树来维持树高(即堆性质)。这样不仅可以做到维护区间,还免去了旋转操作,代码较为简单。

split & merge & kth

inline void pushup(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;}
inline void split(int u,int k,int &x,int &y){
    if(!u) x=y=0;
    else{
        if(val[u]<=k) x=u,split(ch[u][1],k,ch[u][1],y);
        else y=u,split(ch[u][0],k,x,ch[u][0]);
        pushup(u);
    }
}

我们把一棵平衡树所有权值不大于 $k$ 的结点分成一棵树,其他结点分成另一颗树。如果一个结点权值不大于 $k$,其左子树也一定不大于 $k$,可以直接把该节点连着左子树并入其中一棵树,我们只需要接着考虑右子树。如果其权值大于 $k$ 同理。

pushup 操作可以用来更新子树大小等信息。

有时候也可以考虑将前 $k$ 小的结点分成一棵树,即按照数量来分,详见「对于区间的操作」部分。

inline int merge(int x,int y){
    if(!x||!y) return x+y;
    if(rnd[x]<rnd[y]){
        ch[x][1]=merge(ch[x][1],y);
        pushup(x);return x;
    }
    else{
        ch[y][0]=merge(x,ch[y][0]);
        pushup(y);return y;
    }
}

合并操作就类似于堆的合并,由于堆的权值是随机的,所以暴力合并即可。

inline int kth(int u,int k){
    while(1){
        if(k<=siz[ch[u][0]]) u=ch[u][0];
        else if(k==siz[ch[u][0]]+1) return u;
        else k-=siz[ch[u][0]]+1,u=ch[u][1];
    }
}

kth 操作用来查询查询排名为 $k$ 的数,这个操作有时可以很好地搭配上述操作。

一些基础操作不多赘述,有需要的可以看下边的完整代码的普通平衡树部分。

对于区间的操作

类似于 Splay,我们可以维护一个序列,然后每次对于区间操作时只需要把所需要的区间 split 出来再对整棵树进行操作(例如打标记)即可。为了找出区间,我们需要对于 split 操作进行一些修改,即从按权值分裂为分裂前 $k$ 个结点。

inline void split(int u,int k,int &x,int &y){
    if(!u) x=y=0;
    else{
        pushdown(u);
        if(siz[ch[u][0]]<k) x=u,split(ch[u][1],k-siz[ch[u][0]]-1,ch[u][1],y);
        else y=u,split(ch[u][0],k,x,ch[u][0]);
        pushup(u);
    }
}

用这样的办法可以解决区间翻转等普通 treap 无法实现的问题。详见下方完整代码的文艺平衡树部分。

完整代码

Luogu3369 【模板】普通平衡树

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int ch[N][2],val[N],rnd[N],siz[N],root,cnt;
int newnode(int x){
    siz[++cnt]=1;
    val[cnt]=x;
    rnd[cnt]=rand();
    return cnt;
}
inline void pushup(int x){
    siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
}
inline int merge(int x,int y){
    if(!x||!y) return x+y;
    if(rnd[x]<rnd[y]){
        ch[x][1]=merge(ch[x][1],y);
        pushup(x);return x;
    }
    else{
        ch[y][0]=merge(x,ch[y][0]);
        pushup(y);return y;
    }
}
inline void split(int u,int k,int &x,int &y){
    if(!u) x=y=0;
    else{
        if(val[u]<=k) x=u,split(ch[u][1],k,ch[u][1],y);
        else y=u,split(ch[u][0],k,x,ch[u][0]);
        pushup(u);
    }
}
inline int kth(int u,int k){
    while(1){
        if(k<=siz[ch[u][0]]) u=ch[u][0];
        else if(k==siz[ch[u][0]]+1) return u;
        else k-=siz[ch[u][0]]+1,u=ch[u][1];
    }
}
int Q;
int main(){
    srand(time(0));scanf("%d",&Q);
    while(Q--){
        int opt,a,x,y,z;
        scanf("%d%d",&opt,&a);
        if(opt==1){
            split(root,a,x,y);
            root=merge(merge(x,newnode(a)),y);
        }
        else if(opt==2){
            split(root,a,x,z);
            split(x,a-1,x,y);
            y=merge(ch[y][0],ch[y][1]);
            root=merge(merge(x,y),z);
        }
        else if(opt==3){
            split(root,a-1,x,y);
            printf("%d\n",siz[x]+1);
            root=merge(x,y);
        }
        else if(opt==4){
            printf("%d\n",val[kth(root,a)]);
        }
        else if(opt==5){
            split(root,a-1,x,y);
            printf("%d\n",val[kth(x,siz[x])]);
            root=merge(x,y);
        }
        else if(opt==6){
            split(root,a,x,y);
            printf("%d\n",val[kth(y,1)]);
            root=merge(x,y);
        }
    }
    return 0;
}

Luogu3391 【模板】文艺平衡树

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int ch[N][2],val[N],rnd[N],siz[N],root,cnt;
bool tag[N];
int newnode(int x){
    siz[++cnt]=1;
    val[cnt]=x;
    rnd[cnt]=rand();
    return cnt;
}
inline void pushup(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;}
inline void pushdown(int x){
    if(!tag[x]) return;
    swap(ch[x][0],ch[x][1]);
    if(ch[x][0]) tag[ch[x][0]]^=1;
    if(ch[x][1]) tag[ch[x][1]]^=1;
    tag[x]=0;
}
inline int merge(int x,int y){
    if(!x||!y) return x+y;
    if(rnd[x]<rnd[y]){
        pushdown(x);
        ch[x][1]=merge(ch[x][1],y);
        pushup(x);return x;
    }
    else{
        pushdown(y);
        ch[y][0]=merge(x,ch[y][0]);
        pushup(y);return y;
    }
}
inline void split(int u,int k,int &x,int &y){
    if(!u) x=y=0;
    else{
        pushdown(u);
        if(siz[ch[u][0]]<k) x=u,split(ch[u][1],k-siz[ch[u][0]]-1,ch[u][1],y);
        else y=u,split(ch[u][0],k,x,ch[u][0]);
        pushup(u);
    }
}
inline void get(int u){
    if(!u) return;
    pushdown(u);
    get(ch[u][0]);
    printf("%d ",val[u]);
    get(ch[u][1]);
}
int n,m;
int main(){
    srand(time(0));scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) root=merge(root,newnode(i));
    for(int i=1;i<=m;i++){
        int l,r,x,y,z;scanf("%d%d",&l,&r);
        split(root,l-1,x,y);split(y,r-l+1,y,z);
        tag[y]^=1;
        merge(merge(x,y),z);
    }
    get(root);
    return 0;
}


月流华 岁遗沙 万古吴钩出玉匣