普通平衡树

链接

multiset失效了,我不得不去学习平衡树了,但是我偶然接触到了FHQ 平衡树,发现还不错,代码简单好理解

与AVL不同,FHQ实现的是分裂与合并操作,插入撤除都很方便,而且一般不会被特殊数据给卡住

重点函数是split和merge,split将要分裂的函数按val分裂为x和y两个部分(两棵树),merge则相反,将两棵树合并起来

这样插入操作就只需要将root按val拆开,在合并x和单独的val,接着全部一起合并即可

删除操作则将root按val-1,val拆成x,y,z三部分,这样我们只需要删除y的一个节点再全部合并就好了

至于获取排名,将root按val-1拆成x,y两部分,这样x就包含了所有小于val的数了,我们只返回x根节点的size(节点数)+1即可

然后是根据排名获取某个值,这个比较麻烦,我们需要根据root的左右节点的size和传入的rk比较,如果左孩子的size+1恰好为rk,说明root的val恰好就是答案;如果左孩子的size不小于rk的话,说明我们要找的数在左边;如果前两个都不满足,说明要找的数在右边,我们可以让rk减去左边的所有节点数,让右孩子重新作为根节点去执行这个过程

接着就是前驱和后继,前驱按val-1分裂,x的最右边就是前驱;后继按val分裂,y的最左边就是后继

#include<iostream>
#include<random>
using namespace std;
const int MAXN = 1e5 + 5;
struct Node {
	int val;
	int l, r;
	int size;
}fhq[MAXN];
int cnt, root;
int newnode(int val) {
	fhq[++cnt] = { val,0,0,1 };
	return cnt;
}
void update(int x) {
	fhq[x].size = fhq[fhq[x].l].size + fhq[fhq[x].r].size + 1;
}
void split(int now, int val, int &x, int &y) {
	if (!now) x = y = 0;
	else {
		if (fhq[now].val <= val) {
			x = now;
			split(fhq[now].r, val, fhq[now].r, y);
		}
		else {
			y = now;
			split(fhq[now].l, val, x, fhq[now].l);
		}
        update(now);
	}
	
}
int merge(int x, int y) {
	if (!x || !y) return x + y;
	if (rand() % (fhq[x].size + fhq[y].size) < fhq[x].size) {
		fhq[x].r = merge(fhq[x].r, y);
		update(x);
		return x;
	}
	else {
		fhq[y].l = merge(x, fhq[y].l);
		update(y);
		return y;
	}
}
int x, y, z;
void ins(int val) {
	split(root, val, x, y);
	root = merge(merge(x, newnode(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);
}
int getrank(int val) {
	split(root, val - 1, x, y);
	int ans = fhq[x].size + 1;
	root = merge(x, y);
	return ans;
}
int getnum(int rk) {
	int now = root;
	while (now) {
		if (fhq[fhq[now].l].size + 1 == rk) return fhq[now].val;
		if (fhq[fhq[now].l].size >= rk) now = fhq[now].l;
		else rk -= fhq[fhq[now].l].size + 1, now = fhq[now].r;
	}
	return -1;
}
int pre(int val) {
	split(root, val - 1, x, y);
	int now = x;
	while (now && fhq[now].r) now = fhq[now].r;
	int ans = fhq[now].val;
	root = merge(x, y);
	return ans;
}
int nxt(int val) {
	split(root, val, x, y);
	int now = y;
	while (now && fhq[now].l) now = fhq[now].l;
	int ans = fhq[now].val;
	root = merge(x, y);
	return ans;
}
int main() {
	srand(time(0));
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	while (n--) {
		int opt, x;
		cin >> opt >> x;
		switch (opt) {
		case 1:ins(x);break;
		case 2:del(x);break;
		case 3:cout<<getrank(x)<<'\n';break;
		case 4:cout<<getnum(x)<<'\n';break;
		case 5:cout << pre(x) << '\n';break;
		case 6:cout << nxt(x) << '\n';break;
		}
	}
}

时间复杂度:O(n log n)

空间复杂度:O(n)