FHQ-Treap 简介

FHQ-treap 即非旋Treap，是一种短小精悍，功能丰富的平衡树。

据说它的效率介于 Treap 和 Splay 之间（可能是我的FHQ常数比较小，跑得比我的Treap还快）。

它可以实现 Splay 可以实现的所有功能，包括平衡树的基本操作和区间翻转操作。

它的实现难度比 Splay 要简单很多，没有 Splay 那么多转来转去的操作，不会令人头晕，而且FHQ代码的对称性良好，易于调试。

有两种 FHQ-Treap，一种是按值为关键字的，一种是按下标为关键字的（适用于区间翻转等操作时）。

FHQ-Treap 类似于Treap，都有一个随机的 key 值，以此来保持树的平衡。

Split (分裂) & merge (合并)

FHQ-Treap 的核心操作为 \(\text{split}\) (分裂) 和 \(\text{merge}\) (合并)。

\(\text{split}(root,val,x,y)\) 表示将 \(root\) 的子树拆分为两半，一半中的值(或下标)都小于等于 \(val\), 一半的值都大于 \(val\)。

\(\text{merge}(x,y)\) 表示将 \(x\) 子树和 \(y\) 子树合并起来，要保证x中的元素都小于y中的元素。

具体操作都是依靠 \(\text{split}\) 和 \(\text{merge}\) 来实现的。

// 按值为关键字

struct Node

{

	int l,r; // 左右儿子编号

	int val;// 真实值

	int key;// 随机值

	int size;// 子树大小

}fhq[N];

void pushup(int u){ // 维护其子树大小

	fhq[u].size = fhq[fhq[u].l].size + fhq[fhq[u].r].size + 1;

}

inline void split(int u,int val,int &x,int &y) // 递归实现

{

	if(!u) {// 空节点

		x = y = 0;

		return;

	}

	if(fhq[u].val <= val) { // 点的值大于val,递归其右儿子

		x = u;

		split(fhq[u].r,val,fhq[u].r, y);

	}

	else { // 点的值小于val,递归其左儿子

		y = u;

		split(fhq[u].l,val,x,fhq[u].l);

	}

	pushup(u); // 维护其子树大小

}

inline int merge(int x,int y)

{

	if(!x || !y) return x | y;  // 有一个子树为空，不需要操作

	if(fhq[x].key >= fhq[y].key) { // key 为随机值，这里是保证平衡的关键

		fhq[x].r = merge(fhq[x].r,y); // 将y接到右儿子或更下方上，递归合并

		pushup(x);

		return x;

	}

	else {

		fhq[y].l = merge(x,fhq[y].l);

		pushup(y);

		return y;

	}

}

insert (插入)

// 插入一个值为 val 的点

int create(int val) { // 新建一个值为val的点

	fhq[++cnt].val = val,fhq[cnt].key = rnd(),fhq[cnt].size = 1;

	return cnt;

}

void insert(int val){

	split(root,val,x,y); // 按val分裂成x,y，x中的元素都小于val，以此满足merge需要的性质

	root = merge(merge(x,create(val)), y); // 将x,新建的值为val的点，y合并

}

删除

//删除一个值为val的点

void del(int val) {

	split(root,val,x,z);

	split(x,val-1,x,y); // 前面两行将val点(y)抠出来

	y = merge(fhq[y].l,fhq[y].r); // 直接合并y的左节点和右节点，即为删除y

	root = merge(merge(x,y),z); // 合并即可

}

按值获取排名

//找到val在树中的排名

void getrank(int val) {

	split(root,val-1,x,y); // 抠出小于val的那些点(x)

	printf("%d\n",fhq[x].size+1); // x的size即为小于val的点的个数, 加上val自己即为排名

	root = merge(x,y);

}

按排名获取值

//获取排名为rank的点的值

