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] 报表统计