平衡树：YYDS
以下是常见的平衡树/要用平衡树实现的算法：
- Treap（有旋/无旋）
- Splay树
- WBLT（Weight Balanced Leafy Tree，重量平衡线段树）
- SBT（Size Balanced Tree，陈启峰树）
- AVL树
- B树 、B+树
- 笛卡尔树
- 红黑树 、左偏红黑树 、AA树
- 替罪羊树 $\to$ K-D Tree（k-Dimension Tree）
- LT（Leafy Tree，平衡线段树）
- 2-3树 、2-3-4树
- ······
（平衡树能整出的花活真TM多）可见，平衡树在计算机科学中是一种非常重要的数据结构。
其中，在 $NOIP$ 考试范围内的有：
- Treap（有旋/无旋）
- Splay树
- 笛卡尔树
在这之中，我认为无旋 Treap（范浩强树）在 $OI$ 中的应用最为重要与广泛。所以，这篇笔记主要记录范浩强树的实现。（绝对不是因为时间紧迫所以只学了无旋 Treap）
前置知识：二叉搜索树
二叉搜索树是一种二叉树的树形数据结构，其定义如下：
1.空树是二叉搜索树。
2.若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
3.若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
4.二叉搜索树的左右子树均为二叉搜索树。$^{[1]}$
二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于一个有 $n$ 个结点的二叉搜索树中，这些操作的最优时间复杂度为 $O(\log n)$，最坏为 $O(n)$。随机构造这样一棵二叉搜索树的期望高度为 $O(\log n)$。
在给朴素搜索树插入一个新节点时，我们需要从这个搜索树的根节点开始递归，如果新节点比当前节点小，那就向左递归，反之亦然。最后当发现当前节点没有子节点时，就根据新节点的值的大小，让新节点成为当前节点的左或右子节点。$^{[1]}$
如果新插入的节点的值是随机的，那这个朴素搜索树的形状会非常的「胖」。也就是说，每一层的节点比较多。若如此，那么它可以达到我们期望的复杂度。这里放一张图来表示一下随机情况下期望得到的满二叉树，其深度为 $log(n)$：
但是它可以被卡成最坏复杂度。
如果我们有序地（如输入一个单增的序列）给一个朴素的搜索树插入节点，那这棵树就会变得非常 “瘦长” 。由于每次插入的节点都比前面的大，所以都被安排到右儿子上了。
那这就跟一条链（实际上是一个链表）一样了，所有操作复杂度都退化为 $O(n)$，然后就会 T 飞。
引用一张 oi-wiki 上的图来表示这棵可怜的树：
这棵树中，节点 $1$ 到节点 $5$ 权值递增。
怎么解决呢？Treap 给出了一个 比米奇妙妙屋还要妙的 解法。
Treap
Treap（树堆）是一种 弱平衡 的 二叉搜索树。它同时符合二叉搜索树和堆的性质，名字也因此为 tree（树）和 heap（堆）的组合。$^{[1]}$
根据定义，我们可以得出它的一些基本性质：
1.左子节点的值（ $\textit{val}$ ）比父节点大
2.右子节点的值（ $\textit{val}$ ）比父节点小（当然这也是可以反过来的）
3.子节点值（ $\textit{priority}$ ）比父节点大或小（取决于是小根堆还是大根堆）$^{[1]}$
前两个是二叉平衡树的性质，后一个是堆的性质。
声明：以下若没有特殊说明，使用的都是小根堆，包括最后的代码板子。
不难看出，如果用的是同一个值，那这两种数据结构的性质是矛盾的，所以我们再在搜索树的基础上，引入一个给堆的值 $\textit{priority}$。对于 $\textit{val}$ 值，我们维护搜索树的性质，对于 $\textit{priority}$ 值，我们维护堆的性质。其中 $\textit{priority}$ 这个值是随机给出的。$^{[1]}$
那么，Treap 要怎么解决二叉搜索树的问题呢？
关键就在 Treap 中的那个堆。
Treap 通过随机化的 $\textit{priority}$ 属性，以及维护堆性质的过程，「打乱」了节点的插入顺序。从而让二叉搜索树达到了理想的复杂度，避免了退化成链的问题。$^{[1]}$
Treap 有较为严格的复杂度证明（看这里），每一次操作都是 $O(logn)$的。
总之，你永远可以相信 Treap 的力量。
现在，就到了平衡树的一个关键了：如何维护平衡。
在这里，Treap 分裂成了两派：一派用旋转维护，称为 有旋 Treap ；另一派就是这篇笔记的重点，它使用 分裂 与 合并 两个操作来维护，这就是所谓的 无旋 Treap，即 范浩强树。
相比于有旋的，无旋的优势在于代码实现简单，可以方便地进行区间操作。缺点则是常数较大，但一般我们不会在意这些常数。（况且我们还有一些虽然不常用但确实可行的优化）$^{[2]}$
无旋 Treap
下面逐一介绍无旋 Treap 的基本操作。
分裂（split）
注：这里的分裂方式是按值分裂，事实上还可以按排名分裂，两种方法的效果一样。
分裂过程接受两个参数：根指针 $\textit{cur}$、关键值 $\textit{key}$。结果为将根指针指向的 Treap 分裂为两个 Treap，第一个 Treap 所有结点的值（$\textit{val}$）小于等于 $\textit{key}$，第二个 Treap 所有结点的值大于 $\textit{key}$。
该过程首先判断 $\textit{key}$ 是否小于 $\textit{cur}$ 的值，若小于，则说明 $\textit{cur}$ 及其右子树全部大于 $\textit{key}$，属于第二个 Treap。当然，也可能有一部分的左子树的值大于 $\textit{key}$，所以还需要继续向左子树递归地分裂。对于大于 $\textit{key}$ 的那部分左子树，我们把它作为 $\textit{cur}$ 的左子树，这样，整个 $\textit{cur}$ 上的节点都是大于 $\textit{key}$ 的。$^{[1]}$
为了方便理解，这里引用一张 oi-wiki 上的图表示 $cur<key$ 时的分裂：
示例代码：
int update(int o){return t[o].sz=t[t[o].l].sz+t[t[o].r].sz+1,o;}//update用于更新size
void split(int o,int x,int &l,int &r)//o即上文中的cur，x即key，l和r是左右端点。
{
if(o==0) return l=0,r=0,void();
if(t[o].k<=x) l=o,split(t[o].r,x,t[o].r,r);
else r=o,split(t[o].l,x,l,t[o].l);
update(o);
}
合并
因为需要合并的两个 Treap 已经有序，所以我们在合并的时候只需要考虑把哪个树「放在上面」，把哪个「放在下面」，也就是是需要判断将哪个一个树作为子树。
显然，根据堆的性质（再次提醒：我们采用的是小根堆），我们需要把 $\textit{priority}$ 小的放在上面。
同时，我们还需要满足搜索树的性质，所以若 $l$ 的根结点的 $\textit{priority}$ 小于 $r$ 的，那么 $l$ 即为新根结点，并且 $r$ 因为值比 $l$ 更大，应与 $r$ 的右子树合并；反之，则 $r$ 作为新根结点，然后因为 $l$ 的值比 $r$ 小，与 $r$ 的左子树合并。
int merge(int l,int r)
{
if(l==0||r==0) return l+r;
if(t[l].p<=t[r].p) return t[l].r=merge(t[l].r,r),update(l);//p即priority
return t[r].l=merge(l,t[r].l),update(r);
}
插入
为了插入一个关键码为 $x$ 的节点，我们把整棵树分裂成不大于/大于 $x$ 的两棵树 $A,B$，然后直接申请一个新的节点。最后将新节点与 $A$ 和 $B$ 合并即可。
申请节点的代码如下：
int newnode(int x)
{
++cnt;
t[cnt]=node(x,rand(),1);
return cnt;
}
一个优化是，在将 $A$ 分裂成小于/等于 $x$ 的两棵树，若等于 $x$ 的那棵树为空，则增加其数量与子树大小，反之则增加节点数与子树大小。这个优化可以减少节点的浪费，对代码有常数级的复杂度提升。
伪代码如下：
p <- split(x-1)
if p.size=0 do：
newnode(x)
else do:
p.size++
cnt++
但一般为了简便，我们不经常采用这个小优化。下面是不采用优化的代码：
void insert(int x)
{
int l,r;
split(rt,x,l,r),rt=merge(merge(l,newnode(x)),r);
}
删除
删除操作也使用和插入操作相似的方法，找到值和 $\textit{x}$ 相等的节点，并且删除它。
void erase(int x)
{
int l,r,p;
split(rt,x,l,r),split(l,x-1,l,p);
p=merge(t[p].l,t[p].r),rt=merge(merge(l,p),r);
}
根据值查询排名
首先，求排名（$k$）可以这么转化为求节点数：
$k=\sum\limits_{i=1}^{n} [T_i<k]+1$
所以我们根据 $\textit{val} - 1$ 分裂当前树，那么分裂后的第一个树中的全体节点 $A$ 就符合:
$A\le val-1$
$A$ 也包含了所有值小于 $x$ 的节点。所以 $A.size+1$ 就是我们想要的 $k$。
int rnk(int x)//rank可能与内置函数重名
{
int l,r,res;
split(rt,x-1,l,r),res=t[l].sz+1,rt=merge(l,r);
return res;
}
根据排名（k）查询值
分三种情况：
- 如果左子树的大小等于 $k-1$，那么直接返回 $cur$ 指向的搜索树中的值就是答案；
- 如果左子树大小小于 $k-1$，那么答案在右子树里。此时我们把 $k-1$ 减掉左子树大小之后递归右子树即可；
- 如果左子树大小大于 $k-1$，那么直接递归左子树。
代码如下：
int kth(int k,int o=rt)
{
if(t[t[o].l].sz==k-1) return t[o].k;
if(t[t[o].l].sz<k-1) return kth(k-1-t[t[o].l].sz,t[o].r);
else return kth(k,t[o].l);
}
查询第一个比 $val$ 小的节点（前驱）
可以把这个问题转化为，在比 $\textit{val}$ 小的所有节点中，找出排名最大的。
我们根据 $\textit{val}$ 来分裂这个 Treap，返回的第一个 Treap 中的节点的值就全部小于 $\textit{val}$，然后我们调用 kth 函数找出这个树中值最大的节点。
int pre(int x)
{
int l,r,res;
split(rt,x-1,l,r),res=kth(t[l].sz,l),rt=merge(l,r);
return res;
}
查询第一个比 $val$ 大的节点（后继）
和上个操作类似，可以把这个问题转化为，在比 $\textit{val}$ 大的所有节点中，找出排名最大的。
根据 $\textit{val}$ 分裂后，返回的第二个 Treap 中的所有节点的值就大于 $\textit{val}$。
然后我们去查询这个树中排名为 $1$ 的节点（也就是值最小的节点）的值，就可以成功查到第一个比 $\textit{val}$ 大的节点。
int nxt(int x)
{
int l,r,res;
split(rt,x,l,r),res=kth(1,r),rt=merge(l,r);
return res;
}
这些就是无旋 Treap 的基础单点操作。当然，它还可以进行区间操作，但在此由于篇幅所限不作讲述。
例题
这里给出 P6136 的代码，也是无旋 Treap 的完整板子。
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
return s*w;
}
const int N=2e6+114;
struct node{
int k,p,sz,l,r;
node(int k=0,int p=0,int sz=0,int l=0,int r=0):k(k),p(p),sz(sz),l(l),r(r){}
}t[N];
int cnt,n,rt,m,last,ans;
int newnode(int x){return ++cnt,t[cnt]=node(x,rand(),1),cnt;}
int update(int o){return t[o].sz=t[t[o].l].sz+t[t[o].r].sz+1,o;}
void split(int o,int x,int &l,int &r)
{
if(o==0) return l=0,r=0,void();
if(t[o].k<=x) l=o,split(t[o].r,x,t[o].r,r);
else r=o,split(t[o].l,x,l,t[o].l);
update(o);
}
int merge(int l,int r)
{
if(l==0||r==0) return l+r;
if(t[l].p>=t[r].p) return t[l].r=merge(t[l].r,r),update(l);
return t[r].l=merge(l,t[r].l),update(r);
}
void insert(int x)
{
int l,r;
split(rt,x,l,r),rt=merge(merge(l,newnode(x)),r);
}
void erase(int x)
{
int l,r,p;
split(rt,x,l,r),split(l,x-1,l,p);
p=merge(t[p].l,t[p].r),rt=merge(merge(l,p),r);
}
int rnk(int x)
{
int l,r,res;
split(rt,x-1,l,r),res=t[l].sz+1,rt=merge(l,r);
return res;
}
int kth(int k,int o=rt)
{
if(t[t[o].l].sz==k-1) return t[o].k;
if(t[t[o].l].sz<k-1) return kth(k-t[t[o].l].sz-1,t[o].r);
else return kth(k,t[o].l);
}
int pre(int x)
{
int l,r,res;
split(rt,x-1,l,r),res=kth(t[l].sz,l),rt=merge(l,r);
return res;
}
int nxt(int x)
{
int l,r,res;
split(rt,x,l,r),res=kth(1,r),rt=merge(l,r);
return res;
}
signed main()
{
srand(0);
n=read(),m=read();
for(int i=1;i<=n;i++) insert(read());
while(m--)
{
int opt=read(),x=read()^last;
switch(opt)
{
case 1: insert(x); break;
case 2: erase(x); break;
case 3: last=rnk(x),ans^=last; break;
case 4: last=kth(x),ans^=last; break;
case 5: last=pre(x),ans^=last; break;
case 6: last=nxt(x),ans^=last; break;
}
}
printf("%d",ans);
}
参考文章
[1] oi-wiki Treap