[TOC]
二叉搜索树(BST)
BST 是一种常用的数据结构，每个节点储存着一个可以比较大小的权值，并且其满足如下性质：对于任意节点 u，其左子树（如果存在）内所有节点的权值均小于 u 的权值，其右子树（如果存在）内所有节点的权值均大于 u 的权值。
不难发现这棵树可以做很多事情：这棵树的中序遍历就是排好序的序列，并且可以很方便的进行插入删除和查找操作（只需层层递归即可），同时可以统计一个元素的排名（只需看左边有多少节点）。
然而，如果插入的序列是一个递增的序列，则 BST 的复杂度可以退化到 O(n)，这样的话查找一个元素的复杂度和在线性表内查找就没有什么区别了，需要进行优化。
不难发现，对于一个集合，如果我们将他建构成一棵 BST，可以有很多情况，而很明显地：左右平衡的结构是相对比较优的，这样子的话操作的期望复杂度为 O(\log n)，达到了我们的目的。
下面学习一些比较常用的可以使 BST 平衡的手法
Treap
简介
Treap=Tree+Heap，是一种相对好写的平衡 BST（简称平衡树），从其命名可以看出来它是一个堆（Heap) 与 BST（Tree）的结合体。
Treap 有如下性质：
- 是一棵关于元素值 val 的 BST
- 是关于权值 priority（一般是随机的）的堆（小根大根没什么区别）
- val 和 priority 确定时，Treap 唯一
这样随机给元素分配权值可以使得 Treap 不容易退化成链，使查找/插入/删除/第 k 大/排名的操作都是 O(\log n) 的。
Initialization
首先是 Treap 的数组形式定义（指针太难写了而且容易出奇奇怪怪的 bug）
struct treap
{
int ch[2];//存储左/右儿子的编号
int cnt,size;//存储当前元素的数量和子树大小
int val,p;//val为元素值，p为随机权值
}t[maxn];
下面操作类似于线段树的 pushup，主要是下面信息改变后维护子树大小用
#define L t[u].ch[0]
#define R t[u].ch[1]
inline void maintain(int u)
{
t[u].size=t[u].cnt+t[L].size+t[R].size;
return;
}
旋转
接下来了解一下 Treap 的核心操作：旋转。
Treap 的旋转操作只需要实行一次，说人话就是为了保持堆的性质，将某节点的儿子旋转上来，同时要使树仍满足 BST 的性质，怎么实现呢？看下图：
画图理解后，代码就比较容易写了：d 是旋转方式，0 为旋转左儿子上来（右旋），1 则反之亦然。
void rotate(int &x,int d)// x 引用是为了方便修改，一般传进来的参就是 t[u].ch[x]
{
int k=t[x].ch[d];//要旋转上来的节点
t[x].ch[d]=t[k].ch[d^1];
t[k].ch[d^1]=x;
maintain(x);//这里一定要先维护 x
maintain(x=k);//然后将 x 的值改变，并维护之
}
注意 x 和 k 的维护顺序，因为 k 的 size 是要从 x 那里更新来的，所以要先处理好儿子的结果。
插入/删除
插入操作。直接从根开始，二分查找到对应位置，如果已经存在则 ++cnt，如果不存在就新建节点。
void insert(int &u,int val)
{
if(!u)//如果 val 不存在
{
u=++cnt;//开一个新节点
t[u].size=t[u].cnt=1;
t[u].val=val;
t[u].p=rand();//随机一个权值
return;
}
t[u].size++;//因为加到子树里面了，所以 ++size
if(t[u].val==val)//找到了就直接增加cnt
{
t[u].cnt++;
return;
}
int d=t[u].val<val;//比较巧妙的写法，待插入值大的话就是1，对应右儿子，反之亦然
insert(t[u].ch[d],val);
if(t[u].p>t[t[u].ch[d]].p)//维护小根堆，如果插入后破坏了堆的性质
rotate(u,d);//就把对应儿子旋上来
return;
}
删除操作。比较难搞，遇到一个节点的时候分为如下情况：
- 当前节点不是待删除节点，递归儿子查找删除
- 当前节点是待删除节点但是个数大于 1，个数– 然后返回
- 当前节点是待删除节点且个数为 1
- 至少有一个儿子为空：把另外一个儿子翻上来，然后直接丢掉自己
- 两个儿子都不为空：把随机权值较低的儿子翻上来，然后化为 1 情况继续递归
void delnode(int &u,int val)
{
if(!u)return;//访问到空了
if(t[u].val==val)//找到待删除节点
{
if(t[u].cnt>1)//多于一个就只删除一个
{
t[u].cnt--;
t[u].size--;
return;
}
int d=t[L].p>t[R].p;
if((!L)||(!R))//如果左或右有至少一边为空
u=L+R;//直接把非空的赋给 u
else rotate(u,d),delnode(u,val);//否则就把随机权值更小的儿子翻上来，然后递归处理
}
else t[u].size--,delnode(t[u].ch[t[u].val<val],val);//size--，然后递归到儿子里面删除
}
查询排名/第 k 大/小
查询排名操作。这个就比较简单了，同时也是我们为什么要维护每个节点的 size。看代码即能理解：
int rank(int u,int val)
{
if(!u)return 1;//如果到了空节点，返回 1，因为排名可以排到 1
if(t[u].val==val)//如果找到了对应的数
return t[L].size+1;//返回左儿子的大小加 1
if(t[u].val>val)//如果当前节点大于待查找
return rank(L,val);//递归查找左儿子
else return rank(R,val)+t[L].size+t[u].cnt;//这里比较容易错，因为需要加上左儿子和节点本身产生的贡献
}
查询第 k 小/大。这里实现查询第 k 小，理解了排名操作基本就能写出来了。值得注意的是这里既可以递归操作，也可以直接迭代写出来。
递归：
int kth(int u, int k)
{
if (!u)
return 0;
int lsize = L ? t[L].size : 0;
if (k <= lsize)
return kth(L, k);
else if(k <= lsize + t[u].cnt)
return t[u].val;
else return kth(R, k - t[u].cnt - lsize);//k要减去贡献
}
非递归：
int kth(int k)
{
int u=root;//从根节点开始向下查找
while (true)
{
if(k<=t[L].size)//如果待查询的 k 小于左子树大小
u=L;//往左走
else if(k>t[L].size+t[u].cnt)//如果大于了左边和本身产生的贡献
k-=t[L].size+t[u].cnt,u=R;//首先 k 要减去贡献，然后再往右走
else return t[u].val;//否则就是找到了，直接返回即可
}
}
前驱后继/完整代码
前驱和后继。前驱的定义为“小于 x 的最大的数”。为了满足“小于 x”，如果当前节点大于等于 x，则在左儿子里面查找。但如果发现了小于 x 的数，为了满足“最大的数”，要在其右子树里面继续查找，结合代码会更好理解。
int pre(int u,int val)
{
if(!u)//查到了空节点
return -inf;//就返回一个不会对答案产生贡献的 -inf
if(t[u].val>=val)//如果不满足“小于 val“ 的性质
return pre(L,val);//就在左儿子里面找
return max(pre(R,val),t[u].val);//取max是为了处理万一右儿子不存在
}
int nxt(int u,int val)//与前驱同理
{
if(!u)
return inf;
if(t[u].val<=val)
return nxt(R,val);
return min(nxt(L,val),t[u].val);
}
所以 洛谷 P6136 的代码如下（省略了一些不关键的定义）：（建议不要提交 P3369，有很多问题没有考虑到的 Treap 是可以通过那道题的，建议交加强版）
#include <cstdio>
#include <cctype>
#include <climits>
#include <cstdlib>
#define L t[u].ch[0]
#define R t[u].ch[1]
inline int read()
{
char c = getchar();
int s = 0;
bool x = 0;
while (!isdigit(c))
x = x | (c == '-'), c = getchar();
while (isdigit(c))
s = 10 * s + c - '0', c = getchar();
return x?-s:s;
}
inline int max(int a,int b){return a > b? a : b;}
inline int min(int a,int b){return a < b? a : b;}
const int maxn = 2e6+5, inf = INT_MAX-20;
int cnt, root, lastans = 0, ans = 0;
struct treap
{
int ch[2];
int val, p;
int size, cnt;
} t[maxn];
inline void maintain(int u)
{
t[u].size = t[u].cnt + t[L].size + t[R].size;
return;
}
inline void rotate(int &u, int d)
{
int k = t[u].ch[d];
t[u].ch[d] = t[k].ch[d ^ 1];
t[k].ch[d^1] = u;
maintain(u);
maintain(u = k);
return;
}
void insert(int &u, int val)
{
if (!u)
{
u = ++cnt;
t[u].size = t[u].cnt = 1;
t[u].val = val;
t[u].p = rand();
return;
}
t[u].size++;
if (t[u].val == val)
{
t[u].cnt++;
return;
}
int d = val > t[u].val;
insert(t[u].ch[d], val);
if (t[t[u].ch[d]].p < t[u].p)
rotate(u, d);
return;
}
void delnode(int &u,int val)
{
if (!u)
return;
if (t[u].val == val)
{
if (t[u].cnt > 1)
{
t[u].cnt--;
t[u].size--;
return;
}
if ((!L) || (!R))
u = L + R;
else
{
int d = t[L].p > t[R].p;
rotate(u, d);
delnode(u, val);
}
}
else
t[u].size--, delnode(t[u].ch[val > t[u].val], val);
return;
}
int rank(int u,int val)
{
if (!u)
return 1;
if (val == t[u].val)
return t[L].size + 1;
if (val < t[u].val)
return rank(L, val);
else return rank(R, val) + t[L].size + t[u].cnt;
}
int kth(int u, int k)
{
if (!u)
return 0;
int lsize = L ? t[L].size : 0;
if (k <= lsize)
return kth(L, k);
else if(k <= lsize + t[u].cnt)
return t[u].val;
else return kth(R, k - t[u].cnt - lsize);
}
int pre(int u, int val)
{
if (!u)
return -inf;
if (t[u].val >= val)
return pre(L, val);
else return max(t[u].val, pre(R, val));
}
int suc(int u, int val)
{
if (!u)
return inf;
if (t[u].val <= val)
return suc(R, val);
else return min(t[u].val, suc(L, val));
}
int main()
{
int n = read(), m = read();
srand(20041031);
while (n--)
insert(root, read());
while (m--)
{
int opt = read(), x = read() ^ lastans;
switch (opt)
{
case 1:
insert(root, x);
break;
case 2:
delnode(root, x);
break;
case 3:
ans ^= (lastans = rank(root, x));
break;
case 4:
ans ^= (lastans = kth(root, x));
break;
case 5:
ans ^= (lastans = pre(root, x));
break;
case 6:
ans ^= (lastans = suc(root, x));
break;
}
}
printf("%d\n", ans);
return 0;
}
FHQ-Treap（无旋 Treap）
由范浩强大佬发明的神级数据结构，相比于 Treap 不用旋转，且增添了两个核心操作：分裂（split）与合并（merge），这两个操作是无旋 Treap 的核心操作，其余的所有操作都是基于 split 和 merge 的。
两个值相同的元素是分别储存在两个不同的节点里面的，不像 Treap 的 cnt 域
分裂
该操作把一棵 Treap 分裂成两棵，有两种分裂方法：按值分裂以及按大小分裂。这里先考虑按值分裂。
该种分裂方式按照一个阈值 k 把一棵 Treap 分裂成两棵，满足左树的所有元素值均小于等于 k，右树的所有元素值均大于 k。由于 Treap 满足堆的性质，所以直接分裂即可，不需要特殊维护。
一般来说 split() 函数使用递归实现：void split(int u, int k, int &x, int &y)，其中 u 表示当前节点，k 不再赘述，两个引用 x 和 y 是放返回值（即分裂出来的左树的根和右树的根）的。
void split(int u, int k, int &x, int &y)
{
if (!u)
x = y = 0;
else
{
if (t[u].val <= k)
{
x = u;
split(R, k, R, y);
}
else
{
y = u;
split(L, k, x, L);
}
maintain(u);
}
return;
}
接下来解释一下上面的代码：
首先如果这个节点不存在，就不能再继续了，直接 x = y = 0; 即可。
然后如果这个节点的值小于等于 k，则这个节点肯定是划到左树里面去了，所以有 x = u;，然后对于这个节点的左子树，肯定是被划到左子树里面去的，所以继续分裂右子树，即 split(R, k, R, y);。如果无法理解，下面来看看具体步骤：
这是一棵分裂前的 FHQ-Treap（省略了节点编号和随机权值，只保留了值），让我们以阈值 7 将其分裂。一开始 split(root, 7, x, y)
首先我们找到树根 6，6 \le 7，所以划到左树里面，同时它的左子树也都属于左树。（属于左树的节点标红）
接下来 split(R, k, R, y) 即 split(10的编号, 7, t[6].ch[1], y) 现在来到节点 10，注意到 10 > 6，所以 10 划给右树，10 的所有右节点也都划给右树：此时 y 就被赋为 10 的编号。
然后 split(L, k，x, L) 即 split(8的编号, 7, t[6].ch[1], t[10].ch[0])，8 > 7
接下来 split(L, k, x, L) 即 split(7的编号, 7, t[6].ch[1], t[8].ch[0])，发现 7 \le 7，所以划到左子树，并且 x=u，即把 t[6].ch[1] 赋为 7，
然后 split(R, k, R, y) 即 split(0, 7, t[7].ch[1], t[8].ch[0])，发现节点不存在，将 x 和 y 都赋为 0，返回即可。这样就完成了分裂。
总结一下：
- 遇到比小于等于阈值的节点，由于其左子树一定划为左树，所以要继续分裂右子树，传下去左树的根是当前节点的右儿子，在更深的递归层会更新。
- 遇到大于阈值的节点，同理，分裂左子树，传下去右树的根是当前节点的左儿子，在更深的递归层会更新
这个递归可能一开始不太好理解，但是理解了会发现其实挺简单的。
合并
合并的时候是把两棵 FHQ-Treap x 和 y 合并成一棵，必须满足：x 中所有节点的值小于等于 y 中所有节点的值，然后合并的结果也要满足 Treap 的性质（即堆的性质）。
合并函数 int merge(int x, int y) 返回合并后的树根，x,y 分别为两棵待合并树的根。由于要维护堆的性质，实现如下：
int merge(int x, int y)
{
if (!x || !y)
return x + y;
if (t[x].key < t[y].key)
{
t[x].ch[1] = merge(t[x].ch[1], y);
maintain(x);
return x;
}
else
{
t[y].ch[0] = merge(x, t[y].ch[0]);
maintain(y);
return y;
}
}
首先如果两棵树的其中一棵为空，则直接返回另一棵的根即可。
然后维护一个小根堆（小根大根其实无所谓），如果发现左边子树根（x）的权小一些，说明是 x 做父亲，将其右子树与 y 合并的结果作为其右子树即可，合并完记得 pushup 一下就行了。
反之亦然，将 y 的左子树与 x 合并的结果作为 y 的左子树即可，注意传参的顺序：先传左树后传右树
还是比较好理解的。学习完了两个基本操作，就可以很轻松的实现插入删除排名 k\text{th} 前驱后继等操作了。
插入
值得注意的是，FHQ-Treap 在处理相同值的时候是单独开新节点的，不像一般的 Treap 维护 cnt 域。
核心思想就是以待插入值为阈值分裂成树 x，y，然后将 x，新节点和 y 合并即可。
void insert(int val)
{
t[++cnt].val = val;//开新节点
t[cnt].key = rnd();//随机分配权
t[cnt].size = 1;
int x, y;//临时变量
split(root, val, x, y);//按照 val 分裂
root = merge(merge(x, cnt), y);//先合并 x 和新节点，再将结果与 y 合并
return;
}
删除
这个操作比较精妙：考虑删除 val，先将整棵树分裂成 x，y，z 三棵树，满足：x 中所有节点值均小于 val，y 中均等于 val，z 中均大于 val。这时候我们发现要删除一个 val 就只需要拿掉 y 的根节点就可以了，其等价于直接合并 y 的左右子树。
void delnode(int val)
{
int x, y, z;
split(root, val - 1, x, y);//按照 val-1 分裂出 x 树
split(y, val, y, z);//再按照 val 分裂出 y 和 z
y = merge(t[y].ch[0], t[y].ch[1]);//直接拿掉 y 的根
root = merge(merge(x, y), z);//再复原就可以了
return;
}
排名/第 k 大/小
查询排名很类似于删除操作，但只需要分裂出小于 val 的树然后返回其大小加一的值即可。
int rank(int val)
{
int x, y;
split(root, val - 1, x, y);
int ans = t[x].size + 1;
root = merge(x, y);
return ans;
}
然而查询 k\text{th} 时就不能分裂/合并了，老老实实按照大多数平衡树的写法就可以了，建议非递归，常数小一些。
int kth(int k)
{
int u = root;
while (true)
{
int lsize = 0;
if (L)
lsize = t[L].size;
if (k <= lsize)
u = L;
else if (k > lsize + 1)
k -= lsize + 1, u = R;
else return t[u].val;
}
}
前驱/后继
前驱：小于 x 且最大的数，所以利用排名和 k\text{th} 即可。查找 x 的排名然后输出对应该排名减一的数即可。
后继：查找 x+1 的排名然后输出该排名对应的数即可
int pre(int val)
{
return kth(rank(val) - 1);
}
int suc(int val)
{
return kth(rank(val + 1));
}
普通平衡树的实现
可以发现代码明显短于一般 Treap 和 Splay，但常数大于 Treap 小于 Splay。关键是特别好写好背
洛谷 P6136 的代码如下：
#include <cstdio>
#include <cctype>
#include <cstdlib>
const int maxn = 1e6 + 2e5;
inline int read()
{
char c = getchar();
int s = 0;
bool x = 0;
while (!isdigit(c))
x = x | (c == '-'), c = getchar();
while (isdigit(c))
s = 10 * s + c - '0', c = getchar();
return x?-s:s;
}
struct node
{
int size;
int ch[2];
int val, key;
#define L (t[u].ch[0])
#define R (t[u].ch[1])
} t[maxn];
int cnt, root;
inline void pushup(int u)
{
t[u].size = t[L].size + t[R].size + 1;
return;
}
void split(int u, int k, int &x, int &y)
{
if (!u)
{
x = y = 0;
return;
}
if (t[u].val <= k)
{
x = u;
split(R, k, R, y);
}
else
{
y = u;
split(L, k, x, L);
}
pushup(u);
return;
}
int merge(int x, int y)
{
if (!x || !y)
return x + y;
if (t[x].key < t[y].key)
{
t[x].ch[1] = merge(t[x].ch[1], y);
pushup(x);
return x;
}
else
{
t[y].ch[0] = merge(x, t[y].ch[0]);
pushup(y);
return y;
}
}
void insert(int val)
{
t[++cnt].val = val;
t[cnt].key = rand();
t[cnt].size = 1;
int x, y;
split(root, val, x, y);
root = merge(merge(x, cnt), y);
return;
}
void delnode(int val)
{
int x, y, z;
split(root, val - 1, x, y);
split(y, val, y, z);
y = merge(t[y].ch[0], t[y].ch[1]);
root = merge(merge(x, y), z);
return;
}
int rank(int val)
{
int x, y;
split(root, val - 1, x, y);
int ans = t[x].size + 1;
root = merge(x, y);
return ans;
}
int kth(int k)
{
int u = root;
while (true)
{
int lsize = 0;
if (L) lsize = t[L].size;
if (k <= lsize)
u = L;
else if (k > lsize + 1)
k -= lsize + 1, u = R;
else return t[u].val;
}
}
int pre(int val)
{
return kth(rank(val) - 1);
}
int suc(int val)
{
return kth(rank(val + 1));
}
int main()
{
int n = read(), m = read(), ans = 0, lastans = 0;
srand(20041031);
while (n--)
insert(read());
while (m--)
{
int opt = read(), x = read() ^ lastans;
switch (opt)
{
case 1:
insert(x);
break;
case 2:
delnode(x);
break;
case 3:
ans ^= (lastans = rank(x));
break;
case 4:
ans ^= (lastans = kth(x));
break;
case 5:
ans ^= (lastans = pre(x));
break;
case 6:
ans ^= (lastans = suc(x));
break;
}
}
printf("%d\n", ans);
return 0;
}
按大小分裂/文艺平衡树的实现
FHQ-Treap 还有另外一种分裂方式：按大小分裂，将一棵 FHQ-Treap 分裂成 x，y，满足 x 的大小为给定值。这样子分裂能够让我们更好更方便地处理区间问题，下面以文艺平衡树为例：
首先是分裂函数：
void split(int u, int size, int &x, int &y)
{
if (!u)
{
x = y = 0;
return;
}
pushdown(u);
if (t[L].size < size)
x = u, split(R, size - t[L].size - 1, R, y);
else
y = u, split(L, size, x, L);
pushup(u);
return;
}
基本和一般的按值分裂是差不多的，只不过要注意的就是如果要继续分裂右子树，传下去的 size 值是需要改变的。
剩下的也没什么了，对于要翻转区间 [l,r]，直接分裂成三棵树。具体地，按照 l-1 分裂成 x 和 y，再将 y 按照 r-l+1 分裂成 y 和 z，此时 y 树就是提取出来的区间 [l,r]，打上标记即可。
实现文艺平衡树的时候需要特别注意标记的下传，实现如下，比 Splay 简洁且不容易写错。
#include <cstdio>
#include <cctype>
#include <cstdlib>
const int maxn = 100000+5;
inline int read()
{
char c = getchar();
int s = 0;
bool x = 0;
while (!isdigit(c))
x = x | (c == '-'), c = getchar();
while (isdigit(c))
s = 10 * s + c - '0', c = getchar();
return x ? -s : s;
}
struct node
{
int ch[2];
int size;
int val, key;
bool tag;
#define L (t[u].ch[0])
#define R (t[u].ch[1])
} t[maxn];
int cnt, root;
inline void pushup(int u)
{
t[u].size = t[L].size + t[R].size + 1;
return;
}
inline void pushdown(int u)
{
if (t[u].tag)
{
int tmp = L; L = R; R = tmp;
t[L].tag ^= 1, t[R].tag ^= 1;
t[u].tag = 0;
}
return;
}
void split(int u, int size, int &x, int &y)
{
if (!u)
{
x = y = 0;
return;
}
pushdown(u);
if (t[L].size < size)
x = u, split(R, size - t[L].size - 1, R, y);
else
y = u, split(L, size, x, L);
pushup(u);
return;
}
int merge(int x, int y)
{
if (!x || !y)
return x + y;
if (t[x].key < t[y].key)
return pushdown(x), t[x].ch[1] = merge(t[x].ch[1], y), pushup(x), x;
else
return pushdown(y), t[y].ch[0] = merge(x, t[y].ch[0]), pushup(y), y;
}
int newnode(int val)
{
t[++cnt].val = val;
t[cnt].key = rand();
t[cnt].size = 1;
return cnt;
}
void reverse(int l, int r)
{
int x, y, z;
split(root, l - 1, x, y);
split(y, r - l + 1, y, z);
t[y].tag ^= 1;
root = merge(merge(x, y), z);
return;
}
void dfs(int u)
{
if (!u)
return;
pushdown(u);
dfs(L);
printf("%d ", t[u].val);
dfs(R);
return;
}
int main()
{
int n = read(), m = read();
for (int i = 1; i <= n; ++i)
root = merge(root, newnode(i));
while (m--)
{
int l = read(), r = read();
reverse(l, r);
}
dfs(root);
return 0;
}
可见 100 行出头就写完了，比 Splay 好写太多了。
维护区间时的一个 trick
当我们在使用 FHQ-Treap 维护一段序列时，有时需要快速找出某元素在序列中的位置，怎么办呢？
此时可以在建树时记录下这个元素在树中的节点编号，然后在找寻其排名时自底而上记录在它左边的节点个数。具体可以这样：
int getrank(int u)
{
int ret = t[L].size + 1;
while (t[u].fa)
{
if (t[t[u].fa].ch[1] == u)
ret += t[t[t[u].fa].ch[0]].size + 1;
u = t[u].fa;
}
return ret;
}
对于一个节点 u，首先它的排名就是其左子树大小加一，然后往上跳，在跳的过程中判断一下它是父亲节点的左儿子还是右儿子，如果是右儿子的话，父亲本身和其兄弟节点都会产生贡献，一路搜到根即可。
同时 pushup 的时候要更新父亲，pushup 一个节点的时候顺带更新其两个儿子的父亲（需要判断是否存在）
inline void pushup(int u)
{
t[u].size = 1;
if (L)
t[u].size += t[L].size, t[L].fa = u;
if (R)
t[u].size += t[R].size, t[R].fa = u;
return;
}
相关题目 [ZJOI2006]书架、[CQOI2014]排序机械臂，当然这些题都可以用 Splay 解决。
启发式合并
此处的合并与之前的 merge 操作不同，此处合并的两棵树就是两棵一般的树，不能简单地直接 O(\log n) 合并。此时我们能做的就是将小树暴力递归加入到大树中，复杂度 O(\log^2 n)。具体实现如下：
void insert(int &root, int u)//表示将 u 节点加入 root 为根的新树中
{
int x, y;
int val = t[u].val;
split(root, val, x, y);
root = merge(merge(x, u), y);
return;
}
void dfs(int u, int &root)//这个 root 的引用是新树的树根
{
if (!u)
return;
dfs(L, root);//先把左子树加入
dfs(R, root);//加入右子树
L = R = 0;//清空儿子，这一步不写会出问题
insert(root, u);//再加入自己
return;
}
int join(int x, int y)
{
if (t[x].size > t[y].size)
swap(x, y);
dfs(x, y);//使 x 成为小树然后递归加入 y 中
return y;//返回新的根 y
}
相关试题 [HNOI2012]永无乡
易错点
- 分裂代码不背错就行
- 涉及到分裂完合并的时候一定记得更新根！！即
root = merge(...) - 类似第二点，删除节点过程中合并 y 的左右子树的时候千万记得更新 y 的值
- 涉及到子树的操作千万提前 pushdown
Splay
简介/Initialization
相较于两种 Treap，Splay（伸展树）则稍微难写一点，Splay 的核心操作就是 splay：即把一个节点旋转到根的位置，以此维护树的平衡。它相较于 Treap 的优点就是可以处理区间信息以及快速合并/分裂（虽然 fhqTreap 也能做到）。
Splay 具有一切 BST 具有的性质，其相较于 Treap 的区别就是它是双旋的，这样可以保证均摊复杂度 O(\log n)（证明要用势能分析，我太菜暂时不会）。首先看下结构体如何定义：
struct Splay
{
int ch[2], fa;//与 treap 不同之处在于 splay 需要记录父亲节点的编号
int cnt, size;
int val;
} t[maxn];
处理旋转的时候是需要知道这个节点是父亲的左儿子还是右儿子的，如下：
inline bool get(int u)
{
return t[t[u].fa].ch[1] == u;
}
旋转后与 Treap 一样需要维护 size
inline void maintain(int u)
{
t[u].size = t[u].cnt + t[L].size + t[R].size;
return;
}
旋转/伸展（Splay）
接下来就是该死的旋转操作了：考虑将 x 节点旋转到 fa 的位置，（令 fa 的父节点为 gfa）图示如下：
这是一开始的情况，首先判断 x 是其父亲的哪个儿子，定义 d_1 为 0 表示是左儿子，1 为右儿子，然后把其父亲的 d_1 儿子变成 t[x].ch[d1^1]，如下，此时由于 d_1=0，所以 d1^1 为右儿子：
接下来用 x 连接 gfa，代替 fa 的位置
最后把 x 与 fa 接起来就可以了（即 t[x].ch[d1^1]=fa）
这样，一次旋转操作就完成了，它完成的就是将一个节点往上旋转到其父亲的位置。代码如下：
void rotate(int u)
{
int fa = t[u].fa, gfa = t[fa].fa;
int d1 = get(u), d2 = get(fa);
t[fa].ch[d1] = t[u].ch[d1 ^ 1], t[t[u].ch[d1 ^ 1]].fa = fa;
if (gfa)
t[gfa].ch[d2] = u;
t[u].fa = gfa;
t[fa].fa = u, t[u].ch[d1 ^ 1] = fa;
maintain(fa);//最后不忘维护，注意先维护 fa，理由同 treap
maintain(u);
}
接下来就是 splay 过程了，splay 操作的目的就是将指定节点旋转到根节点，一次操作分为六种情况：
- 如果 x 的父亲为根，则旋转一次
- 如果 x 的父亲不为根，且 x 和 fa 的儿子类型相同（即“三点共线”，代码中就是
get()函数返回值相同），那么首先左/右旋 fa，再左/右旋 x（两次单旋的方向相同） - 如果在第二种情况种，x 和 fa 的儿子类型不同，则将 x 旋转两次，先左/右再右/左旋（两次单旋的方向不同）
”三点共线“的情况见下图：6 为 x，3 为 fa，2 为 gfa。
可见我们先右旋 fa，得到如下结果：
接下来再右旋 x，得到：
三点不共线的情况如下图：
此时 x=6，fa=4，gfa=2，现在对 x 先进行一次右旋：
再对 x 进行一次左旋：
反复执行如上操作，直到 x 成为根后，整个 splay 过程就结束了。
下面的 splay(u,goal) 意为把 u 节点伸展到 goal 节点的儿子处（goal=0 就是使 u 变成根节点）
void splay(int u, int goal)
{
while (t[u].fa != goal)//一直伸展
{
int fa = t[u].fa, gfa = t[fa].fa;//找到父亲和爷爷
int d1 = get(u), d2 = get(fa);//找到 u 是什么儿子，fa 是什么儿子。左0右1
if (gfa != goal)//如果爷爷不是根，则需要旋转两次，下面是旋转第一次
{
if (d1 == d2)//如果三点共线
rotate(fa);//先旋转 fa
else
rotate(u);//否则先旋转 u
}
rotate(u);//第二次旋转
}
if (goal == 0)//如果 u 成为根了
root = u;//更新根的值
}
插入
插入操作就比较简单了，由于 Splay 的形态是可以改变的，所以不需要递归。每插入一个元素都进行一次 Splay 操作让其变为根
void insert(int val)
{
int u = root, fa = 0;
while (u && t[u].val != val)
fa = u, u = t[u].ch[t[u].val < val];//往下走
if (u)//如果节点已经存在
t[u].cnt++;
else
{
u = ++cnt;//否则新开节点
if (fa)//如果自己不是根
t[fa].ch[t[fa].val < val] = u;
t[u].fa = fa;
t[u].size = t[u].cnt = 1;
t[u].val = val;
}
splay(u, 0);//为了降低均摊复杂度，需要将新插入的节点 splay 到根
}
排名/第 k 小/大
由于 Splay 的形态可以改变，因此在查询排名的时候可以直接将其 splay 到树根，然后统计左子树大小再 +1 就可以了。当然首先需要找到对应的数在哪里，下面先实现 find(int val) 函数，它返回刚好等于 val 的节点的编号（如果存在的话），不存在则返回一个叶子节点（手玩一下便知它返回的要么是前驱要么是后继，但不一定是与 val 的值最接近的节点，但是一定可以保证返回的排名是正确的）。然后 rank() 函数的实现就相当简单了：
int find(int val)
{
int u = root;
while (t[u].val != val && t[u].ch[t[u].val < val])
u = t[u].ch[t[u].val < val];
return u;
}
int rank(int val)
{
splay(find(val), 0);//先把对应节点旋转到根
return t[t[root].ch[0]].size + 1;//直接根的左子树大小加 1
}
需要注意的是如果查询排名的数不存在的话会出一些奇奇怪怪的问题，所以在写加强版模板的时候推荐使用下面的写法：
int rank(int val)
{
insert(val);
int ans = t[t[root].ch[0]].size + 1;
delnode(val);
return ans;
}
第 k 小。类似递归的查找即可，注意查询右子树的时候要减去本身和左子树的贡献：
int kth(int k)
{
int u = root;
while (true)
{
if (k <= t[L].size)//如果第 k 小在左子树中
u = L;
else if (k > t[L].size + t[u].cnt)//如果第 k 小在右子树中
{
k -= t[L].size + t[u].cnt;//减去 L 和 u 产生的贡献
u = R;
}
else
return t[u].val;//否则就是自己了，返回即可
}
}
前驱后继/删除
同排名操作，考虑直接把 val 节点翻到根。此时前驱要么就是根节点，要么就是左子树中最靠右的节点。由 find() 函数的性质，如果 val 存在，则前驱一定在左子树里面的最右边，如果 val 不存在，则翻上来的点要么是前驱要么是后继，如果小于 val 就直接返回，大于 val 则和第一种情况一样，在左子树里面的最右边。
而后继几乎同理。不难写出如下代码：
int getnxt(int val, int opt)//opt=0 是前驱，1 是后继
{
splay(find(val), 0);//先把对应节点翻到根
int u = root;
if (t[u].val < val && (!opt))//如果要找前驱并且根就是前驱，直接返回即可
return u;
if (t[u].val > val && opt)//同理，要查找后继并且根就是后继
return u;
u = t[u].ch[opt];//否则到左/右子树查找
while (t[u].ch[opt ^ 1])//查找最右/左边的节点
u = t[u].ch[opt ^ 1];
return u;
}
注意这个函数返回的是前驱/后继在树中的编号，为什么要这样呢，为了下面的删除操作。
删除一个数时，注意我们如果将其 splay 到根的话，会发现左右子树不好处理。怎么办呢，把前驱旋转到根，然后把后继翻到前驱的下面，此时 splay() 函数的 goal 参数就体现出它的作用了。
不难发现，此时 $val$ 一定是后继节点的左儿子，如图（回想一下前驱和后继的定义，你会发现确实是这样的）：
问题现在就很简单了，只需要删除掉 suc 的左儿子就可以了，如果有多个那就 cnt-- 并把对应节点 splay 到根，只有一个就把 suc 的左儿子设为空即可。现在知道为什么上面前驱和后继的函数返回的是节点编号了吧
void delnode(int val)
{
int pre = getnxt(val, 0);
int suc = getnxt(val, 1);
splay(pre, 0);
splay(suc, pre);//把后继旋转到前驱的儿子
if(t[t[suc].ch[0]].cnt > 1)
{
t[t[suc].ch[0]].cnt--;
splay(t[suc].ch[0], 0);//不忘再splay一次
}
else t[suc].ch[0] = 0;
return;
}
普通平衡树的实现
唯一要注意的就是一开始需要先插入正负无穷，然后算出来的排名要减一，查询的 k 要加一
#include <cstdio>
#include <cctype>
#define L t[u].ch[0]
#define R t[u].ch[1]
inline int read()
{
char c = getchar();
int s = 0;
bool x = 0;
while (!isdigit(c))
x = x | (c == '-'), c = getchar();
while (isdigit(c))
s = 10 * s + c - '0', c = getchar();
return x ? -s : s;
}
inline int max(int a, int b) { return a > b ? a : b; }
inline int min(int a, int b) { return a < b ? a : b; }
const int maxn = 1e5 + 5, inf = 0x3f3f3f3f;
int cnt, root;
struct Splay
{
int ch[2], fa;
int cnt, size;
int val;
} t[maxn];
inline bool get(int u)
{
return t[t[u].fa].ch[1] == u;
}
inline void maintain(int u)
{
t[u].size = t[u].cnt + t[L].size + t[R].size;
return;
}
void rotate(int u)
{
int fa = t[u].fa, gfa = t[fa].fa;
int d1 = get(u), d2 = get(fa);
t[fa].ch[d1] = t[u].ch[d1 ^ 1], t[t[u].ch[d1 ^ 1]].fa = fa;
t[gfa].ch[d2] = u, t[u].fa = gfa;
t[fa].fa = u, t[u].ch[d1 ^ 1] = fa;
maintain(fa);
maintain(u);
}
void splay(int u, int goal)
{
while (t[u].fa != goal)
{
int fa = t[u].fa, gfa = t[fa].fa;
int d1 = get(u), d2 = get(fa);
if (gfa != goal)
{
if (d1 == d2)
rotate(fa);
else
rotate(u);
}
rotate(u);
}
if (goal == 0)
root = u;
}
void insert(int val)
{
int u = root, fa = 0;
while (u && t[u].val != val)
fa = u, u = t[u].ch[t[u].val < val];
if (u)
t[u].cnt++;
else
{
u = ++cnt;
if (fa)
t[fa].ch[t[fa].val < val] = u;
t[u].fa = fa;
t[u].size = t[u].cnt = 1;
t[u].val = val;
}
splay(u, 0);
}
int find(int val)
{
int u = root;
while (t[u].val != val && t[u].ch[t[u].val < val])
u = t[u].ch[t[u].val < val];
return u;
}
int rank(int val)
{
splay(find(val), 0);
return t[t[root].ch[0]].size + 1;
}
int kth(int k)
{
int u = root;
while (true)
{
if (k <= t[L].size)
u = L;
else if (k > t[L].size + t[u].cnt)
{
k -= t[L].size + t[u].cnt;
u = R;
}
else
return t[u].val;
}
}
int getnxt(int val, int opt)
{
splay(find(val), 0);
int u = root;
if (t[u].val < val && (!opt))
return u;
if (t[u].val > val && opt)
return u;
u = t[u].ch[opt];
while (t[u].ch[opt ^ 1])
u = t[u].ch[opt ^ 1];
return u;
}
void delnode(int val)
{
int pre = getnxt(val, 0);
int suc = getnxt(val, 1);
splay(pre, 0);
splay(suc, pre);
if(t[t[suc].ch[0]].cnt > 1)
{
t[t[suc].ch[0]].cnt--;
splay(t[suc].ch[0], 0);
}
else t[suc].ch[0] = 0;
return;
}
int main()
{
insert(inf), insert(-inf);
int n = read();
while (n--)
{
int opt = read(), x = read();
switch (opt)
{
case 1:
insert(x);
break;
case 2:
delnode(x);
break;
case 3:
printf("%d\n", rank(x) - 1);
break;
case 4:
printf("%d\n", kth(x+1));
break;
case 5:
printf("%d\n", t[getnxt(x, 0)].val);
break;
case 6:
printf("%d\n", t[getnxt(x, 1)].val);
break;
}
}
return 0;
}
前驱后继/删除操作的另一种实现
其实对于查询前驱/后继，我们也可以先插入 val（插入后它就会被 splay 成根），然后在其左/右子树中查询前驱/后继，最后完事了删除 val 就行了（val 工具人表示很淦）。
但问题是，删除怎么办，此时要完成前驱后继操作就需要先学会删除。
此处不妨把 val splay 到根，然后分两种情况讨论：
- 如果左/右子树至少有一个是空的话，直接让不空的那个节点当根就可以了（如果删干净了就删干净了吧）
- 如果左右子树都不为空，则相当于要合并两棵 Splay，怎么办呢，考虑怎么维护 Splay 的性质：
我们可以将左子树最大的节点 Splay 到最上方，然后注意到此时根的左儿子肯定没有右儿子了。所以直接把根的右子树接到根的左儿子的右儿子上，然后让左儿子当根，根就直接滚蛋了。觉得抽象的可以看一下下面的图：
这是将待删除节点 splay 到根后，然后我们把左子树的最大值 splay 到左子树的根，这样左子树就不存在右子树了，将原来根的右子树接上去即可。
原来的根节点就可以丢掉不要了，同时不要忘记再更新根的值。
代码如下：（此时 getnxt() 返回的是答案了）
void delnode(int val)
{
splay(find(val), 0);//把待删除节点旋转到根
if (t[root].val != val)
return;
if (t[root].cnt > 1)
{
t[root].cnt--;
t[root].size--;
return;
}
if ((!t[root].ch[0]) || (!t[root].ch[1]))
root = t[root].ch[0] + t[root].ch[1];
else
{
int lmax = t[root].ch[0];
while (t[lmax].ch[1])
lmax = t[lmax].ch[1];
splay(lmax, root);
t[t[root].ch[1]].fa = lmax;
t[lmax].ch[1] = t[root].ch[1];
maintain(root = lmax);
}
t[root].fa = 0;//千万不要忘记把根的 fa 设为 0
return;
}
int getnxt(int val,int opt)
{
insert(val);
int u = t[root].ch[opt], ans = t[u].val;
while (t[u].ch[opt ^ 1])
u = t[u].ch[opt ^ 1], ans = t[u].val;
delnode(val);
return ans;
}
普通平衡树的另外一种实现
洛谷P6136 的实现：这个版本可以较好的处理查询前驱/后继/排名时待查询数不存在的情况
#include <cstdio>
#include <cctype>
#define L t[u].ch[0]
#define R t[u].ch[1]
inline int read()
{
char c = getchar();
int s = 0;
bool x = 0;
while (!isdigit(c))
x = x | (c == '-'), c = getchar();
while (isdigit(c))
s = 10 * s + c - '0', c = getchar();
return x ? -s : s;
}
inline int max(int a, int b) { return a > b ? a : b; }
inline int min(int a, int b) { return a < b ? a : b; }
const int maxn = 2e6 + 5, inf = 2147483647-20;
int cnt, root;
struct Splay
{
int ch[2], fa;
int cnt, size;
int val;
} t[maxn];
inline bool get(int u)
{
return t[t[u].fa].ch[1] == u;
}
inline void maintain(int u)
{
t[u].size = t[u].cnt + t[L].size + t[R].size;
return;
}
void rotate(int u)
{
int fa = t[u].fa, gfa = t[fa].fa;
int d1 = get(u), d2 = get(fa);
t[fa].ch[d1] = t[u].ch[d1 ^ 1], t[t[u].ch[d1 ^ 1]].fa = fa;
if (gfa)
t[gfa].ch[d2] = u;
t[u].fa = gfa;
t[fa].fa = u, t[u].ch[d1 ^ 1] = fa;
maintain(fa);
maintain(u);
}
void splay(int u, int goal)
{
while (t[u].fa != goal)
{
int fa = t[u].fa, gfa = t[fa].fa;
int d1 = get(u), d2 = get(fa);
if (gfa != goal)
{
if (d1 == d2)
rotate(fa);
else
rotate(u);
}
rotate(u);
}
if (goal == 0)
root = u;
}
void insert(int val)
{
int u = root, fa = 0;
while (u && t[u].val != val)
fa = u, u = t[u].ch[t[u].val < val];
if (u)
t[u].cnt++;
else
{
u = ++cnt;
if (fa)
t[fa].ch[t[fa].val < val] = u;
t[u].fa = fa;
t[u].size = t[u].cnt = 1;
t[u].val = val;
}
splay(u, 0);
}
int find(int val)
{
int u = root;
while (t[u].val != val && t[u].ch[t[u].val < val])
u = t[u].ch[t[u].val < val];
return u;
}
int kth(int k)
{
int u = root;
while (true)
{
if (k <= t[L].size)
u = L;
else if (k > t[L].size + t[u].cnt)
{
k -= t[L].size + t[u].cnt;
u = R;
}
else
return t[u].val;
}
}
void delnode(int val)
{
splay(find(val), 0);
if (t[root].val != val)
return;
if (t[root].cnt > 1)
{
t[root].cnt--;
t[root].size--;
return;
}
if ((!t[root].ch[0]) || (!t[root].ch[1]))
root = t[root].ch[0] + t[root].ch[1];
else
{
int lmax = t[root].ch[0];
while (t[lmax].ch[1])
lmax = t[lmax].ch[1];
splay(lmax, root);
t[t[root].ch[1]].fa = lmax;
t[lmax].ch[1] = t[root].ch[1];
maintain(root = lmax);
}
t[root].fa = 0;
return;
}
int rank(int val)
{
insert(val);
int ans = t[t[root].ch[0]].size + 1;
delnode(val);
return ans;
}
int getnxt(int val,int opt)
{
insert(val);
int u = t[root].ch[opt], ans = t[u].val;
while (t[u].ch[opt ^ 1])
u = t[u].ch[opt ^ 1], ans = t[u].val;
delnode(val);
return ans;
}
int main()
{
insert(inf), insert(-inf);
int n = read(), m = read();
while (n--)
insert(read());
int ans = 0, last = 0;
while (m--)
{
int opt = read(), x = read() ^ last;
switch (opt)
{
case 1:
insert(x);
break;
case 2:
delnode(x);
break;
case 3:
ans ^= (last = rank(x) - 1);
break;
case 4:
ans ^= (last = kth(x + 1));
break;
case 5:
ans ^= (last = getnxt(x, 0));
break;
case 6:
ans ^= (last = getnxt(x, 1));
default:
break;
}
}
printf("%d\n", ans);
return 0;
}
文艺平衡树的实现
文艺平衡树，可实现快速区间翻转，主要得益于 Splay 的区间操作功能。具体地，我们对序列 1 – n 建一棵 Splay，这棵 Splay 的中序遍历即为我们的序列。然后如果要对 [l,r] 翻转，就需要先把 [l,r] 区间独立出来成单独一个子树然后打标记。我们可以考虑先把在 Splay 中排名为 l-1 的点 splay 到根，然后将排名为 r+1 的点 splay 到根下方，由 BST 的性质我们可以知道此时 r+1 的左子树就是我们的 [l,r]。
找到之后打标记即可，注意旋转和 Splay 以及找节点的时候千万记得下放标记。
inline void pushdown(int u)
{
if (t[u].mark && u)
{
swap(L, R);
t[L].mark ^= 1;
t[R].mark ^= 1;
t[u].mark = 0;
}
return;
}
然后是翻转函数的实现。注意由于 l-1 可能等于 0，所以需要提前插入正无穷和负无穷节点，同时读入的 [l,r] 要各自自增 1。同时注意此处 find() 函数与之前的区别
int find(int val)
{
int u = root;
while (1)
{
pushdown(u);
if (val <= t[L].size)
u = L;
else
{
val -= t[L].size + 1;
if (!val)
return u;
u = R;
}
}
}
void reverse(int l, int r)
{
splay(find(l - 1), 0);
splay(find(r + 1), root);
int u = t[root].ch[1];
u = t[u].ch[0];
t[u].mark ^= 1;
return;
}
全部具体实现如下：洛谷P3391
#define L (t[u].ch[0])
#define R (t[u].ch[1])
...
struct Splay
{
int ch[2], fa;
int size, val;
int mark;
} t[maxn];
int root, cnt, n, m;
void maintain(int u)
{
t[u].size = t[L].size + t[R].size + 1;
return;
}
int get(int u)
{
return t[t[u].fa].ch[1] == u;
}
inline void pushdown(int u)
{
if (t[u].mark && u)
{
swap(L, R);
t[L].mark ^= 1;
t[R].mark ^= 1;
t[u].mark = 0;
}
return;
}
void rotate(int u)
{
int fa = t[u].fa, gfa = t[fa].fa;
pushdown(fa); pushdown(u);
int d1 = get(u), d2 = get(fa);
t[fa].ch[d1] = t[u].ch[d1 ^ 1];
t[t[u].ch[d1 ^ 1]].fa = fa;
t[u].ch[d1 ^ 1] = fa;
t[fa].fa = u;
if (gfa)
t[gfa].ch[d2] = u;
t[u].fa = gfa;
maintain(fa);
maintain(u);
return;
}
void splay(int u, int goal)
{
pushdown(u);
while (t[u].fa != goal)
{
int fa = t[u].fa, gfa = t[fa].fa;
int d1 = get(u), d2 = get(fa);
if (gfa != goal)
{
if (d1 == d2)
rotate(fa);
else rotate(u);
}
rotate(u);
}
if (!goal)
root = u;
return;
}
void build(int i, int j, int &u, int fa)
{
int cur = (i + j) >> 1;
u = ++cnt;
t[u].fa = fa;
t[u].size = 1;
if (cur == 1)
t[u].val = -(maxn << 1);
else if (cur == n + 2)
t[u].val = maxn << 1;
else
t[u].val = cur - 1;
if (cur > i)
build(i, cur - 1, t[u].ch[0], u);
if (cur < j)
build(cur + 1, j, t[u].ch[1], u);
maintain(u);
return;
}
int find(int val)
{
int u = root;
while (1)
{
pushdown(u);
if (val <= t[L].size)
u = L;
else
{
val -= t[L].size + 1;
if (!val)
return u;
u = R;
}
}
}
void reverse(int l, int r)
{
splay(find(l - 1), 0);
splay(find(r + 1), root);
int u = t[root].ch[1];
u = t[u].ch[0];
t[u].mark ^= 1;
return;
}
void dfs(int u)
{
if (!u)
return;
pushdown(u);
dfs(L);
if (t[u].val <= 0 || t[u].val > n + 1);
else
printf("%d ", t[u].val);
dfs(R);
return;
}
int main()
{
n = read(), m = read();
build(1, n + 2, root, 0);
while (m--)
{
int l = read() + 1, r = read() + 1;
reverse(l, r);
}
dfs(root);
return 0;
}
易错点
- 一开始记得插入正负无穷，然后在计算排名和第 k 大的时候要考虑其影响
- 旋转操作完成后务必 pushup
- 如果涉及到标记下传，需要在可能改变树形的时候或者向下遍历节点的时候先 pushdown
- 插入完成一个节点之后要将其 splay 到根，否则可能 TLE 或者导致其父亲的
size计算错误（因为 splay 时会一路更新size） - splay 一个节点到根之后务必更新
root变量 - 对于任何操作，如果该改变了节点的父子关系，一定记得既要更改儿子的，也要更改父亲的
这样，最基础的平衡树就学习完了，当然平衡树还有很多其他品种，如红黑树、AVL、替罪羊树、SBT 等等，但事实上 FHQ-Treap 和 Splay 已经基本能解决大多数问题了，所以就不再继续深入了。祝大家 debug 快乐。
留言