非旋(fhq)Treap小记

以下摘自 ↑:

二叉搜索树每次操作访问O(深度)个节点。

在刻意构造的数据中，树的形态会被卡成一条链，于是复杂度爆炸

它的复杂度与直接暴力删除类似。

但二叉搜索树扩展性强。更复杂的\(splay,treap,SGT\)等都基于二叉搜索树，只是通过一些对树的形态的改变来保证操作的复杂度，且保持树中序遍历的形态。

随机数据还是很强势的。

在理解了二叉搜索树之后，我们来看非旋\((fhq)Treap\)。

既然二叉搜索树在刻意构造的数据中会被卡成一条链，那么我们可以考虑对每个结点多维护一个信息，来避免这些个情况\(w\)。

对每个结点，除了它本身的权值\(val\)之外，再附加一个权值\(pri\)，要求\(pri_k \geq pri_{son_k}\),即父亲的pri值要大于等于它的儿子的\(pri\)值,而这个\(pri\)值怎么确定呢？它是随机的，也就是rand()!

用非旋\(Treap\)实现普通平衡树，我们只需要5个函数。

一些必要的交代:

\(val[\ ]\) 节点的权值（题目给出

\(pri[ \ ]\) 节点的附加权值（\(rand()\)

\(siz[\ ]\) 节点的大小（子树+自己

