平衡树与FHQ-Treap

平衡树（即平衡二叉搜索树），是通过一系列玄学操作让二叉搜索树（BST）处于较平衡的状态，防止在某些数据下退化（BST在插入值单调时，树形不平衡，单次会退化成 \(\mathcal{O}(n)\) ）。常见的平衡树有Treap、FHQ-Treap、Splay、AVL、红黑树等。平衡树应用广泛，可用于维护集合、数列，辅助LCT等。

FHQ-Treap是一种常数较小，码量较小，功能较多的平衡树。它通过分裂与合并操作，且在合并时根据节点的随机权值确定合并方案，来维持平衡。单次复杂度 \(\mathcal{O}(\log n)\)。

节点信息&基本操作

int s[N];//s[i]以i为根的子树大小
int r[N];//r[i]节点i的随机权值
int v[N];//v[i]节点i的权值
int ch[N][2];//ch[i][0]节点i的左儿子，ch[i][1]节点i的右儿子
int siz;//使用过的节点树，注意并不是树的大小
int rt;//根节点编号

int New(int val) {s[++siz] = 1; r[siz] = rand(); v[siz] = val; return siz;}//创建新节点，返回它的编号
void upd(int p) {s[p] = s[ch[p][0]] + s[ch[p][1]] + 1;}//更新子树大小

合并&分裂

• merge(x, y) 将以x,y为根的两棵树合并为一棵，并返回合并后的根节点编号。以x为根的树中所有任意的权值不大于以y为根的树中所有任意的权值。

我们可以用递归的方式来实现。为了达到平衡，我们需要利用随机权值。通过比较x和y节点的随机权值来确定合并方案。

1. x, y两棵树都非空时：
   
2. x,y都为空时：直接返回0。
3. x,y中一空一非空时：返回非空树的根节点，用位运算中的按位或实现。

注意以x为根的树中所有任意的权值时刻不大于以y为根的树中所有任意的权值。

int merge(int x, int y) {
	if(!x || !y) return x | y;
	return r[x] < r[y] ? (ch[x][1] = merge(ch[x][1], y), upd(x), x) : (ch[y][0] = merge(x, ch[y][0]), upd(y), y);
}

• split(p, val, x, y) 将以p为根的树分裂为两棵树，根分别是x和y。其中x树中所有节点的权值小于等于val，y树中所有节点的权值大于val。

如果节点p的权值 \(\le val\)，那么p和p的左子树的权值都 \(\le val\)，它们一定属于x树。把p节点和p的左子树一并给x，然后在p的右子树内继续分裂。

反之，如果节点p的权值 \(>val\)，那么p和p的右子树的权值都 \(>val\)，它们一定属于y树。把p节点和p的右子树一并给y，然后在p的左子树内继续分裂。

void split(int p, int val, int &x, int &y) {
	if(!p) {x = y = 0; return;}
	v[p] <= val ? (x = p, split(ch[p][1], val, ch[p][1], y)) :
	(y = p, split(ch[p][0], val, x, ch[p][0]));
	upd(p);
}

• split(p, sss, x, y) 将以p为根的树分裂为两棵树，根分别是x和y。其中x树为p树中序遍历的前sss个节点组成的树（按大小分裂）。

与按权值分裂的思想类似。当往右子树走时，要先减去左子树和根节点的大小（左子树大小+1），因为这个大小是相对以当前节点为根的子树而言的。

void split(int p, int sss, int &x, int &y) {
	if(!p) {x = y = 0; return;}
	if(sss > s[ch[p][0]]) x = p, split(ch[p][1], sss - s[ch[p][0]] - 1, ch[p][1], y);
	else y = p, split(ch[p][0], sss, x, ch[p][0]);
	upd(p);
}

插入

设插入的数为 \(val\) ，先按 \(val-1\)分裂出x和y，然后新建权值为 \(val\) 的节点p。依次合并x，p，y即可。

void insert(int val) {
	int x, y;
	split(rt, val - 1, x, y);
	rt = merge(merge(x, New(val)), y);
}

在给定位置插入：把按权值分裂改成按大小分裂就行。

in void ins(int l, char val) {//在l位置后插入值为val的节点
	int x, y;
	split(rt, l, x, y);
	rt = merge(merge(x, New(val)), y);
}

删除

设删除的数为 \(val\) ，先按 \(val\) 分裂出y和z，再将y按 \(val-1\) 分裂出x和y。如果y不为空，说明有值为 \(val\) 的数。如果只删除一个，那么将y设为y的左右儿子合并的结果，再依次合并x，y，z即可；如果删除所有值为 \(val\) 的数，直接合并x和z即可。

