【集训整理】 旋转treap模板

---

Treap是一种弱平衡的二叉搜索树，它同时符合二叉搜索树和堆的性质：

二叉搜索树：右子节点值>父节点>左子节点

堆：子节点的优先值比父节点值小

我们让每个节点的值符合二叉搜索树的性质，同时给每个节点赋一个随机的优先值，让优先值满足堆的性质。

由于优先值是随机的，一旦不满足堆性质就会产生旋转，所以就很难出现退化成链的情况，达到平衡的效果。

Treap分为旋转Treap和无旋treap两种，旋转treap的旋转操作分为右旋和左旋：


写成代码如下：

void left_rotate(int& id) { //左旋
	int tmp = rchild[id];
	rchild[id] = lchild[tmp];
	lchild[tmp] = id;
	id = tmp;
	push_up(lchild[id]);
	push_up(id);
}

void right_rotate(int& id) { //右旋
	int tmp = lchild[id];
	lchild[id] = rchild[tmp];
	rchild[tmp] = id;
	id = tmp;
	push_up(rchild[id]);
	push_up(id);
}

旋转操作其实只涉及两个点，交换下孩子即可。

树的储存，使用数组模拟结构体：

int lchild[maxn];
int rchild[maxn];
int val[maxn],prio[maxn];
int siz[maxn], cnt[maxn];
int tot, root;

val存值，prio存节点的优先值，siz记录某节点的子节点的数量，cnt记录某节点的值出现的次数，用于处理重复元素的情况。

创建节点：

int create(int v) {
	//创建节点，并给予随机优先值
	tot++;
	val[tot] = v;
	prio[tot] = rand();
	siz[tot] = 1;
	cnt[tot] = 1;
	return tot;
}

用rand函数给prio赋随机值。

更新siz的push_up操作：

void push_up(int id) {
	//用于旋转后重新计算size
	siz[id] = siz[lchild[id]] + siz[rchild[id]] + cnt[id];
}

在旋转/插入后siz可能会变化，要push_up从下到上更新。

初始化：

void build() { //初始化，插入一个正无穷和一个负无穷
	root = create(-inf);
	rchild[root] = create(inf);
	push_up(root);
}

初始化要先往里边塞一个正无限和一个负无限节点。

插入：

在二叉查找树上找位置插入，找到树缺位或已有节点修改。每次插完都要检测符不符合堆的性质，如果不符合就用旋转的方式进行平衡。

注意，每层插入递归结束后都要进行一次push_up重新计算size值。

void insert(int& id, int v) {
	if (!id) { //找到树缺位（引用指向的变量（l/rchild）为0）
		id = create(v);
		return;
	}
	if (v == val[id]) cnt[id]++;
	else { //遍历查找树，知道找到他该在的位置
		if (v < val[id]) {
			insert(lchild[id], v);
			//每次插完都要检测符不符合堆的性质，不符合就平衡
			if (prio[id] < prio[lchild[id]]) right_rotate(id);
		}
		else {
			insert(rchild[id], v);
			if (prio[id] < prio[rchild[id]]) left_rotate(id);
		}
	}
	push_up(id); //插入后size会变，沿路更新
}