fhq treap 学习笔记

(Updated: )
oi
,

序

今天心血来潮，来学习一下fhq treap（其实原因是本校有个OIer名叫fh，当然不是我）

简介

fhq treap 学名好像是“非旋转式treap及可持久化”。。。听上去怪怪的。其实就是可以代替LCT、BST等等码量很高的东东。

定义

1
2
3
struct node{
    int son[2],val,rand_val,sz;//很好理解，从左到右依次为：左右儿子编号，权值，随机权值（用处后面会讲），此节点下（包括此节点）共有多少个节点
}tr[N];

操作

最基本的操作

其实都不应该叫做操作。应该类似于维护的。。。

1
2
3
4
5
6
7
8
9
10
void update(int x){
    tr[x].sz=tr[tr[x].son[0]].sz+tr[tr[x].son[1]].sz+1;//更新节点个数，将左右子树节点个数+本节点（不要忘了。。QWQ） 
}
int new_node(int v){
    tot++;//总节点编号++
    tr[tot].sz=1;//默认为1（叶子）
    tr[tot].val=v;//权值赋值
    tr[tot].rand_val=rand();//随机rand权值
    return tot;//返回节点编号
}

基本操作

其实就三个啦。。。。

操作1:merge（默认x<y）

merge的操作其实就是把两棵树合并成一棵（真好！）。使用递归。按照rand出来的权值进行判断是左子树还是右子树。

1
2
3
4
5
6
7
8
9
10
11
12
int merge(int x,int y){
    if(!x!y) return x+y;//如果有一棵树是空的，那么就可以直接退出
    if(tr[x].rand_val<tr[y].rand_val){//按照rand的权值确定左右子树
        tr[x].son[1]=merge(tr[x].son[1],y);//将x的右儿子中merge树y
        update(x);//更新节点数
        return x;//返回
    }else{//同理
        tr[y].son[0]=merge(x,tr[y].son[0]);
        update(y);
        return y;   
    }
}

操作2:split

split的操作其实就是把一棵树拆成两棵子树。当然有两种拆法，一种是按照权值，还有一种是按照节点数分。
这里的操作2是按照权值分，操作3按照节点数分。

1
2
3
4
5
6
7
8
void split(int now,int k,int &x,int &y){//以权值k来分now树，成x,y
    if(!now) x=y=0;//如果当前操作为空树，返回空子树
    else{
        if(tr[now].val<=k) x=now,split(tr[now].son[1],k,tr[now].son[1],y);//如果小于或等于权值k，将左子树改为当前的树，并将当前的树的右子树继续往下分（把所有小于等于权值k的节点划分到一棵树当中）
        else y=now,split(tr[now].son[0],k,x,tr[now].son[0]);//同理
        update(now);//注意更新节点数
    }
}

操作3:rank

在操作2中已经说明过了，是按照节点数分（有点像其他数据结构中查找第k名的操作）

1
2
3
4
5
6
7
8
9
10
11
12
int rank(int now,int k){//在now树中，查找以权值排序的第k个节点
    while(1){
        if(k<=tr[tr[now].son[0]].sz) now=tr[now].son[0];//如果k在左子树当中那就更新
        else{
            if(k==tr[tr[now].son[0]].sz+1) return now;//正好找到
            else{//如果k在右子树当中，注意k还要减去左子树的个数+本节点
                k-=tr[tr[now].son[0]].sz+1;
                now=tr[now].son[1];
            }
        }
    }
}

普通的操作

拿一道例题来讲吧。。。
传送门
其实操作并没有高级多少（主要是想象力。。。）

操作1:插入$x$数

1
2
split(root,a,x,y);
root=merge(merge(x,new_node(a)),y);

这个比较好理解，我们先把树分为x,y两部分，然后把新的节点a看做是一棵树，先与x合并，合并完之后将合并的整体与y合并

操作2:删除$x$数(若有多个相同的数，因只删除一个)

1
2
3
4
split(root,a,x,z);
split(x,a-1,x,y);
y=merge(tr[y].son[0],tr[y].son[1]);
root=merge(merge(x,y),z);

首先我们把树分为x和z两部分
那么x树中的最大权值为a
再把x分为x和y两部分。
此时x中的最大权值为a-1，且权值为a的节点一定是y的根节点。
然后我们可以无视y的根节点，直接把y的左右孩子合并起来，这样就成功的删除了根节点，
最后再把x，y，z合并起来就好

