FHQ_Treap

感谢Capella的技术支持

Capella's Blog


Treap

Treap是一种简单易懂还好写的平衡树,因为之前已经介绍过了,我就不不介绍了。
传送门:Treap平衡树

FHQ_Treap

又叫非旋转Treap,也就是说,它其中没有二叉查找树的旋转操作,是神犇范浩强Orz发明的一种操作极其简单的Treap平衡树,整棵树只有两种操作,分裂和合并。

合并 (merge)

顾名思义,就是把两棵树合并为一颗树。

假设两棵Treap,x和y,默认x的全部权值<y的全部权值。

注意在merge的过程中,维护好堆和二叉搜索树的性质

  • 若优先级 $x.priority<y.priority$

    维护堆的性质,则y成为x的子节点;维护二叉搜索树的性质,则y在x的右子树。

  • 若优先级 $x.priority>y.priority$

    维护堆的性质则,x成为y的子节点;维护二叉搜索树的性质,则x在y的左子树。

那么怎么实现呢?观察上面的两种情况,不难发现这是一个递归操作,将当前合并的。

给出伪代码

1
2
3
4
5
6
7
8
9
merge(x,y)
trueif x==NULL or y==NULL
truetruereturn x==NULL?y:x
trueif x.priority<y.priority
truetruex.rch=merge(x.rch,y)
truetruereturn x
trueelse
truetruey.lch=merge(x,.lch)
truetruereturn y

分裂(split)

顾名思义,就是将一棵树分裂为两个部分,一般有两种分裂方式,按值上下界分裂或者按元素秩的上下界分裂。

按值分裂

设原来Treap当前节点为node,分裂后“$<=k$的子树”为Treap x ,“$>k$的子树”为Treap y

  • 若$node.key<=k$,那么以node为根的左子树全部包含在x中

    把node给x,递归到node的右子树,x变成x的右子树,y还是y

  • 若$node.key>k$,那么以node为根的右子树全部包含在y中

    把node给y,递归到node的左子树,x还是x,y变成y的左子树

1
2
3
4
5
6
7
8
9
10
split(node,k,x,y)
trueif node==NULL
truetruex=y=NULL
trueelse
truetrueif node.key<=k
truetruetruex=node
truetruetruesplit(node.rch,k,node.rch,y)
truetrueelse
truetruetruey=node
truetruetruesplit(node.lch,k,x,node.lch)

按秩分裂

原理同上,只要判断放在哪颗Treap的时候改成k和子树的大小进行比较。

1
2
3
4
5
6
7
8
9
10
split(node,k,x,y)
trueif node==NULL
truetruex=y=NULL
trueelse
truetrueif node.lch.size < k
truetruetruex=node
truetruetruesplit(node.rch,k-node.lch.size-1,node.rch,y)
truetrueelse
truetruetruey=node
truetruetruesplit(node.lch,k,x,node.lch)

模板代码

洛谷 P3369 【模板】普通平衡树(Treap/SBT)

裸的板子题,直接建树做掉。

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

const int inf=0x7f7f7f7f;
const LL linf=0x7f7f7f7f7f7f7f7f;

