平衡树Splay与FHQ

树剖的未来会补的（卑微）。

这里想讲讲平衡树，因为看着高级，可以证明我学过OI。

我们先了解下 /(BST/)，也就是平衡二叉树。

他的概念是，对于每一个非叶子结点，他的左儿子一定小于当前节点，右儿子必定大于当前节点。

类似于如下图，就是一个好看的 /(BST/)：

那我们现在对平衡二叉树有了深入的了解了，我们就开始进行平衡树的讲解。

一：平衡树解决的问题类型：

1.插入（删除）一个数

2.查询某个数的排名

3.查询某个排名所对应的数

4.查询某个数的前驱（后驱）

二：Splay

1.rotate 操作

分为左旋和右旋，我们偷一张图看一下：

我们将 x 右旋，就是将 x 的父亲 (y) 变成 x 的右儿子，x 的右儿子变成 y 的左儿子，x 变为 R 的右儿子。

我们将 y 左旋，得到的结果和上面一样。

那么我们可以轻松写出 rotate 函数了：

inline void rotate(int x) {
	int idx = check(x);//x作为y的哪个儿子
		int f = tree[x].f, idf = check(f);//y和y作为R的哪个儿子
		int sonx = tree[x].son[idx ^ 1];//x的儿子（与x作为的儿子反着）
		int ff = tree[f].f;//y的父亲
		
		connect(sonx, f, idx);//将x的儿子变成y的儿子
		connect(f, x, idx ^ 1);//将x的父亲变成x的儿子
		connect(x, ff, idf);//将x变为原来y的父亲的对应儿子
		
		update(f);
		update(x);//修改当前节点子树的大小
}

2.splay 函数

Splay 的核心，不然也不配命名为 splay。

主要就是进行旋转，将 u 转到 v 的上。

那么我们分三种情况：

1.v 是 u 的父亲，如下图：

我们只需要将 u 转一下即可：

2.u 作为 u 的父亲 k 的左（右）儿子， k 也作为 k 的父亲 v 的左（右）儿子，如下图:

我们需要先旋转 k，再旋转 u：

3.u 作为 u 的父亲 k 的左（右）儿子， k 也作为 k 的父亲 v 的右（左）儿子，如下图：

我们需要连选 2 次 u：

那么这样，我们可以很容易得到 splay 函数的代码：

inline void splay(int u, int v) {
	int fv = tree[v].f;
		
	while (fv != tree[u].f) {
		int fu = tree[u].f;
			
		if (fv == tree[fu].f) rotate(u);//v的父亲是u的父亲的父亲，即v是u的父亲		
		else if (check(u) == check(fu)) rotate(fu), rotate(u);//u和u的父亲分别同属于他们父亲的同种儿子
		else rotate(u), rotate(u);//与上面相反
	}
}

3.处理操作

1.插入：

那么是很显然的，只需要判断是否是相同的数即可。

相同的数，直接在频率上加一即可，否则建立新节点。

代码如下：

inline int add(int x, int fa) {
	tree[++ siz].data = x;
	tree[siz].f = fa;
	tree[siz].cnt = tree[siz].sum = 1;

	return siz;
}//添加一个节点

void push(int x) {
	int sign = 0, nxt;

	tot ++;

	if (! root) root = add(x, 0);//总得先有根节点吧……
	else {
		int now = root;

		while (now) {
			tree[now].sum ++;

			if (tree[now].data == x) {
				tree[now].cnt ++, sign = now;

				break; 
			} //已经有过这个数字，就将cnt++，位置标记

			nxt = tree[now].data < x ? 1 : 0;

			if (! tree[now].son[nxt]) {
				sign = tree[now].son[nxt] = add(x, now);

				break;
			}//这个节点还没有数字，就将这个数字差到当前节点

			now = tree[now].son[nxt];
		}
	}

	splay(sign, root);
}

2.删除：