操作3:查询$x$数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)

1
2
3
split(root,a-1,x,y);
printf("%d\n",tr[x].sz+1);
root=merge(x,y);

我们首先按照a-1的权值把树分开。
那么x树中最大的应该是a-1。
那么a的排名就是siz[x]+1

操作4:查询排名为$x$的数

//rank函数不是白吃饭的

1
printf("%d\n",tr[rank(root,a)].val);

不解释了QWQ

操作5:求$x$的前驱(前驱定义为小于$x$，且最大的数)

//rank函数真的不是白吃饭的

1
2
3
split(root,a-1,x,y);
printf("%d\n",tr[rank(x,tr[x].sz)].val);
root=merge(x,y);

因为要小于a，那么我们按照a-1的权值划分，
x中最大的一定是<=a-1的，
所以我们直接输出x中最大的数就好，
（这里有一个小技巧，因为sz储存的是节点的数目，然后根据二叉查找树的性质，编号最大的就是值最大的）

操作6:求$x$的后继(后继定义为大于$x$，且最小的数)

//rank函数真的不是白吃饭的

1
2
3
split(root,a,x,y);
printf("%d\n",tr[rank(y,1)].val);
root=merge(x,y);

因为要大于a，那么我们按照a的权值划分（取子树y），
y中最小的一定是>a的，
所以我们直接输出y中最小的数就好，
（像操作5一样这里有一个小技巧，因为sz储存的是节点的数目，然后根据二叉查找树的性质，编号最小的就是值最小的）

完整的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
#define N 100010
using namespace std;
inline int read(){
    char ch=getchar();int res=0,f=1;
    while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else{
        write(x/10);
        putchar(x%10+'0');
    }
}
struct node{
    int son[2],val,rand_val,sz;
}tr[N];
int tot=0,root=0;
void update(int x){
    tr[x].sz=tr[tr[x].son[0]].sz+tr[tr[x].son[1]].sz+1;   
}
int new_node(int v){
    tot++;
    tr[tot].sz=1;
    tr[tot].val=v;
    tr[tot].rand_val=rand();
    return tot;
}
int merge(int x,int y){
    if(!x!y) return x+y;
    if(tr[x].rand_val<tr[y].rand_val){
        tr[x].son[1]=merge(tr[x].son[1],y);
        update(x);
        return x;
    }else{
        tr[y].son[0]=merge(x,tr[y].son[0]);
        update(y);
        return y;   
    }
}
void split(int now,int k,int &x,int &y){
    if(!now) x=y=0;
    else{
        if(tr[now].val<=k) x=now,split(tr[now].son[1],k,tr[now].son[1],y);
        else y=now,split(tr[now].son[0],k,x,tr[now].son[0]);
        update(now);
    }
}
int rank(int now,int k){
    while(1){
        if(k<=tr[tr[now].son[0]].sz) now=tr[now].son[0];
        else{
            if(k==tr[tr[now].son[0]].sz+1) return now;
            else{
                k-=tr[tr[now].son[0]].sz+1;
                now=tr[now].son[1];
            }
        }
    }
}
int T,type,x,y,z,a,b;
int main(){
    srand((unsigned)time(NULL));
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&type,&a);
        if(type==1){
            split(root,a,x,y);
            root=merge(merge(x,new_node(a)),y);
        }else if(type==2){
            split(root,a,x,z);
            split(x,a-1,x,y);
            y=merge(tr[y].son[0],tr[y].son[1]);
            root=merge(merge(x,y),z);
        }else if(type==3){
            split(root,a-1,x,y);
            printf("%d\n",tr[x].sz+1);
            root=merge(x,y);
        }else if(type==4) printf("%d\n",tr[rank(root,a)].val);
        else if(type==5){
            split(root,a-1,x,y);
            printf("%d\n",tr[rank(x,tr[x].sz)].val);
            root=merge(x,y);
        }else if(type==6){
            split(root,a,x,y);
            printf("%d\n",tr[rank(y,1)].val); 
            root=merge(x,y);
        }
    }
    return 0;
}

写在最后

当然，fhqtreap的应用不仅限于这些，还有许多，还待我继续学习。。。 参考：zwfymqz
mocha从两位大佬的博文中窃取了许多。。。