非旋treap

treap是一种弱平衡树,它以用随机创造随机来使自身平衡(头铁随机数)。

treap分为非旋treap(FHQ-treap)和旋转treap,然而非旋treap有更大的应用空间

非旋treap的核心分为splitmerge

split

pair<int,int> split(int root,int val)

该操作支持将一个以给定点root为根的树分成两部分,记分成p1,p2p_1,p_2两部分

其中p1p_1内部所有节点的某种值(自定)均小于等于传入参数valp2p_2内部所有节点的某种值(自定)均大于传入参数val

split实现

这里将需要比较的值设成val

通过对比当前根rootval,如果根部的值大于参数值,则该根属于p2p_2,同时根据平衡树性质,右子树也全部属于p2p_2,但左子树未知,所以应递归分解左子树。同理,如果根部值小于等于参数值,则递归分解右子树

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; //p赋给左子树
//递归分解右子树
split(t[p].rc,val,t[p].rc,y);
}
else
{
y=p; //p赋给右子树
//递归分解左子树
split(t[p].lc,val,x,t[p].lc);
}
}

merge

int merge(int x,int y)

有分解就有合并,该操作将两棵树合并,返回合并后的根节点

注意:x,yx,y左右位置会影响结果,也就是merge(x,y)和merge(y,x)不同

merge实现

因为两个平衡树已经平衡,合并过程只需要考虑校验值的大小(即随机出的值)

这里对于校验值需要满足大根堆性质,所以若节点xx的校验值大于节点yy,则xx作为根,yy作为右节点(yy的值一定大于xx的值),同时递归分解右子树。

对于小于情况同理

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//priority作为校验值
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;
}
}

子树信息

有时我们需要统计子树的信息(比如求和,最大值等),如果两子树信息可以快速合并(像线段树一样),在splitmerge时更新子树信息即可。因为是自底向上更新,且两棵子树信息都会重新更新,所以无论是分裂后还是合并后各个子树信息都是正确的。

应用

两个核心操作已经可以完成几乎所有操作


[Luogu3369]普通平衡树

  1. 插入xx

    将原树按照xx进行split,新建一个节点,权值为xx,记为pp,合并p1,p,p2p_1,p,p_2

  2. 删除xx,删一个

    按照x1x-1进行split,得到p1,p2p_1,p_2,再将p2p_2按照xx进行split,得到p2,p3p_2,p_3,此时p2p_2只包含xx,因为要求只删一个,所以合并lsonp2,rsonp2lson_{p2},rson_{p2}覆盖p2p_2,再合并p1,p2,p3p_1,p_2,p_3

  3. 查询数值xx排名

    按照x1x-1进行split,排名即为sizep1+1size_{p1}+1

  4. 查询排名xx是哪个数

    这就需要递归去查看,因为满足二叉搜索树性质,所以左右子树跳即可,注意递归右子树需要减去左子树大小和自身

  5. xx的前驱

    按照x1x-1进行split,前驱即为p1p_1中排名最后的数,即排名sizep1size_{p1}

  6. xx的后继

    按照xx进行split,后继为p2p_2中排名第一的数(p2p_2的数全部大于xx)

可以将相同节点打上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]区间的树(先分裂一个端点再分裂另一个),将[l,r][l,r]区间的树打上标记。

注意这里仅在根节点打标记,类似懒标记的做法,每次需要向下递归之前进行下传,因为先下传再递归,故标记不会传到其他区间

下传操作需要交换左右子树,并且下传标记,注意下传用异或操作

最后按照中序遍历输出

可以可持久化,类比下一题


[Luogu3835]可持久化平衡树

非旋treap特征是无需记录父节点,所以可以可持久化

splitmerge的时候新建节点,记录root[i]表示ii版本的根部位置

注意到splitmerge操作是成对出现的,若按照权值相同节点合并,则splitmerge访问的节点一致,可以只在split时执行新建节点。

毒瘤点可以只在insertdelete操作才新建节点,会省那么一捏捏的空间(防毒瘤出题人是给玩明白了)

一定要注意空间消耗!!!

练习

[NOI2004] 郁闷的出纳员:注意查询的是第kk大(逆天人才没看懂样例)

[ZJOI2007] 报表统计

Author: cjh-hhz
Link: https://cjh-hhz.github.io/04bb231a039d.html/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.