update：2023.1.12 以前写的博客看起来太仓促了，修改了一下。update：2023.6.21 还是只会写模板的我来再修一下（其实是基本重写了一遍我以前写的什么狗屎）。第一次写是2022.8.9，现在一看都快隔着一年了，令人感慨。

(资料图)

FHQ-Treap

学习这种平衡树不需要了解 treap，据说 treap 和 splay 能干的事情他也能干，而且还支持可持久化。

FHQ-Treap 虽然名字里带 treap，但是我感觉和 treap 没有多大的关系，主要是因为 FHQ 不需要 treap 的核心操作——旋转。

而 FHQ 为了保持一个平衡的状态，通过两个基本的操作来实现其他各种操作。

前置知识二叉搜索树

一棵满足以下条件的二叉树：左子树的点的值都小于根节点的值，右子树的点的值都大于根节点的值，且左右子树都满足这个性质。

堆

一种维护数据让其最值在最上方的数据结构，比如大根堆就是大的值在上面，小的值在下面。

原理

FHQ-Treap 不是通过旋转来保持平衡的，而是通过两个函数 split 和 merge 。顾名思义，split 就是分裂，merge 就是合并。当然，从最底层的原理来看，还不是这两个函数。FHQ-Treap 中的 Treap 代表 Tree + Heap，也就是说，FHQ-Treap 会按二叉搜索树一样根据键值排序结点，并且随机赋给每个结点一个优先级，按照二叉堆的顺序排序结点（这里用大根堆其实大根堆小根堆都一样，都是为了保持平衡）。Treap 通过旋转，使平衡树同时满足这两个性质，从而达到平衡。而FHQ-Treap 通过调用 merge 函数时使平衡树满足堆序，实现原理与 Treap 不同，这也是为什么我上面说不用了解 Treap 的原因。

变量与函数

先看一下定义的数组：

int ch[N][2], val[N], siz[N], key[N], cnt;int T, rt = 0;inline void push_up(int x) {siz[x] = 1 + siz[ch[x][0]] + siz[ch[x][1]];}inline int node(int x){cnt++;siz[cnt] = 1;val[cnt] = x;key[cnt] = rand();return cnt;}

其中 ch表示当前结点的左右儿子的编号，\(0\) 是左儿子，\(1\) 是右儿子。

val是结点存储的值，siz是以当前点为根的子树大小，key是我们赋的随机权值。

push_up主要是用于更新 siz，因为在 FHQ 中查找有关排名之类的操作都是需要用到 siz来判断的，所以主要是更新子树的大小。

node函数的含义就是新开一个点，里面的 key要赋随机权值，在初始化完之后要返回当前点的编号。

分裂与合并按值分裂

我们先来看一下代码：

inline void split(int x, int k, int &xx, int &yy){if(! x) return xx = yy = 0, void();if(val[x] <= k) xx = x, split(ch[x][1], k, ch[x][1], yy);else yy = x, split(ch[x][0], k, xx, ch[x][0]);push_up(x);return ;}

函数里面的参数，x是当前点的编号，k是分裂的权值，也就是我们现在是把小于等于 k的结点分为一棵子树，大于 k的结点分为一棵子树；xx,yy是我们分裂出来的两棵树的根结点。

根据二叉搜索树的性质，我们首先是判断当前点的值是不是小于等于 k，如果成立则把当前 xx替换成 x，也就是当前结点，表示当前结点被划分到左边的子树中，然后在往下递归，因为当前点的左子树的值肯定小于等于 x的权值，所以也成立，在左子树，而右子树的不一定会成立，所以我们去判断右子树。

如果要是当前点的值大于 k的话，我们就直接把他给分给右子树，也就是把 yy替换成 x，然后继续递归。

我们重复上面的步骤，如果当前点是空的就直接返回不属于任何一个结点的子节点，也就是在递归回去的过程中把分裂完后子节点为空的结点的 ch给更新掉。

图片来自OI—Wiki。

按排名分裂

其实和上面的是差不多的，就是把值改成了排名，在判断的时候用的是 siz。

inline void split2(int x, int k, int &xx, int &yy){if(! x) return xx = yy = 0, void();if(siz[ch[x][0]] + 1 <= k) xx = x, split(ch[x][1], k - size[ch[x][0]] - 1, ch[x][1], yy);else yy = x, split(ch[x][0], k, xx, ch[x][0]);push_up(x);return ;}

要注意在当前点被分到 xx的时候，我们需要将 k减去 siz[x] + 1，因为我们在往下是到右子树去找，所以之前左子树占掉的排名个数要减去。

合并

先来看代码：

inline int merge(int x, int y){if(! x || ! y) return x + y;if(key[x] > key[y]){ch[x][1] = merge(ch[x][1], y);push_up(x);return x;}else {ch[y][0] = merge(x, ch[y][0]);push_up(y);return y;}}

我们在合并的时候，就要考虑来满足堆的性质了，让随机权值最大的点在上面。