\(ch[\ ][0/1]\) 节点的左/右儿子编号(动态开点

首先是非旋\(Treap\)的核心函数：

\(\mathbb{A}.{Split}\) 分裂：

\(split\)的主要思想是将原本的这棵树按照某个值\(x\)分裂成两棵，其中\(\leq x\)的为一棵，\(>x\)的为另一棵

void split(int nd,int a,int &x,int &y) {

	if(!nd) x=y=0;

	else {

		if(val[nd]>a) {

			y=nd;

			split(ch[nd][0],a,x,ch[nd][0]);

		} else {

			x=nd;

			split(ch[nd][1],a,ch[nd][1],y);

		}

		update(nd);

	}

}

其中\(nd\)表示当前节点，\(a\)表示上面所提到的某个值\(x\)，而\(x，y\)表示分裂成的两棵树的根分别是\(x,y\)。

采取递归分裂的方式，如果当前节点的\(val>a\)，根据二叉搜索树的性质，要去当前节点的左子树寻找，而可以确定另外一棵子树的根也就是当前节点\(nd\),然后我们递归的去左子树寻找，但是要注意传参的时候，传的是：\(split(ch[nd][0],a,x,ch[nd][0])\),因为我们把\(nd\)节点的左子树的一部分分裂到了另一棵树中，相应的需要改变原来的左儿子的值，让左子树中\(>x\)的部分接到\(nd\)节点的左儿子上。

如果\(val<=a\)同理。

最后我们需要更新\(nd\)节点的信息。

\(\mathbb{B}. merge\) 合并：

将两棵子树重新合并为一棵，要求\(a\)树的最大权值<=\(b\)树的最小权值(对有没有等于产生疑惑，暂且认为有吧

int merge(int a,int b) {

	if(!a||!b) return a+b;

	if(pri[a]<pri[b]) {

		ch[b][0]=merge(a,ch[b][0]);

		update(b);

		return b;

	} else {

		ch[a][1]=merge(ch[a][1],b);

		update(a);

		return a;

	}

}

如果\(a\)的随机权值要比\(b\)的小，为了满足上面“要求\(pri_k \geq pri_{son_k}\),即父亲的pri值要大于等于它的儿子的\(pri\)值”，应该将b节点作为子树的根，由于“\(a\)树的最大权值<=\(b\)树的最小权值”，所以将\(a\)与\(b\)的左儿子进行合并，合并之后得到的根作为\(b\)的左儿子,更新\(b\)。反之同理。

\(\mathbb{C}.\) 一些不是那么重要的函数：

\(\mathfrak{a}.\)基本上每个平衡树都有的找第a大：

int Kth(int a,int now) {

	while(1) {

		if(siz[ch[now][0]]>=a)

			now=ch[now][0];

		else {

			if(siz[ch[now][0]]+1==a)

				return val[now];

			else {

				a-=(siz[ch[now][0]]+1);

				now=ch[now][1];

			}

		}

	}

}

\(\mathfrak{b}.\) 新建节点

int New(int a) {

	Tcnt++;

	val[Tcnt]=a;

	pri[Tcnt]=rand();

	siz[Tcnt]=1;

	return Tcnt;

}

\(\mathfrak{c}.\) 更新

void update(int nd) {

	siz[nd]= siz[ch[nd][0]]+ siz[ch[nd][1]]+ 1;

}

这就是非旋\(Treap\)的基本函数，下面口胡一下如何完成普通平衡树的各项操作：

1.插入\(a\)数

将原树分裂成\(\leq a\)的树和\(>a\)的树，新建a节点，将新建节点与\(\leq a\)的树合并，再将两棵树合并

2.删除\(a\)数(若有多个相同的数，应只删除一个)

将树分裂成\(\leq a\)和\(>a\)的两棵，再将\(\leq a\)的分裂为\(\leq a-1\)与\(>a-1\)的（那么\(>a-1\)的树里就只有一堆a），合并\(>a-1\)树的左右子树（根就被吃掉了），然后按照分裂顺序再合并回去

3.查询\(a\)数的排名(排名定义为比当前数小的数的个数+1)

将树分裂成\(\leq a-1\)和\(>a-1\)的两棵，那么\(\leq a-1\)的树的\(siz+1\)就是a的排名

4.查询排名为\(a\)的数

直接Kth(a,root);

5.求\(a\)的前驱(前驱定义为小于\(a\)，且最大的数)

将树分裂成\(\leq a-1\)和\(>a-1\)的两棵，查询\(\leq a-1\)树中第\(siz\)大的节点编号

6.求\(a\)的后继(后继定义为大于\(a\)，且最小的数)

将树分裂成\(\leq a\)和\(>a\)的两棵，查询\(>a\)的树第一大的节点的编号

以上所有操作都一定要记得合并回去

#include<bits/stdc++.h>

using namespace std;

inline int read() {

	int ans=0;

	char last=' ',ch=getchar();

	while(ch>'9'||ch<'0') last=ch,ch=getchar();

	while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();

	if(last=='-') ans=-ans;

	return ans;

}const int mxn=100010;

int T;

int val[mxn],pri[mxn];

int ch[mxn][2],siz[mxn];

int Tcnt;

void update(int nd) {

	siz[nd]= siz[ch[nd][0]]+ siz[ch[nd][1]]+ 1;

}

int New(int a) {

	Tcnt++;

	val[Tcnt]=a;

	pri[Tcnt]=rand();

	siz[Tcnt]=1;

	return Tcnt;

}

void split(int nd,int a,int &x,int &y) {

	if(!nd) x=y=0;

	else {

		if(val[nd]>a) {

			y=nd;

			split(ch[nd][0],a,x,ch[nd][0]);

		} else {

			x=nd;

			split(ch[nd][1],a,ch[nd][1],y);

		}

		update(nd);

	}

}

int merge(int a,int b) {

	if(!a||!b) return a+b;

	if(pri[a]<pri[b]) {

		ch[b][0]=merge(a,ch[b][0]);

		update(b);

		return b;

	} else {

		ch[a][1]=merge(ch[a][1],b);

		update(a);

		return a;

	}

}

int Kth(int a,int now) {

	while(1) {

		if(siz[ch[now][0]]>=a)

			now=ch[now][0];

		else {

			if(siz[ch[now][0]]+1==a)

				return val[now];

			else {

				a-=(siz[ch[now][0]]+1);

				now=ch[now][1];

			}

		}

	}

}

int main () {

	T=read();

	int opt,a,root=0,x,y,z,w;

	while(T--) {

		opt=read();

		a=read();

		if(opt==1) {

			split(root,a,x,y);

			x=merge(x,New(a));

			root=merge(x,y);

		}

		if(opt==2) {

			split(root,a,x,y);

			split(x,a-1,z,w);

			w=merge(ch[w][0],ch[w][1]);

			z=merge(z,w);

			root=merge(z,y);

		}

		if(opt==3) {

			split(root,a-1,x,y);

			printf("%d\n",siz[x]+1);

			root=merge(x,y);

		}

		if(opt==4)

			printf("%d\n",Kth(a,root));

		if(opt==5) {

			split(root,a-1,x,y);

			printf("%d\n",Kth(siz[x],x));

			root=merge(x,y);

		}

		if(opt==6) {

            split(root,a,x,y);

            printf("%d\n",Kth(1,y));

            root=merge(x,y);

        }

	}

	return 0;

}

巴特西

非旋(fhq)Treap小记

\(\mathbb{A}.{Split}\) 分裂：

\(\mathbb{B}. merge\) 合并：

\(\mathbb{C}.\) 一些不是那么重要的函数：

最新文章

热门文章