class FHQ_Treap
{
private:
true
truetypedef struct TreapNode
{
truetrueint key,priority,size;
truetrueTreapNode *lch,*rch;
true}*Treap;

trueTreap root,nil;
true
trueinline long random()
{
truetruestatic int seed=19260817;
truetruereturn seed=int(seed*48271LL%2147483647);
true}

trueinline Treap creat(int x)
{
truetrueTreap node=new TreapNode;
truetruenode->size=1;
truetruenode->key=x;
truetruenode->priority=random();
truetruenode->rch=node->lch=nil;
truetruereturn node;
true}

trueinline void update(Treap node)
{
truetruenode->size = node->lch->size + node->rch->size + 1;
true}

trueTreap merge(Treap x,Treap y)//必须保证x树一定严格小于y树的
{
truetrueif(x==nil||y==nil)
truetruetruereturn x==nil?y:x;
truetrueif(x->priority < y->priority)//维护堆的性质
truetrue{
truetruetruex->rch=merge(x->rch,y);//递归向下一层层合并
truetruetrueupdate(x);//更新结点
truetruetruereturn x;
truetrue}
truetrueelse
truetrue{
truetruetruey->lch=merge(x,y->lch);
truetruetrueupdate(y);
truetruetruereturn y;
truetrue}
true}

truevoid split(Treap node,int k,Treap &x,Treap &y)//以大小为k的元素为分界点,将node树分成x和y两部分
{
truetrueif(node==nil)
truetruetruex=y=nil;
truetrueelse
truetrue{
truetruetrueif(node->key<=k)
truetruetrue{
truetruetruetruex=node;
truetruetruetruesplit(node->rch,k,node->rch,y);
truetruetrue}
truetruetrueelse
truetruetrue{
truetruetruetruey=node;
truetruetruetruesplit(node->lch,k,x,node->lch);
truetruetrue}
truetruetrueupdate(node);
truetrue}
true}

trueTreap find_rank(Treap node,int k)//根据子树统计求排名,参见《算法导论》
{
truetruewhile(1)
truetrue{
truetruetrueif(k<=node->lch->size)
truetruetruetruenode=node->lch;
truetruetrueelse if(k==node->lch->size+1)
truetruetruetruereturn node;
truetruetrueelse
truetruetrue{
truetruetruetruek-=node->lch->size+1;
truetruetruetruenode=node->rch;
truetruetrue}
truetrue}
true}

public:

trueFHQ_Treap()
true{
truetruenil=new TreapNode;
truetruenil->rch=nil->lch=nil;
truetruenil->size=0;
truetruenil->priority=2147483647;
truetrueroot=nil;
true}
true
truevoid insert(int k)
{
truetrueTreap x,y;
truetruesplit(root,k,x,y);//以将要插入的值k为分界点分裂root树为x,y两部分
truetrueroot=merge(merge(x,creat(k)),y);//将k作为单独一棵树和x,y合并为新树root
true}

truevoid erase(int k)
{
truetrueTreap x,y,z,tmp;
truetruesplit(root,k,x,z);//以要删除的k为分界点分裂root树为x,z两部分
truetruesplit(x,k-1,x,y);//以k-1分裂x
truetruetmp=y;
y=merge(y->lch,y->rch);//合并y的子树为一棵树,即删除y中的一个元素
delete tmp;
truetrueroot=merge(merge(x,y),z);//合并x,y,z
true}

trueint query_rank(int k)
{
truetrueTreap x,y,tmp;
truetruesplit(root,k-1,x,y);//以值k-1为分界点分裂树,其中0~k-1的树均处于树x中
truetrueint ans=x->size+1;
truetrueif(find_rank(y,1)->key!=k)
truetruetrueans=0;
truetrueroot=merge(x,y);//分裂后合并恢复原样
truetruereturn ans;
true}

trueint query_select(int k)
{
truetrueTreap ans=find_rank(root,k);
truetrueif(ans!=nil)
truetruetruereturn ans->key;
truetrueelse
truetruetruereturn -inf;
true}

trueint query_before(int k)
{
truetrueTreap x,y,tmp;
truetruesplit(root,k-1,x,y);//同理rank查询
truetruetmp=find_rank(x,x->size);//找到到树x的最后一个数的指针
truetrueint ans=tmp->key;//记录这个数
truetrueroot=merge(x,y);//合并恢复原样
truetruereturn ans;
true}

trueint query_after(int k)
{
truetrueTreap x,y,tmp;
truetruesplit(root,k,x,y);//按k分开,大于k的所有数被分在了y树里面
truetruetmp=find_rank(y,1);//后继结点就是y树的第一个元素
truetrueroot=merge(x,y);
truetrueint ans=tmp->key;
truetruereturn ans;
true}
}*T=new FHQ_Treap;

int main()
{
trueint n;
truescanf("%d",&n);
for(int i=1,mode,x;i<=n;i++)
{
scanf("%d%d",&mode,&x);
switch(mode)
truetrue{
truetruetruecase 1:T->insert(x);break;
truetruetruecase 2:T->erase(x);break;
truetruetruecase 3:printf("%d\n",T->query_rank(x));break;
truetruetruecase 4:printf("%d\n",T->query_select(x));break;
truetruetruecase 5:printf("%d\n",T->query_before(x));break;
truetruetruecase 6:printf("%d\n",T->query_after(x));break;
truetruetruetrue//1.插入x数
truetruetruetrue//2.删除x数(若有多个相同的数,因只删除一个)
truetruetruetrue//3.查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数,因输出最小的排名)
truetruetruetrue//4.查询排名为x的数
truetruetruetrue//5.求x的前驱(前驱定义为小于x,且最大的数)
truetruetruetrue//6.求x的后继(后继定义为大于x,且最小的数)
}
}
truedelete T;
truereturn 0;
}

例题

一些进阶的题目

关于维护序列

洛谷P3391 【模板】文艺平衡树(Splay)

这个题不是维护值的大小顺序了,是维护一个序列。我们可以用二叉搜索树中序遍历恒不变的特点,维护用Treap维护一个类似二叉搜索树的结构。利用树的中续遍历维护序列。

题目有以下要求

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,结果是5 2 3 4 1

当然用Splay和旋转Treap是可以维护的,考虑怎么用FHQ_Treap维护。

考虑一个性质,假如翻转一整颗二叉搜索树维护的序列,我们可以将这棵树连通它的所有子树的左右孩子交换,就可以将这个二叉搜索树的中序遍历从头到尾翻转。