void erase(int val) {
	int x, y, z;
	split(rt, val, x, z);
	split(x, val - 1, x, y);
	if(y) y = merge(ch[y][0], ch[y][1]);
	rt = merge(merge(x, y), z);
}
/*
void erase_all(int val) {
	int x, y, z;
	split(rt, val, x, z);
	split(x, val - 1, x, y);
	rt = merge(x, z);
}
*/

区间删除：分裂出目标树，合并其它树就得到了删除后的树。

void eraselr(int l, int r) {
	int x, y, z;
	split(rt, r, y, z);
	split(y, l - 1, x, y);
	rt = merge(x, z);
}

查找值的排名

排名定义为比它小的数的个数加1。分裂出权值比它小的树，答案就是这棵树的大小+1。

int rank(int val) {
	int x, y, ans;
	split(rt, val - 1, x, y);
	ans = s[x] + 1;
	rt = merge(x, y);
	return ans;
}

根据排名查找值

从根节点出发，根据子树大小判断目标是否为当前节点，或要往哪里走。当往右子树走时，要先减去左子树和根节点的大小（左子树大小+1），因为这个排名是相对以当前节点为根的子树而言的。

int val(int rk) {
	int p = rt;
	while(p) {
		if(s[ch[p][0]] + 1 == rk) return v[p];
		else if(rk <= s[ch[p][0]]) p = ch[p][0];
		else rk = rk - s[ch[p][0]] - 1, p = ch[p][1];
	}
}

前驱&后继

前驱：小于 \(x\)，且最大的数

后继：大于 \(x\)，且最小的数

顺着这个思路，我们只要分裂出满足前半句话的树，然后就很容易在这棵树内得到满足后半句话的节点。

int prev(int val) {
	int x, y, tmp;
	split(rt, val - 1, x, y);
	tmp = x;
	while(ch[tmp][1]) tmp = ch[tmp][1];
	rt = merge(x, y);
	return v[tmp];
}
int next(int val) {
	int x, y, tmp;
	split(rt, val, x, y);
	tmp = y;
	while(ch[tmp][0]) tmp = ch[tmp][0];
	rt = merge(x, y);
	return v[tmp];
}

维护区间

FHQ-Treap也可以用于维护区间。如果我们让节点在真正序列中的位置满足BST性质，那么真正序列就是树的中序遍历。一般地，FHQ-Treap进行一次区间修改/查询的方法是：分裂出目标树 -> 修改/查询（一般使用类似线段树的懒标记） -> 合并。这里就要按大小分裂了。

与线段树不同的是，FHQ-Treap支持任意位置插入/删除、区间翻转等操作，但常数较大。

对于每个操作 \([l,r]\)，我们先按大小分裂出这棵目标树。方法是，先分裂出 \(y=[1,r]\) 和 \(z=[r+1,n]\)，再将y分裂出 \(x=[1,l-1]\) 和 \(y=[l,r]\)。此时的y就是目标树了。

然后，我们给y打上懒标记。注意分裂/合并时要下传标记。下传标记的方法视情况而定。

例题

• 【模板】普通平衡树

所有操作前文已讲。

#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <algorithm>

using namespace std;

#define in __inline__
#define rei register int
char inputbuf[1 << 23], *p1 = inputbuf, *p2 = inputbuf;
#define getchar() (p1 == p2 && (p2 = (p1 = inputbuf) + fread(inputbuf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
in int read() {
	register int res = 0;
	char ch = getchar();
	bool f = true;
	for(; ch < '0' || ch > '9'; ch = getchar())
		if(ch == '-') f = false;
	for(; ch >= '0' && ch <= '9'; ch = getchar())
		res = res * 10 + (ch ^ 48);
	return f ? res : -res;
}
in void write(register int x){
	static unsigned char _q[35]; register unsigned char t=0;
	for(; x; x /= 10) _q[++t] = x % 10;
	for(; t; --t) putchar(_q[t] + 48);
	putchar(32);
}
in void swap(int &x, int &y) {x ^= y ^= x ^= y;}

const int N = 1e5 + 5;
int ch[N][2], s[N], r[N], v[N], siz, rt;

int New(int val) {s[++siz] = 1; r[siz] = rand(); v[siz] = val; return siz;}
void upd(int p) {s[p] = s[ch[p][0]] + s[ch[p][1]] + 1;}

