This is not the end.

0%

treap, 无旋treap(fhq treap)及可持久化

Posted on

treap

treap，又叫树堆。我们可以用它去维护一个序列，或者一个集合。裸的带旋的treap可以支持插入，删除，查第$k$大，查排名，以及其他的二叉搜索树的操作；无旋treap可以支持所有splay支持的操作（区间修改，翻转，覆盖，信息合并等等），操作的复杂度是$O(\log n)$的，并且不是均摊的！

关于treap的形态

它是一棵二叉树，并且，从原序列的结构上来看，它是一棵二叉搜索树，中序遍历拖出来可以得到原来的序列；而每个节点还有一个随机的权值$key$，从$key$上来看，整棵树满足堆的性质。（下面我们都假设是小根堆）

性质1：对于一个序列，每个点的$key$之间的大小关系确定的前提下，这个序列构造出来的treap是唯一的

（哦对了这个treap也是一个笛卡尔树）

我们考虑这个序列中$key$最小的那个位置，它必须是树的根（因为是堆）。然后它左边的那些位置必须在它的左子树内，右边那些位置则必须在它的右子树内（因为它是二叉搜索树）。并且它左边的、$key$最小的那个位置一定是它的左儿子（因为是堆）……这样下来，我们会发现这棵树形态是唯一确定的。

性质2：一个随机生成的长度为$n$的序列，它的笛卡尔树的高度期望是$O(\log n)$。

证明算法导论上面有，可是我太菜了看不懂qwq。

关于随机权值

LYC建议我用xorshift，因为stl自带的rand()值域小而且慢。
下面这个写法，循环节是$2^{32}-1$，$seed$初始化为一个非$0$的数就可以了。

1
2
3
4
5
6
7
#define uint unsigned int
uint seed=19260817;
uint Rand()
{
    seed^=seed<<13,seed^=seed>>17,seed^=seed<<5;
    return seed;
}

wiki上的介绍（点击References处的链接可以下载论文）

带旋treap

我没有写过呢，因为感觉它没啥用。

大概的实现原理就是，插入一个数的时候，先把这个数在叶子的位置插入（要保证满足二叉搜索树的性质），然后它的$key$可能就不满足堆的性质了，我们就可以把它向上旋转（和splay类似，旋转后二叉搜索树的性质仍然满足，而该节点和父亲的位置交换了）。删除的时候，先把这个点向下旋转到叶子（选择$key$较小的儿子把它旋上来），然后把这个点删掉。其他操作和二叉搜索树是一样的。

而且这个东西还不能支持区间操作，简直不如 01 Trie。

参考这篇blog

无旋treap

（又叫fhq treap）这是个好东西，splay支持的东西（什么区间翻转啊，区间修改啊）它都支持，而且还比splay好写，而且还可以可持久化！

它的操作依赖于两个函数：
1.split：
1）将树的中序遍历里面的前$k$个节点分离出来，形成两个treap，一个里面是前$k$个节点，另一个里面是后$n-k$个节点。
2）（如果这棵树上的节点是对于$val$满足二叉搜索树的性质）将树中$val$小于等于$x$的节点分离到第一棵treap中，将其他的节点分离到第二棵treap当中。
2.merge：将两个treap（要求第一个treap的节点的$val$，也就是我们要让它满足二叉搜索树性质的那一维，必须全部小于第二个$treap$的节点的$val$）合并为一个treap。

merge

假设第一个treap的根为$a$，第二个treap的根为$b$，那么分两种情况讨论：
1）$a$的$key$小于$b$的$key$，那么$a$应该在$b$的上面，又因为要满足二叉搜索树的性质，所以合并$a$的右儿子与$b$即可。
2）否则，合并$b$的左儿子与$a$即可。

我实在是不知道它是怎么想出来的，不过它显然是对的。

1
2
3
4
5
6
7
8
void merge(int &r,int a,int b)
{
	if(!a||!b){r=a+b; return;}
	push_down(a),push_down(b);
	if(key[a]<=key[b]) merge(ch[r=a][1],ch[a][1],b);
	else merge(ch[r=b][0],a,ch[b][0]);
	push_up(r);
}

split

分离出前$k$个节点：我们考虑根节点属于那一棵treap，这只需要判断它的左儿子的$sz$即可。
1）如果左儿子的$sz$大于等于$k$，那么根节点属于第二棵treap，并且它的右儿子全部属于第二棵treap，我们递归分离左子树。
2）否则，这个点属于第一棵treap，并且它的左子树全部属于第一棵treap，我们递归分离右子树即可。