如图

中序遍历为:1 2 3 4 5 6 7 8 9 10

完全旋转后如图

中序遍历就变成了:10 9 8 7 6 5 4 3 2 1

于是我们可以将区间分裂为x、y、z三部分,分别为[1,l-1]、[l,r]、[r+1,n],然后对y区间进行翻转。

具体的翻转呢,只要打一个tag就可以了,不翻转为0,转一次为1,转两次为0,转三次为1……

然后递归的时候下放标记就可以了。

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

const int inf=0x7f7f7f7f;
const LL linf=0x7f7f7f7f7f7f7f7f;

class FHQ_Treap
{
true
private:
true
truetypedef struct TreapNode
{
truetrueint key,priority,size;
truetrueint flag;
truetrueTreapNode *lch,*rch;
true}*Treap;

trueTreap root,nil;

trueinline long random()
{
truetruestatic int seed=19260817;
truetruereturn seed=int(seed*48271LL%2147483647);
true}

trueinline Treap creat(int x)
{
truetrueTreap node=new TreapNode;
truetruenode->size=1;
truetruenode->key=x;
truetruenode->flag=0;
truetruenode->priority=random();
truetruenode->rch=node->lch=nil;
truetruereturn node;
true}

trueinline void update(Treap node)
{
truetruenode->size = node->lch->size + node->rch->size + 1;
true}

trueinline void pushdown(Treap node)
{
truetrueswap(node->lch,node->rch);
truetrueif(node->lch!=nil)
truetruetruenode->lch->flag^=1;
truetrueif(node->rch!=nil)
truetruetruenode->rch->flag^=1;
truetruenode->flag=0;
true}

trueTreap merge(Treap x,Treap y)//必须保证x树一定严格小于y树的
{
truetrueif(x==nil||y==nil)
truetruetruereturn x==nil?y:x;
truetrueif(x->priority < y->priority)//维护堆的性质
truetrue{
truetruetrueif(x->flag)
truetruetruetruepushdown(x);
truetruetruex->rch=merge(x->rch,y);//递归向下一层层合并
truetruetrueupdate(x);//更新结点
truetruetruereturn x;
truetrue}
truetrueelse
truetrue{
truetruetrueif(y->flag)
truetruetruetruepushdown(y);
truetruetruey->lch=merge(x,y->lch);
truetruetrueupdate(y);
truetruetruereturn y;
truetrue}
true}

truevoid split(Treap node,int k,Treap &x,Treap &y)//以第k个元素为分界点,将node树分成x和y两部分
{
truetrueif(node==nil)
truetruetruex=y=nil;
truetrueelse
truetrue{
truetruetrueif(node->flag)
truetruetruetruepushdown(node);
truetruetrueif(node->lch->size < k)
truetruetrue{
truetruetruetruex=node;
truetruetruetruesplit(node->rch,k-node->lch->size-1,node->rch,y);
truetruetrue}
truetruetrueelse
truetruetrue{
truetruetruetruey=node;
truetruetruetruesplit(node->lch,k,x,node->lch);
truetruetrue}
truetruetrueupdate(node);
truetrue}
true}

truevoid dfs_output(Treap node)
{
truetrueif(node==nil)
truetruetruereturn;
truetrueif(node->flag)
truetruetruepushdown(node);
truetruedfs_output(node->lch);
truetrueprintf("%d ",node->key);
truetruedfs_output(node->rch);
true}

public:

trueFHQ_Treap()
true{
truetruenil=new TreapNode;
truetruenil->rch=nil->lch=nil;
truetruenil->size=0;
truetruenil->priority=2147483647;
truetrueroot=nil;
true}

trueinline void push_back(int x)
{
truetrueroot=merge(root,creat(x));
true}

trueinline void turn(int l,int r)
{
truetrueTreap x,y,z;
truetrue
truetruesplit(root,l-1,x,y);
truetruesplit(y,r-l+1,y,z);
truetruey->flag^=1;
truetrueroot=merge(x,merge(y,z));
true}

trueinline void output()
{
truetruedfs_output(root);
puts("");
true}
true

true
}*T=new FHQ_Treap;

int n,m;
true
int main()
{
truescanf("%d%d",&n,&m);
truefor(int i=1;i<=n;i++)
truetrueT->push_back(i);
truefor(int i=1;i<=m;i++)
true{
truetrueint l,r;
truetruescanf("%d%d",&l,&r);
truetrueT->turn(l,r);
true}
trueT->output();
delete T;
truereturn 0;
}

用结点维护区间

最典型的问题NOIP2017 Day2T3 P3960列队

关于怎么维护题目中的信息,我写的题解说明的比较清楚了,这里主要说一些细节问题。

