投稿
  1. 高性能架构探索首页
  2. C/C++

c++ FHQ Treap

admin • • C/C++ • 阅读 129

前面我们对平衡树有了个大概的了解

关于 Treap

Treap=Binary Search Tree + Heap
二叉搜索树 + 二叉堆（一般是小根堆）
Treap 每一个节点有两个值
一个值是平衡树的值，一个值是随机的（用于堆来保持平衡）
二叉堆的性质使其保持平衡

关于 FHQ Treap

这个名字来源很简单： FHQ 大佬发明的 Treap
普通的 Treap 是通过旋转来平衡的
而 FHQ Treap 是通过合并、分裂来维护的

核心操作

约定

变量名 作用
sz[] 存储以某个节点为根的子树的节点数（包括它自己）
l[] 某个节点的左孩子
r[] 某个节点的右孩子
fix[] 维护平衡的随机值
val[] 原本树上的值
cnt 节点个数
root 当前平衡树的根节点

基本操作

很简单，看一下就可以明白了

push_up

更新节点子树的节点数，注意包括节点本身

inline void push_up(int o){
    sz[o]=sz[l[o]]+sz[r[o]]+1;
}
new_node

创建新节点，返回当前节点下标
别忘了初始化种子，不然随机数很多都一样

inline int new_node(int num){
    cnt++;
    sz[cnt]=1;
    val[cnt]=num;
    fix[cnt]=rand();
    return cnt;
}

正式开始

这两个操作都是用递归实现的
常数有点大
不过应该还是很好理解的 QwQ

分裂 Split
void split(int now,int k,int &x,int &y){
    if(!now) x=y=0;
    else{
    if(val[now]<=k) x=now,split(r[now],k,r[x],y);
    else y=now,split(l[now],k,x,l[y]);
    push_up(now); 
    }
}

void split(int now,int k,int &x,int &y){
    if(!now) x=y=0;
    else{
        int tmp=size[l[now]]+1;
        if(tmp<=k) x=now,split(r[now],k-tmp,r[x],y);
        else y=now,split(l[now],k,x,l[y]);
        push_up(now);
    }
}

一个按 val 分裂，一个按 sz 分裂，思路基本相同。
作用：把以 now 为根的子树按照权值 k 分成 x 和 y 两颗子树
分完之后权值比 k 大的都在 y 子树中，其他的都在 x 子树中
思路（以按照权值分裂为例）：

  1. 根节点为空，两个子树也为空，直接返回
  2. 根节点权值比 k 小，根节点和其左子树都给 x ，把根节点的右子树继续分成 r[x] 和 y 两颗子树
  3. 否则，根节点和其右子树都给 y ，把根节点的左子树继续分成 x 和 l[y] 两颗子树
  4. 分裂完毕，更新根节点的 sz
合并 Merge
int merge(int x,int y){
    if(!x||!y) return x+y;
    if(fix[x]<fix[y]) return r[x]=merge(r[x],y),push_up(x),x;
    return l[y]=merge(x,l[y]),push_up(y),y;
}

作用：把 x 和 y 两颗子树合并成一颗树，并返回根节点
思路：

  1. 有一颗子树为空，直接返回 x + y （如果存在，不为空的那颗子树）
  2. fix[x]<fix[y] ，为满足小根堆的性质，先将 r[x] 和 y 合并，然后更新 x 的 sz ，最后将 x 作为根节点
  3. 否则，先将 l[y] 和 x 合并，然后更新 y 的 sz ，最后将 y 作为根节点

其他操作

有了这两个核心操作已经可以干很多事了
注意：分裂的子树 x 、 y 和 z 自行定义

Insert 插入节点

作用：添加值为 val 的节点
思路：把树按照插入的值分裂成 x 和 y ，再把插入的值看成一棵树与 y 合并，再将 y 和 x 合并

inline void ins(int val){
    split(root,val,x,y);
    root=merge(x,merge(new_node(val),y));
    return;
}

还有另一种思路：直接将这颗子树与根节点合并，简单粗暴

void ins(int val){
    root=merge(root,new_node(val));
}

Delete 删除节点

作用：删除值为 val 的节点
思路：找到以要删除的节点的值所在的子树，把其左子树和右子树合并，再把所有的子树合并，这个节点就删除了。

inline void del(int val){
    split(root,val,x,z);split(x,val-1,x,y);
    y=merge(l[y],r[y]);
    root=merge(x,merge(y,z));
}

Rank 查询排名

作用：查询值为 val 再树中的排名。
思路：返回 val 左子树的 sz+1 ，记得合并