int merge(int x, int y) {
	if(!x || !y) return x | y;
	if(r[x] > r[y]) {ch[x][1] = merge(ch[x][1], y); upd(x); return x;}
	else {ch[y][0] = merge(x, ch[y][0]); upd(y); return y;}
}
void split(int p, int val, int &x, int &y) {
	if(!p) {x = y = 0; return;}
	v[p] <= val ? (x = p, split(ch[p][1], val, ch[p][1], y)) :
		(y = p, split(ch[p][0], val, x, ch[p][0]));
	upd(p);
}
in void insert(int val) {
	int x, y;
	split(rt, val - 1, x, y);
	rt = merge(merge(x, New(val)), y);
}
in void erase(int val) {
	int x, y, z;
	split(rt, val, x, z);
	split(x, val - 1, x, y);
	if(y) y = merge(ch[y][0], ch[y][1]);
	rt = merge(merge(x, y), z);
}
in int rank(int val) {
	int x, y, ans;
	split(rt, val - 1, x, y);
	ans = s[x] + 1;
	rt = merge(x, y);
	return ans;
}
in int val(int rk) {
	int p = rt;
	while(p) {
		if(s[ch[p][0]] + 1 == rk) return v[p];
		else if(rk <= s[ch[p][0]]) p = ch[p][0];
		else rk = rk - s[ch[p][0]] - 1, p = ch[p][1];
	}
}
in int prev(int val) {
	int x, y, tmp;
	split(rt, val - 1, x, y);
	tmp = x;
	while(ch[tmp][1]) tmp = ch[tmp][1];
	rt = merge(x, y);
	return v[tmp];
}
in int next(int val) {
	int x, y, tmp;
	split(rt, val, x, y);
	tmp = y;
	while(ch[tmp][0]) tmp = ch[tmp][0];
	rt = merge(x, y);
	return v[tmp];
}

int main() {
	int q = read(), opt, x, lst = 0, ans = 0;
	srand(time(0));
	for(; q; --q) {
		opt = read(), x = read();
		if(opt == 1) insert(x);
		else if(opt == 2) erase(x);
		else if(opt == 3) write(rank(x)));
		else if(opt == 4) write(val(x));
		else if(opt == 5) write(prev(x));
		else write(next(x));
	}
}

• 【模板】文艺平衡树

我们显然可以得到一个性质：同一个区间翻转偶数次等同于没有翻转。 于是我们可以利用异或运算来实现（\(0\operatorname{xor}\) 奇数次 \(1\) 得到 \(1\)，偶数次得到 \(0\)）。

暴力翻转整棵目标树就是交换每个节点的左右儿子，那么下传标记时更新左右儿子的标记，并交换左右儿子即可。

最终答案就是整棵树中序遍历得到的序列。递归输出时也要下传标记。

const int N = 1e5 + 5;
int s[N], ch[N][2], r[N], v[N], siz, rt, n, m, t[N];

in void push(int p) {
	if(!t[p]) return;
	swap(ch[p][0], ch[p][1]);
	if(ch[p][0]) t[ch[p][0]] ^= 1;
	if(ch[p][1]) t[ch[p][1]] ^= 1;
	t[p] = 0;
}
in int New(int val) {
	v[++siz] = val; s[siz] = 1; r[siz] = rand(); return siz;
}
in void upd(int p) {s[p] = s[ch[p][0]] + s[ch[p][1]] + 1;}

void print(int p) {
	if(!p) return;
	push(p);
	print(ch[p][0]);
	write(v[p]);
	print(ch[p][1]);
}

int merge(int x, int y) {
	if(!x || !y) return x | y;
	return r[x] < r[y] ? (push(x), ch[x][1] = merge(ch[x][1], y), upd(x), x) : (push(y), ch[y][0] = merge(x, ch[y][0]), upd(y), y);
}
void split(int p, int sss, int &x, int &y) {
	if(!p) {x = y = 0; return;}
	push(p);
	if(sss > s[ch[p][0]]) x = p, split(ch[p][1], sss - s[ch[p][0]] - 1, ch[p][1], y);
	else y = p, split(ch[p][0], sss, x, ch[p][0]);
	upd(p);
}

void rotate() {
	int l = read(), r = read(), x, y, z;
	split(rt, r, y, z);
	split(y, l - 1, x, y);
	t[y] ^= 1;
	rt = merge(merge(x, y), z);
}

int main() {
	srand(time(0));
	n = read(); m = read();
	for(rei i = 1; i <= n; ++i) rt = merge(rt, New(i));
	for(; m; --m) rotate();
	print(rt);
	return 0;
}

有什么问题珂以在评论区提出并吊打这个蒟蒻/kk