treap是一种弱平衡树，它以用随机创造随机来使自身平衡(头铁随机数)。
treap分为非旋treap(FHQ-treap)和旋转treap,然而非旋treap有更大的应用空间
非旋treap的核心分为split和merge
split
pair<int,int> split(int root,int val)
该操作支持将一个以给定点root为根的树分成两部分，记分成p1,p2两部分
其中p1内部所有节点的某种值(自定)均小于等于传入参数val，p2内部所有节点的某种值(自定)均大于传入参数val
split实现
这里将需要比较的值设成val
通过对比当前根root的val，如果根部的值大于参数值，则该根属于p2，同时根据平衡树性质，右子树也全部属于p2，但左子树未知，所以应递归分解左子树。同理，如果根部值小于等于参数值，则递归分解右子树
code
需要动态更改节点左右子树，为避免指针8字节大空间(溢出乱飞)，这里使用数组实现，用地址符更改节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void split(int p,int val,int &x,int &y)
{
if(!p) {x=y=0; return;}
if(t[p].val<=val)
{
x=p;
split(t[p].rc,val,t[p].rc,y);
}
else
{
y=p;
split(t[p].lc,val,x,t[p].lc);
}
}
|
merge
int merge(int x,int y)
有分解就有合并，该操作将两棵树合并，返回合并后的根节点
注意：x,y左右位置会影响结果，也就是merge(x,y)和merge(y,x)不同
merge实现
因为两个平衡树已经平衡，合并过程只需要考虑校验值的大小(即随机出的值)
这里对于校验值需要满足大根堆性质，所以若节点x的校验值大于节点y，则x作为根，y作为右节点(y的值一定大于x的值)，同时递归分解右子树。
对于小于情况同理
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
int merge(int x,int y)
{
if(!x||!y) return x+y;
if(t[x].priority>t[y].priority)
{
t[x].rc=merge(t[x].rc,y);
return x;
}
else
{
t[y].lc=merge(x,t[y].lc);
return y;
}
}
|
子树信息
有时我们需要统计子树的信息（比如求和，最大值等），如果两子树信息可以快速合并（像线段树一样），在split和merge时更新子树信息即可。因为是自底向上更新，且两棵子树信息都会重新更新，所以无论是分裂后还是合并后各个子树信息都是正确的。
应用
两个核心操作已经可以完成几乎所有操作
[Luogu3369]普通平衡树
-
插入x
将原树按照x进行split，新建一个节点，权值为x，记为p,合并p1,p,p2
-
删除x，删一个
按照x−1进行split，得到p1,p2，再将p2按照x进行split，得到p2,p3,此时p2只包含x，因为要求只删一个，所以合并lsonp2,rsonp2覆盖p2，再合并p1,p2,p3
-
查询数值x排名
按照x−1进行split，排名即为sizep1+1
-
查询排名x是哪个数
这就需要递归去查看，因为满足二叉搜索树性质，所以左右子树跳即可，注意递归右子树需要减去左子树大小和自身
-
x的前驱
按照x−1进行split，前驱即为p1中排名最后的数，即排名sizep1
-
x的后继
按照x进行split，后继为p2中排名第一的数(p2的数全部大于x)
可以将相同节点打上count，合并相同权值的节点，注意到对cnt加减操作需要递归查找并递归更改，不能先找到节点编号后直接对该点更改(维护size)
封装代码
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
| struct treap{
#define ls t[p].lc
#define rs t[p].rc
struct tree{
int val,priority,lc,rc,siz;
}t[mxn]; int root,p1,p2,p3,tot;
int New(int val)
{
t[++tot]=tree{val,rand(),0,0,1};
return tot;
}
void push_up(int p) {t[p].siz=t[ls].siz+t[rs].siz+1;}
void split(int p,int val,int &x,int &y)
{
if(!p) {x=y=0; return;}
if(t[p].val<=val)
{
x=p;
split(t[p].rc,val,t[p].rc,y);
}
else
{
y=p;
split(t[p].lc,val,x,t[p].lc);
}
push_up(p);
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
if(t[x].priority>t[y].priority)
{
t[x].rc=merge(t[x].rc,y);
push_up(x);
return x;
}
else
{
t[y].lc=merge(x,t[y].lc);
push_up(y);
return y;
}
}
void insert(int val)
{
split(root,val,p1,p2);
root=merge(merge(p1,New(val)),p2);
}
void erase(int val)
{
split(root,val-1,p1,p2);
split(p2,val,p2,p3);
p2=merge(t[p2].lc,t[p2].rc);
root=merge(merge(p1,p2),p3);
}
int point_rank(int val)
{
split(root,val-1,p1,p2);
int ans=t[p1].siz+1;
root=merge(p1,p2);
return ans;
}
int find_rank(int p,int ra)
{
if(t[ls].siz>=ra) return find_rank(t[p].lc,ra);
if(t[ls].siz+1==ra) return p;
else return find_rank(t[p].rc,ra-t[ls].siz-1);
}
int get_pre(int val)
{
split(root,val-1,p1,p2);
int ans=find_rank(p1,t[p1].siz);
ans=t[ans].val;
root=merge(p1,p2);
return ans;
}
int get_after(int val)
{
split(root,val,p1,p2);
int ans=find_rank(p2,1);
ans=t[ans].val;
root=merge(p1,p2);
return ans;
}
}t;
|
[Luogu3391]文艺平衡树
建立一棵以序列位置作为关键值的树，每次操作分裂出[l,r]区间的树(先分裂一个端点再分裂另一个)，将[l,r]区间的树打上标记。
注意这里仅在根节点打标记，类似懒标记的做法，每次需要向下递归之前进行下传，因为先下传再递归，故标记不会传到其他区间
下传操作需要交换左右子树，并且下传标记，注意下传用异或操作
最后按照中序遍历输出
可以可持久化，类比下一题
[Luogu3835]可持久化平衡树
非旋treap特征是无需记录父节点，所以可以可持久化
在split和merge的时候新建节点，记录root[i]表示i版本的根部位置
注意到split和merge操作是成对出现的,若按照权值相同节点合并，则split和merge访问的节点一致，可以只在split时执行新建节点。
毒瘤点可以只在insert和delete操作才新建节点，会省那么一捏捏的空间(防毒瘤出题人是给玩明白了)
一定要注意空间消耗！！！
练习
[NOI2004] 郁闷的出纳员:注意查询的是第k大(逆天人才没看懂样例)
[ZJOI2007] 报表统计