inline int rnk(int val){
    split(root,val-1,x,y);
    int ans=sz[x]+1;
    root=merge(x,y);
    return ans;
}

Kth 第 K 大

作用：查询以 o 为根节点的子树中排名为 rank 的值
思路：

  1. rank 等于当前节点左子树的 sz+1 ，直接返回 val[o]
  2. rank 小于左子树的 sz ，向左搜索， rank 不变
  3. 否则，向右搜索， rank 减去左子树的 sz+1
inline int kth(int o,int rank){
    if(rank<=sz[l[o]]) return kth(l[o],rank);
    if(rank==sz[l[o]]+1) return val[o];
    return kth(r[o],rank-sz[l[o]]-1);
}

Precursor 前驱

前驱定义：小于 x 的最大值，不存在根据题目要求
作用：查询值为 v 的前驱
思路：把树按照 v-1 分裂，如果那棵树不为空，就查询排名为 sz 的（最大），否则按照要求
注意：按照 v-1 分裂使得一棵子树全部都是小于 v 的

inline int pre(int v){
    split(root,v-1,x,y);
    int ans=sz[x]?kth(x,sz[x]):-2147483647;
    root=merge(x,y);
    return ans;
}

Successor 后继

后继定义：大于 x 的最小值，不存在根据题目要求
作用：查询值为 v 的后继
思路：把树按照 v 分裂，如果那棵树不为空，就查询排名为 1 的（最小），否则按照要求
注意：按照 v 分裂使得一棵子树全部都是大于 v 的

inline int suc(int v){
    split(root,v,x,y);
    int ans=sz[y]?kth(y,1):2147483647;
    root=merge(x,y);
    return ans;
}

高级操作

垃圾回收

由于删除节点后那个下标就空出来，以后就都没用过了，所以可以用一个数组存起来，优化空间
假设垃圾桶是 bin[] ，尾指针是 top
这时我们的 Delete 应该改动一下，把没用的下标加入队列中

inline void del(int val){
    split(root,val,x,z);split(x,val-1,x,y);
    bin[++top]=y,y=merge(l[y],r[y]);
    root=merge(x,merge(y,z));
}

增加新节点的函数也有所改动

inline int new_node(int num){
    int cur=top?bin[top--]:++cnt;
    l[cur]=r[cur]=0;
    sz[cur]=1;
    val[cur]=num;
    fix[cur]=rand();
    return cur;
}

注意：一定要把一个节点的左右儿子给清空，因为有可能之前用过

例题

洛谷 P3369