首先是数据范围分析。

  1. 30分,可以直接开n*m数组,暴力模拟。

  2. 50分,一个结点只放一个数字,显然是不现实的,坐等MLE。

  3. 100分,用平衡树、线段树维护区间。

  4. 100分,树状数组(我反正不会)

我们考虑以往的结点size作用。

  • 当前结点为根的子树总共结点数目。

  • 当前结点为根的子树总共有多少个数字。

显然,假如是维护区间的话,第一个条件size还是满足的,但是第二个条件,我们就必须多开一个len记录了。

所以,公式:

所以,在统计元素位置的时候,找到第k个数在第t个结点上面,则将树分为x、y、z三部分,分别是[1,t-1],[t,t],[t+1,n],第k个数即为

然后就可以做了。

因为本题要建多棵平衡树,为了思路清晰,建议大家使用面向对象编程,用class把数据结构封装,以保证不会乱套。

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

const int inf=0x7f7f7f7f;
const LL linf=0x7f7f7f7f7f7f7f7f;
const int maxn=3e5+10;

class FHQ_Treap
{
private:
typedef struct TreapNode
{
LL l,r,len;
int priority,size;
TreapNode *lch,*rch;
}*Treap;

Treap root,nil;

inline long random()
{
static int seed=19260817;
return seed=int(seed*48271LL%2147483647);
}

inline void update(Treap node)
{
if(node==nil)
return;
node->len=node->lch->len+node->rch->len+(node->r-node->l+1);
node->size=node->lch->size+node->rch->size+1;
}

inline Treap creat(LL l,LL r)
{
Treap node=new TreapNode;
node->l=l,node->r=r;
node->priority=random();
node->lch=node->rch=nil;
update(node);
return node;
}

Treap merge(Treap x,Treap y)
{
if(x==nil||y==nil)
{
update(x==nil?y:x);
return x==nil?y:x;
}
if(x->priority < y->priority)
{
x->rch=merge(x->rch,y);
update(x);
return x;
}
else
{
y->lch=merge(x,y->lch);
update(y);
return y;
}
}

void split(Treap node,int k,Treap &x,Treap &y)
{
if(node==nil)
x=y=nil;
else
{
if(node->lch->size<k)
{
x=node;
split(node->rch,k-node->lch->size-1,node->rch,y);
}
else
{
y=node;
split(node->lch,k,x,node->lch);
}
update(node);
}
}

int ord(Treap node,int k)
{
if(!k)
return 0;
if(node->lch->len<k && k<=node->lch->len+(node->r-node->l+1))
return node->lch->size+1;
if(k<=node->lch->len)
return ord(node->lch,k);
else
return ord(node->rch,k-node->lch->len-(node->r-node->l+1))+node->lch->size+1;
}

public:

FHQ_Treap()
{
nil=new TreapNode;
nil->lch=nil->rch=nil;
nil->size=0;
nil->l=nil->r=nil->len=0;
nil->priority=2147483647;
root=nil;
}

void push_back(LL l,LL r)
{
root=merge(root,creat(l,r));
}

LL find_and_pop(int k)
{
Treap x,y,z;
int t=ord(root,k);
split(root,t-1,x,y);
split(y,1,y,z);
LL ans=k-x->len-1+y->l;
if(y->len>=2)
{
if(y->l==ans)
{
y->l++;
y->len--;
}
else if(y->r==ans)
{
y->r--;
y->len--;
}
else
{
Treap nodel=creat(y->l,ans-1),noder=creat(ans+1,y->r);
delete y;
y=merge(nodel,noder);
}
root=merge(merge(x,y),z);
}
else if(y->len==1)
{
delete y;
y=nil;
root=merge(x,z);
}
return ans;
}
}*Que=new FHQ_Treap[maxn],*Last_line=new FHQ_Treap;

int main()
{
int n,m,Q;
scanf("%d%d%d",&n,&m,&Q);
for(int i=1;i<=n;i++)
{
Que[i].push_back(1ll*(i-1)*m+1,1ll*i*m-1);
Last_line->push_back(1ll*i*m,1ll*i*m);
}
while(Q--)
{
int x,y;
LL ans;
scanf("%d%d",&x,&y);
if(y==m)//特判最后一列
{
ans=Last_line->find_and_pop(x);//找到并删掉这个人
Last_line->push_back(ans,ans);//扔到列尾
}
else
{
ans=Que[x].find_and_pop(y);//找到第x行第y个人并删掉
LL tmp=Last_line->find_and_pop(x);
Que[x].push_back(tmp,tmp);//删掉最后一列第x人并插入第x行行末
Last_line->push_back(ans,ans);//将这个人插入最后一列列尾
}
printf("%lld\n",ans);
}

delete [] Que;
delete Last_line;
return 0;
}