1
2
3
4
5
6
7
void split(int x,int k,int &a,int &b)
{
	if(!x){a=b=0; return;} push_down(x);
	if(sz[ch[x][0]]>=k) split(ch[x][0],k,a,ch[b=x][0]);
	else split(ch[x][1],k-sz[ch[x][0]]-1,ch[a=x][1],b);
	push_up(x);
}

分离出权值小于等于$x$的点：同理，判断根节点属于哪一棵treap即可。

1
2
3
4
5
6
7
void splitv(int x,int v,int &a,int &b)
{
	if(!x){a=b=0; return;}
	if(val[x]<=v) a=x,splitv(ch[x][1],v,ch[x][1],b);
	else b=x,splitv(ch[x][0],v,a,ch[x][0]);
	push_up(x);
}

从上面split和merge的实现可以看出来，和两个操作的复杂度与treap的高度是同级的，而由于$key$是随机的，所以树高的期望是$O(\log n)$的，所以这两个操作的复杂度是$O(\log n)$的。

接下来我们来看一些常规的操作：

insert 插入

假如我们要在第$p$个元素后面插入一个元素，那么把前$p$个元素split出来，然后对将要新加入的元素单独建一棵树（实际上树中只有一个点），把原来的前$p$个元素，新加入的元素，后$n-p$个元素merge在一起就可以了。

而如果是要插入一段区间，我们就需要先把这个区间build成一个treap，利用单调栈维护最右链即可，代码如下：

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
int new_node(int v)
{
	int u=++ncnt;
	val[u]=v,key[u]=Rand(),push_up(u); return u;
}
int st[N],b[N],tot,p;
void build(int &r)
{
	int top; st[top=1]=b[1]=new_node(b[1]);
	for(int i=2;i<=tot;++i)
	{
		b[i]=new_node(b[i]);
		//单调栈里面维护最右链。新加的点在中序遍历中必须处在末尾，所以前面的节点如果有key比它大的，那么必须作为它的左子树
		while(top&&key[b[i]]<key[st[top]])
		    ch[b[i]][0]=st[top],push_up(st[top]),top--;
		//这里push_up的原因是，一个点出栈后，它的子树内的信息就不会再变化了，所以要及时push_up
		if(top) ch[st[top]][1]=b[i];
		st[++top]=b[i];
	}
	while(top) push_up(st[top]),top--; r=st[1];
}
//在第p个位置后面插入b数组中的tot个元素
void insert()
{
	int x,y,z; split(rt,p,x,z); build(y);
	merge(rt,x,y),merge(rt,rt,z);
}

注意对新加入的元素单独建树的时候，所有维护区间信息的变量（$sz$，$su m$之类的）要赋初值，因为我们是采取了合并的方式，要保证它是一棵合法的树。这一点和splay不一样。

维护$val$满足二叉搜索树性质的也是类似，只不过分离的是所有小于等于$v-1$的节点。

1
2
3
4
5
void insert(int v)
{
	int x,y,c=make(v); splitv(rt,v,x,y);
	merge(rt,x,c),merge(rt,rt,y);
}

delete 删除

假如要删除第$p$个元素，我们就两次split把原树分成三个部分：前$p-1$个，第$p$个，后$n-p$个。然后直接把前$p-1$个和后$n-p$个merge起来就可以了。删除一段区间也是类似的。

1
2
3
4
5
6
//下面的代码删除第p个元素开始的tot个元素，recycle是一个回收子树内所有节点的函数
void del(int p,int tot)
{
	int x,y,z; split(rt,p-1,x,z),split(z,tot,y,z);
	recycle(y); merge(rt,x,z);
}

如果是按照$val$满足二叉搜索树性质，并且可能有多个元素的$val$相同，假设我们现在要删除一个$val$等于$v$的元素，那么就把$val$等于$v$的单独分裂出来，把这棵treap根节点的左儿子和右儿子merge起来（本质上就是删掉一个节点），然后再把三棵树merge回去。

1
2
3
4
5
6
7
void del(int v)
{
	int x,y,z;
	splitv(rt,v,x,y),splitv(x,v-1,x,z);
	merge(z,ch[z][0],ch[z][1]);
	merge(rt,x,z),merge(rt,rt,y);
}

区间操作

区间修改：我们把这段区间分离出来，然后打标记就可以啦。
区间查询：我们把这段区间分离出来，返回这棵treap的根的子树信息就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//区间翻转
void Swap(int x){swap(ch[x][0],ch[x][1]),rev[x]^=1;}
void Rev(int l,int r)
{
	int x,y,z;
	split(rt,l-1,x,y),split(y,r-l+1,y,z);
	Swap(y);
	merge(rt,x,y),merge(rt,rt,z);
}
//查询从p开始的tot个元素的和
int query(int p,int tot)
{
	int x,y,z; split(rt,p-1,x,z),split(z,tot,y,z);
	int ans=sum[y].sum; merge(rt,x,y),merge(rt,rt,z);
	return ans;
}