#include<bits/stdc++.h>
#define maxn 500001
using namespace std;
int sz[maxn],l[maxn],r[maxn],fix[maxn],val[maxn];
int T,cnt,n,m,x,y,z,p,a,root,bin[maxn],top;
inline int read(){
    int x=0,f=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())
        if(c=='-') f=-1;
    for(;c>'/'&&c<':';c=getchar())
        x=(x<<1)+(x<<3)+(c^48);
    return x*f;
}
inline void write(int x){
    if(x<0){x=-x;putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline void wl(int x){write(x);putchar('\n');}
inline void push_up(int x)
{
    sz[x]=1+sz[l[x]]+sz[r[x]];
}
inline int new_node(int x){
    int cur=top?bin[top--]:++cnt;
    l[cur]=r[cur]=0;
    sz[cur]=1;
    val[cur]=x;
    fix[cur]=rand();
    return cur;
}
inline void split(int now,int k,int &x,int &y){
    if(!now) x=y=0;
    else{
        if(val[now]<=k) x=now,split(r[now],k,r[x],y);
        else y=now,split(l[now],k,x,l[y]);
        push_up(now); 
    }
}
inline int merge(int x,int y){
    if(!x||!y) return x+y;
    if(fix[x]<fix[y]) return r[x]=merge(r[x],y),push_up(x),x;
    return l[y]=merge(x,l[y]),push_up(y),y;
}   
int kth(int now,int rank){
    if(sz[l[now]]+1==rank) return val[now];
    if(rank<=sz[l[now]]) return kth(l[now],rank);
    return kth(r[now],rank-sz[l[now]]-1);
}
int main(){
    srand((unsigned)time(NULL));
    T=read();
    while(T--){
        p=read();a=read();
        if(p==1){
            split(root,a,x,y);
            root=merge(merge(x,new_node(a)),y);
        }
        else if(p==2){
            split(root,a,x,z);split(x,a-1,x,y);
            bin[++top]=y;y=merge(l[y],r[y]);
            root=merge(x,merge(y,z));
        }
        else if(p==3){
            split(root,a-1,x,y);
            wl(sz[x]+1);
            root=merge(x,y);
        }
        else if(p==4) wl(kth(root,a));
        else if(p==5){
            split(root,a-1,x,y);
            wl(kth(x,sz[x]));
            root=merge(x,y);
        }
        else{
            split(root,a,x,y);
            wl(kth(y,1));
            root=merge(x,y);
        }
    }
    return 0;
}

可持久化

可持久化就是回到某一时刻进行操作，需要一个 rt[] 代替 root 存储每一时刻的根节点
我们只需将分裂劈出来的链上的每个点都 copy 一个新节点，合并的时候合并的也是新节点
这样合并时就不用新增节点了，因为合并之前肯定要分裂，而分裂已经新建好了，这样可以减少很多时间和空间
Copy 函数实现：

inline void copy(int cur,int old){
    sz[cur]=sz[old];
    val[cur]=val[old];
    l[cur]=l[old];
    r[cur]=r[old];
    fix[cur]=fix[old];
    return;
}

更改后的 Split ：

void split(int now,int k,int &x,int &y){
    if(!now) x=y=0;
    else{
        if(val[now]<=k)  {
            x=++cnt;
            copy(x,now);
        split(r[x],k,r[x],y); 
            push_up(x);
        }
        else{
            y=++cnt;
            copy(y,now);
            split(l[y],k,x,l[y]);
            push_up(y);
        }
    }
}

注意：可持久化的题输入会给你版本号 v ，记得 rt[i]=rt[v] ，并且所有操作在 rt[i] 上执行

例题

洛谷 P3835

#include<bits/stdc++.h>
#define N 500005*50
using namespace std;
inline int read(){
    int x=0,f=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())
        if(c=='-') f=-1;
    for(;c>'/'&&c<':';c=getchar())
        x=(x<<1)+(x<<3)+(c^48);
    return x*f;
}
inline void write(int x){
    if(x<0){x=-x;putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline void wl(int x){write(x);putchar('\n');}
int n,val[N],fix[N],l[N],r[N],sz[N],cnt,rt[500005];
inline int newnode(int x){
    sz[++cnt]=1;
    val[cnt]=x;
    fix[cnt]=rand();
    return cnt; 
}
inline void copy(int cur,int old){
    sz[cur]=sz[old];
    val[cur]=val[old];
    l[cur]=l[old];
    r[cur]=r[old];
    fix[cur]=fix[old];
    return;
}
inline void push_up(int x){
    sz[x]=sz[l[x]]+sz[r[x]]+1;
}
void split(int now,int k,int &x,int &y){
    if(!now) x=y=0;
    else{
        if(val[now]<=k)  {
            x=++cnt;
            copy(x,now);
        split(r[x],k,r[x],y); 
        push_up(x);
        }
        else{
            y=++cnt;
            copy(y,now);
            split(l[y],k,x,l[y]);
            push_up(y);
    }
    }
}
int merge(int x,int y){
    if(x==0||y==0) return x+y;
    if(fix[x]<fix[y]){
        r[x]=merge(r[x],y);
        push_up(x);
        return x;
    }
    else{
        l[y]=merge(x,l[y]);
        push_up(y);
        return y;
    }
}
int kth(int now,int rank){
    if(sz[l[now]]+1==rank) return val[now];
    if(rank<=sz[l[now]]) return kth(l[now],rank);
    return kth(r[now],rank-sz[l[now]]-1);
}
int main(){
    srand((unsigned)time(NULL));
    n=read();
    for(register int i=1;i<=n;i++){
    int v,opt,a,b,x,y,z;
        v=read(),opt=read(),a=read();
        rt[i]=rt[v];
        if(opt==1){
            split(rt[i],a,x,y);
            rt[i]=merge(merge(x,newnode(a)),y); 
        }
        else if(opt==2){
            split(rt[i],a,x,z);
            split(x,a-1,x,y);
            y=merge(l[y],r[y]);
            rt[i]=merge(merge(x,y),z);
        } 
        else if(opt==3){
            split(rt[i],a-1,x,y);
            wl(sz[x]+1);
            rt[i]=merge(x,y);
        }
        else if(opt==4) wl(kth(rt[i],a));
        else if(opt==5){
            split(rt[i],a-1,x,y);
            if(!sz[x]) puts("-2147483647");
            else wl(kth(x,sz[x]));
            rt[i]=merge(x,y);
        }
        else if(opt==6){
            split(rt[i],a,x,y);
            if(!sz[y]) puts("2147483647");
            else wl(kth(y,1));
            rt[i]=merge(x,y);
        } 
    }
}

区间翻转

例题

洛谷 P3391

解析

首先要知道：这颗平衡树的中序遍历为原数组
并且运用了线段树下传懒标记的思想，用数组 tag[] 记录，表示当前子树是否要翻转
意思是：这个地方做个记号，以后到这了顺便传下去，这样减少了很多次重复的翻转
传标记 down 实现:

inline void down(int x){
    if(tag[x]){
        swap(l[x],r[x]);
        if(l[x]) tag[l[x]]^=1;
        if(r[x]) tag[r[x]]^=1;
        tag[x]=0;       
    } 
}

传标记中的 swap 相当于普通翻转中的交换，根节点即为中间点
要注意，这里需要按照 sz 分裂
只需把树分成了三个部分，将中间那个子树打上标记，再把所有的合并，就实现了区间翻转了

void rev(int l,int r){
    split(root,l-1,x,y);
    split(y,r-l+1,y,z);
    tag[y]^=1;
    y=merge(y,z);
    root=merge(x,y);
}

更改后的分裂和合并
要先传标记

int merge(int x,int y){
    if(!x||!y) return x+y;
    if(fix[x]<fix[y]){
        down(x);
        r[x]=merge(r[x],y);
        push_up(x);
        return x;
    }
    else{
        down(y);
        l[y]=merge(x,l[y]);
        push_up(y);
        return y;
    }
}
void split(int now,int k,int &x,int &y){
    if(!now) x=y=0;
    else{
        down(now);
        int tmp=size[l[now]]+1;
        if(tmp<=k) x=now,split(r[now],k-tmp,r[x],y);
        else y=now,split(l[now],k,x,l[y]);
        push_up(now);
    }
}

还需要一个输出，输出树的中序遍历
这里先传标记解决了标记没传完的问题

void print(int now){
    if(!now) return;
    down(now);
    print(l[now]);
    printf("%d ",val[now]);
    print(r[now]);
}
代码
#include<bits/stdc++.h>
#define maxn 4000001
using namespace std;
int size[maxn],l[maxn],r[maxn],fix[maxn];
int val[maxn],tag[maxn];
int T,cnt,n,m,root,lt,rt;
inline int read(){
    int x=0,f=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())
        if(c=='-') f=-1;
    for(;c>'/'&&c<':';c=getchar())
        x=(x<<1)+(x<<3)+(c^48);
    return x*f;
}
inline void write(int x){
    if(x<0){x=-x;putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline void push_up(int x)
{
    size[x]=1+size[l[x]]+size[r[x]];
}
inline void down(int x){
    if(tag[x]){
        swap(l[x],r[x]);
        if(l[x]) tag[l[x]]^=1;
        if(r[x]) tag[r[x]]^=1;
        tag[x]=0;       
    } 
}
inline int new_node(int x){
    cnt++;
    size[cnt]=1;
    val[cnt]=x;
    fix[cnt]=rand();
    tag[cnt]=0;
    return cnt;
}
int merge(int x,int y){
    if(!x||!y) return x+y;
    if(fix[x]<fix[y]){
        down(x);
        r[x]=merge(r[x],y);
    push_up(x);
    return x;
    }
    else{
        down(y);
    l[y]=merge(x,l[y]);
    push_up(y);
    return y;
    }
}
void split(int now,int k,int &x,int &y){
    if(!now) x=y=0;
    else{
        down(now);
        int tmp=size[l[now]]+1;
        if(tmp<=k) x=now,split(r[now],k-tmp,r[x],y);
        else y=now,split(l[now],k,x,l[y]);
        push_up(now);
    }
}
void ins(int val){
    root=merge(root,new_node(val));
}
void print(int now){
    if(!now) return;
    if(tag[now]) down(now);
    print(l[now]);
    write(val[now]),putchar(32);
    print(r[now]);
}
void rev(int l,int r){
    int x=0,y=0,z=0;
    split(root,l-1,x,y);
    split(y,r-l+1,y,z);
    tag[y]^=1;
    y=merge(y,z);
    root=merge(x,y);
}
int main(){
    srand(time(0));
    n=read(),m=read();
    for(register int i=1;i<=n;i++) ins(i);
    while(m--){
        lt=read(),rt=read();
        rev(lt,rt);
    }
    print(root);
}

The End

原文链接: https://www.cnblogs.com/KonjakLAF/p/12759259.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    c++ FHQ Treap

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/346593

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月2日 上午3:59
下一篇 2023年3月2日 上午3:59

相关推荐