因为两个分裂出来的子树已经有序，所以我们在合并的时候只需要考虑把哪个树「放在上面」，把哪个「放在下面」，也就是是需要判断将哪个一个树作为子树。显然，根据堆的性质，我们需要把 key值大的放在上面（上面说过里默认用大根堆）

同时，我们还需要满足搜索树的性质，所以若 xx的根结点的 key小于 yy的，那么 xx即为新根结点，并且 yy因为 val值比 xx更大，应与 xx的右子树合并；反之，则 yy作为新根结点，然后因为 xx的 val值比 yy小，与 yy的左子树合并。

其他操作插入点

split(rt, a, x, y);rt = merge(merge(x, node(a)), y);

我们把当前的整棵树按照给定的点的权值给分开，然后新开一个点，将其与 x合并后再与 y合并即可。

删除点

split(rt, a, x, z);split(x, a - 1, x, y);y = merge(ch[y][0], ch[y][1]);rt = merge(merge(x, y), z);

我们把小于等于 a的点给分出来，然后从这棵子树里面把小于等于 a-1的点给分出来，也就是我们相当于 y中的结点全是等于 a的，然后我们把左右儿子合并就把一个值为 a的点给删掉了，然后合并起来即可。

查询给定值的排名

split(rt, a - 1, x, y);cout << siz[x] + 1 << endl;rt = merge(x, y);

我们先把小于等于 a-1，也就是小于 a的值都给分出来，然后以他为根的子树大小就是当前 a值的排名了。

查询给定排名的值

inline int get_rank(int x, int k){while(1){if(k <= siz[ch[x][0]]) {x = ch[x][0]; continue;}if(k == siz[ch[x][0]] + 1) return x;else k -= siz[ch[x][0]] + 1, x = ch[x][1];}}

这个没有什么好方法，只能暴力找，但由于我们平衡树的优良结构，复杂度是 \(O(\log n)\) 的。

查询前驱

split(rt, a - 1, x, y);cout << val[get_rank(x, siz[x])] << endl;rt = merge(x, y);

我们把小于等于 a-1的点也就是小于 a的点给分出来然后直接查询我们的 x中最后一个点的序号然后输出对应值即可。

查询后继

split(rt, a, x, y);cout << val[get_rank(y, 1)] << endl;rt = merge(x, y);

跟上面的原理差不多，我们只不过是在大于 a的结点的子树中找了第一个大于 a的点。

P3369【模板】普通平衡树

#include #define int long long#define N 500100using namespace std;int ch[N][2], val[N], siz[N], key[N], cnt;int T, rt = 0;inline int read(){int x=0,f=1;char ch=getchar();while(ch<"0"||ch>"9"){if(ch=="-")f=-1;ch=getchar();}while(ch>="0"&&ch<="9"){x=x*10+ch-"0";ch=getchar();}return x*f;}inline void push_up(int x) {siz[x] = 1 + siz[ch[x][0]] + siz[ch[x][1]];}inline int node(int x){cnt++;siz[cnt] = 1;val[cnt] = x;key[cnt] = rand();return cnt;}inline int merge(int x, int y){if(! x || ! y) return x + y;if(key[x] > key[y]){ch[x][1] = merge(ch[x][1], y);push_up(x);return x;}else {ch[y][0] = merge(x, ch[y][0]);push_up(y);return y;}}inline void split(int x, int k, int &xx, int &yy){if(! x) return xx = yy = 0, void();if(val[x] <= k) xx = x, split(ch[x][1], k, ch[x][1], yy);else yy = x, split(ch[x][0], k, xx, ch[x][0]);push_up(x);return ;}inline void split2(int x, int k, int &xx, int &yy){if(! x) return xx = yy = 0, void();if(siz[ch[x][0]] + 1 <= k) xx = x, split(ch[x][1], k - siz[ch[x][0]] - 1, ch[x][1], yy);else yy = x, split(ch[x][0], k, xx, ch[x][0]);push_up(x);return ;}inline int get_rank(int x, int k){while(1){if(k <= siz[ch[x][0]]) {x = ch[x][0]; continue;}if(k == siz[ch[x][0]] + 1) return x;else k -= siz[ch[x][0]] + 1, x = ch[x][1];}}signed main(){srand((unsigned)time(NULL));T = read();while(T --){int op = read(), a = read(), x, y, z;if(op == 1){split(rt, a, x, y);rt = merge(merge(x, node(a)), y);}if(op == 2){split(rt, a, x, z);split(x, a - 1, x, y);y = merge(ch[y][0], ch[y][1]);rt = merge(merge(x, y), z);}if(op == 3){split(rt, a - 1, x, y);cout << siz[x] + 1 << endl;rt = merge(x, y);}if(op == 4) cout << val[get_rank(rt, a)] << endl;if(op == 5){split(rt, a - 1, x, y);cout << val[get_rank(x, siz[x])] << endl;rt = merge(x, y);}if(op == 6){split(rt, a, x, y);cout << val[get_rank(y, 1)] << endl;rt = merge(x, y);}}return 0;}