查排名

直接将小于等于$v-1$的分离出来，返回第一棵树的$sz+1$即可。

1
2
3
4
5
6
int rnk(int v)
{
	int x,y; splitv(rt,v-1,x,y);
	int ans=sz[x]+1; merge(rt,x,y);
	return ans;
}

查前驱后继

前驱：将小于等于$v-1$的分离出来，然后返回第一棵树中最大的元素。
后继：将小于等于$v$的分离出来，然后返回第二棵树中最小的元素。
（当然也可以用二叉搜索树的写法）

1
2
3
4
5
6
7
8
9
10
11
12
13
//返回前驱，后继的节点编号
int pre(int v)
{
	int x,y,z; splitv(rt,v-1,z,y); x=z;
	while(ch[x][1]) x=ch[x][1];
	merge(rt,z,y); return x;
}
int suf(int v)
{
	int x,y,z; splitv(rt,v,y,z); x=z;
	while(ch[x][0]) x=ch[x][0];
	merge(rt,y,z); return x;
}

其他操作

和splay，二叉搜索树一样的~

模板题

普通平衡树 我的提交记录
文艺平衡树 我的提交记录
维护数列 我的提交记录

可持久化Treap

split 与 merge

split

可持久化意味着我们在操作的时候不能够修改任何的东西。

观察一下split的代码：

1
2
3
4
5
6
7
void split(int x,int k,int &a,int &b)
{
	if(!x){a=b=0; return;}
	if(sz[ch[x][0]]>=k) split(ch[x][0],k,a,ch[b=x][0]);
	else split(ch[x][1],k-sz[ch[x][0]]-1,ch[a=x][1],b);
	push_up(x);
}

我们实际上修改了什么？分离完后，第一棵树的最右链上的点的右儿子，以及第二棵树上最左链上的点的左儿子。那么我们把这些最右链和最左链上的点复制一遍，在复制的版本上修改就可以了。

1
2
3
4
5
6
void split(int x,int k,int &a,int &b)
{
	if(!x){a=b=0; return;}
	if(sz[ch[x][0]]>=k) split(ch[x][0],k,a,ch[b=cpy(x)][0]),push_up(b);
	else split(ch[x][1],k-sz[ch[x][0]]-1,ch[a=cpy(x)][1],b),push_up(a);
}

merge

还是看代码：

1
2
3
4
5
6
7
void merge(int &r,int a,int b)
{
    if(!a||!b){r=a+b; return;}
    if(key[a]<=key[b]) merge(ch[r=a][1],ch[a][1],b);
    else merge(ch[r=b][0],a,ch[b][0]);
    push_up(r);
}

我们实际上修改的，是第一棵树的最右链上的点和第二棵树最左链上的点。复制一遍即可。

1
2
3
4
5
6
7
void merge(int &r,int a,int b)
{
    if(!a||!b){r=a+b; return;}
    if(key[a]<=key[b]) r=cpy(a),merge(ch[r][1],ch[a][1],b);
    else r=cpy(b),merge(ch[r][0],a,ch[b][0]);
    push_up(r);
}

等等，真的需要复制吗？对于许多的题目，我们都是先split，然后再merge，merge的时候第一棵树的最右链和第二棵树的最左链在split的时候都已经复制过了，所以其实可以直接赋值，不再复制节点，即和普通的无旋treap一样的写法。

区间操作

有了函数式的split和merge，我们就可以可持久化带插入，单点修改，删除的无旋treap了。

但是一旦涉及到区间操作，就涉及到打标记，就很难受了。

看到网上的题解大多数是这样子实现的：下放标记的时候，把儿子节点复制一遍，像这样——

1
2
3
4
5
6
7
8
9
10
void push_down(int x)
{
	if(rev[x])
	{
		swap(ch[x][0],ch[x][1]);
		if(ch[x][0]) ch[x][0]=cpy(ch[x][0]),rev[ch[x][0]]^=1;
		if(ch[x][1]) ch[x][1]=cpy(ch[x][1]),rev[ch[x][1]]^=1;
		rev[x]=0;
	}
}

这样子显然是正确的，但是感觉空间会造成浪费。能不能直接像可持久化线段树那样，把标记永久化了呢？

答案是肯定的！我在这篇题解中介绍了它。空间和时间相对于前面的写法都要优秀一些。

复杂度

时间复杂度比较显然，单次操作是$O(\log n)$的。

但是空间复杂度，尽管单次操作是$O(\log n)$的，但是每次操作要split和merge好几次，而且本来这个树高也不是严格$\log n$的，所以我觉得TGSteven的话很有道理：数组能开多大开多大！