FHQ-Treap

简介

基于分裂与合并的 Treap。

操作

split

按权值分裂：

inline void split(int p, int k, int &x, int &y) {// p 表示当前分裂树的根节点，x,y 表示分裂成的两棵树的根节点，k 为关键字
	if(! p) return x = y = 0, void();

	if(val[p] <= k) {
		x = p;
		split(rs[p], k, rs[p], y);
	}
	else {
		y = p;
		split(ls[p], k, x, ls[p]);
	}

	psup(p);
}

按排名分裂：

inline void split(int p, int k, int &x, int &y) {
	if(! p) return x = y = 0, void();

	if(sz[ls[p]] >= k) {
		y = p;
		split(ls[p], k, x, ls[p]);
	}
	else {
		x = p;
		split(rs[p], k - sz[ls[p]] - 1, rs[p], y);
	}

	psup(p);

	return ;
}

两种写法并非完全相同，需要看要求仔细斟酌。

merge

inline int merge(int x, int y) {
	if(! x || ! y) return x | y;

	if(rnd[x] > rnd[y]) { // 考虑 x,y 谁作为根，随机优先级大的作为根
		rs[x] = merge(rs[x], y); // x 为根，将 x 原先的右子树和以 y 为根的子树合并作为新的右子树
		psup(x);

		return x;
	}
	else  {
		ls[y] = merge(x, ls[y]); // 反之，将 y 原先的左子树和以 x 为根的子树合并作为新的左子树
		psup(y);

		return y;
	}
}

• 注：根据笔者的写法，相当于是左儿子写右边，右儿子写左边的，不过无伤大雅。

扩展操作

insert

inline void insert(int p) {
	int x = 0, y = 0;

	split(root, p - 1, x, y);
	merge(merge(x, create(p)), y);
}

相当于将新增节点当一颗新树合并进去。

delete

inline void deleted(int p) {
	int x = 0, y = 0, z = 0;

	split(root, p, x, y);
	split(x, p - 1, x, z);

	z = merge(ls[z], rs[z]);
	root = merge(z, merge(x, y));

	return ;
}

分裂出只包含查询值 \(p\) 的平衡树，合并该树的左右儿子，则相当于丢掉根节点，等价于删去一个 \(p\) 元素。