void getval(int rank) {

	int u = root;

	while(u) {

		// fhq[fhq[u].l].size为值小于点u的点的个数

		if(fhq[fhq[u].l].size + 1 == rank) break; // 找到了!!!

		if(fhq[fhq[u].l].size >= rank) u = fhq[u].l; // 发现rank在左儿子中，递归查找左儿子

		else rank -= fhq[fhq[u].l].size + 1, u = fhq[u].r; // 发现rank在右儿子中，递归查找右儿子前要减去rank的值

	}

	printf("%d\n", fhq[u].val);

}

找前驱

// 找到小于val的最大值

void pre(int val) {

	split(root,val-1,x,y); // 先抠出小于val的值(x)

	int u = x;

	while(fhq[u].r) u = fhq[u].r; // 在小于val的值中找最大值

	printf("%d\n",fhq[u].val);

	root = merge(x,y);

}

找后继

// 找大于val的最小值

void nxt(int val) {

	split(root,val,x,y); // 先抠出大于val的值(y)

	int u = y;

	while(fhq[u].l) u = fhq[u].l; // 在大于val的值中找最小值

	printf("%d\n",fhq[u].val);

	root = merge(x,y);

}

完整板子

点击查看代码

// P3369 【模板】普通平衡树

// 因为这里加了两个哨兵，所以实现和上面介绍的有一点点区别

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

struct Node {

	int l,r;

	int val;// real value

	int key;// for treap

	int size;

} fhq[N];

int root,cnt;

mt19937 rnd(233);

int create(int val) {

	fhq[++cnt].val = val,fhq[cnt].key = rnd(),fhq[cnt].size = 1;

	return cnt;

}

void pushup(int u) {

	fhq[u].size = fhq[fhq[u].l].size + fhq[fhq[u].r].size + 1;

}

void split(int u,int val,int &x,int &y) {

	if(!u) {

		x = y = 0;

		return;

	}

	if(fhq[u].val <= val) {

		x = u;

		split(fhq[u].r,val,fhq[u].r, y);

	} else {

		y = u;

		split(fhq[u].l,val,x,fhq[u].l);

	}

	pushup(u);

}

int merge(int x,int y) {

	if(!x || !y) return x + y;

	if(fhq[x].key >= fhq[y].key) {

		fhq[x].r = merge(fhq[x].r,y);

		pushup(x);

		return x;

	} else {

		fhq[y].l = merge(x,fhq[y].l);

		pushup(y);

		return y;

	}

}

int x,y,z;

void insert(int val) {

	split(root,val,x,y);

	root = merge(merge(x,create(val)), y);

}

void del(int val) {

	split(root,val,x,z);

	split(x,val-1,x,y);

	y = merge(fhq[y].l,fhq[y].r);

	root = merge(merge(x,y),z);

}

void getrank(int val) {

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

	printf("%d\n",fhq[x].size);

	root = merge(x,y);

}

void getval(int rank) {

	rank++;

	int u = root;

	while(u) {

		if(fhq[fhq[u].l].size + 1 == rank) break;

		if(fhq[fhq[u].l].size >= rank) u = fhq[u].l;

		else rank -= fhq[fhq[u].l].size + 1, u = fhq[u].r;

	}

	printf("%d\n", fhq[u].val);

}

void pre(int val) {

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

	int u = x;

	while(fhq[u].r) u = fhq[u].r;

	printf("%d\n",fhq[u].val);

	root = merge(x,y);

}

void nxt(int val) {

	split(root,val,x,y);

	int u = y;

	while(fhq[u].l) u = fhq[u].l;

	printf("%d\n",fhq[u].val);

	root = merge(x,y);

}

int main() {

	int n;

	scanf("%d",&n);

	insert(2147483647), insert(-2147483647); // 哨兵

	while(n--) {

		int opt,val;

		scanf("%d%d",&opt,&val);

		if(opt == 1) insert(val);

		if(opt == 2) del(val);

		if(opt == 3) getrank(val);

		if(opt == 4) getval(val);

		if(opt == 5) pre(val);

		if(opt == 6) nxt(val);

	}

	return 0;

}

巴特西