无旋 Treap 学习笔记
其实谈不上学习笔记。
在谈平衡树之前，我们需要知道一种二叉树：
二叉查找树（BST）
性质
二叉查找树满足一种性质，即对于该树上的任意一个节点：
- 该节点的权值不小于它左子树上所有节点的权值。
- 该节点的权值不大于它右子树上所有节点的权值。
显然一颗 BST 的中序遍历就是一个权值非严格单调递增的节点序列。
在一颗 BST 上面，可以实现 插入、删除、查找排名、查找第 $k$ 大、求前驱、后继这几种操作。（此处前驱和后继的定义为最大的小于 $x$ 的值和最小的大于 $x$ 的值，下同。）
代码
关于 BST 的代码，个人认为大部分对于无旋 Treap 的学习没有什么帮助，故不提及。绝对不是因为懒。
下面是蓝书上的代码：
struct BST {
int l, r; // 左右子节点在数组中的下标
int val; // 节点关键码
} a[SIZE]; // 数组模拟链表
int tot, root, INF = 1<<30;
int New(int val) {
a[++tot].val = val;
return tot;
}
void Build() {
New(-INF), New(INF);
root = 1, a[1].r = 2;
}
int Get(int p, int val) {
if (p == 0) return 0; // 检索失败
if (val == a[p].val) return p; // 检索成功
return val < a[p].val ? Get(a[p].l, val) : Get(a[p].r, val);
}
void Insert(int &p, int val) {
if (p == 0) {
p = New(val); // 注意p是引用，其父节点的l或r值会被同时更新
return;
}
if (val == a[p].val) return;
if (val < a[p].val) Insert(a[p].l, val);
else Insert(a[p].r, val);
}
int GetNext(int val) {
int ans = 2; // a[2].val==INF
int p = root;
while (p) {
if (val == a[p].val) { // 检索成功
if (a[p].r > 0) { // 有右子树
p = a[p].r;
// 右子树上一直向左走
while (a[p].l > 0) p = a[p].l;
ans = p;
}
break;
}
// 每经过一个节点，都尝试更新后继
if (a[p].val > val && a[p].val < a[ans].val) ans = p;
p = val < a[p].val ? a[p].l : a[p].r;
}
return ans;
}
void Remove(int &p, int val) { // 从子树p中删除值为val的节点
if (p == 0) return;
if (val == a[p].val) { // 已经检索到值为val的节点
if (a[p].l == 0) { // 没有左子树
p = a[p].r; // 右子树代替p的位置，注意p是引用
}
else if (a[p].r == 0) { // 没有右子树
p = a[p].l; // 左子树代替p的位置，注意p是引用
}
else { // 既有左子树又有右子树
// 求后继节点
int next = a[p].r;
while (a[next].l > 0) next = a[next].l;
// next一定没有左子树，直接删除
Remove(a[p].r, a[next].val);
// 令节点next代替节点p的位置
a[next].l = a[p].l, a[next].r = a[p].r;
p = next; // 注意p是引用
}
return;
}
if (val < a[p].val) {
Remove(a[p].l, val);
} else {
Remove(a[p].r, val);
}
}
void zig(int &p) {
int q = a[p].l;
a[p].l = a[q].r, a[q].r = p;
p = q; // 注意p是引用
}
void zag(int &p) {
int q = a[p].r;
a[p].r = a[q].l, a[q].l = p;
p = q; // 注意p是引用
}
（zig 和 zag 等会提及）
好了，现在你已经会平衡树了（逃
BST 的树高期望是 $\log n$ ，所以所有操作的期望复杂度为 $O(\log n)$。
看着很不错？但是如果遇到出题人稍微卡一卡：
你给我说这是二叉树？
BST 就会愉快地变成单次操作为 $O(n)$，但是我们有一些奇技淫巧可以让它变平衡。
平衡树
在讲平衡树之前，我觉得需要回收一下伏笔。
左旋与右旋
还记得前面代码中的 Zig 和 Zag 吗，这就是一种方法。
Zig 是右旋，即在满足 BST 的性质下将右儿子旋转到它的父亲。
Zag 是左旋，即在满足 BST 的性质下将左儿子旋转到它的父亲。
上面就是一种普遍的平衡树的维护方式。
但是下文基本不会提到它们，因为我们写的是无旋 Treap。
Treap
首先讲讲什么是 Treap。
Treap 是 Tree 和 Heap 的合成词，即用堆的性质来维护 BST。换句话说，就是这颗 BST 必须同时满足堆的性质和 BST 的性质，当 Treap 不满足堆的性质时，就需要用旋转来维护。
但是堆的权值应该是什么？首先肯定不是同一个值，因为这样等于没有优化；也不是 BST 的权值，，因为这样是自动将 BST 退化成一条链。
那么应该是什么？
我们发现 BST 在随机数据下的树高期望为 $\log n$ ，于是我们果断引入随机数来充当堆的权值，这样树高就为 $\log n$ 级别。
（上面可能有点绕。注意，BST 和堆是在同一个树上，即对于树上的每一个节点，都有两个权值，分别记录 BST 的权值和堆的权值。）
但是不用旋转，我们应该用什么来维护平衡树？
无旋 Treap（FHQ）
无旋 Treap，又称 FHQ，是一种基于分裂和合并实现的平衡树。
和带旋 Treap 一样，无旋 Treap 的节点也有两个值，分别为 BST 的权值 $v$，和堆的权值 $w$。
参量
在所有之前，我们先来清理一下对于每个节点需要哪些值：
struct sss
{
int r,l,s,w,v;
#define l(x) tree[x].l//左儿子
#define r(x) tree[x].r//右儿子
#define s(x) tree[x].s//子树大小
#define w(x) tree[x].w//堆的权值
#define v(x) tree[x].v//BST的权值
}tree[100005];
下面是一颗完整的普通平衡树的结构：
struct FHQ
{
int cnt,root;//根和节点数量
struct sss
{
int r,l,s,w,v;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define s(x) tree[x].s
#define w(x) tree[x].w
#define v(x) tree[x].v
}tree[100005];
int New(int x)
{
w(++cnt)=rand();
v(cnt)=x;
s(cnt)=1;
return cnt;
}
void pushup(int x){...}
void splitv(int root,int key,int &x,int &y){...}
void splits(int root,int s,int &x,int &y){...}
int merge(int x,int y){...}
void insert(int key){...}
void remove(int key){...}
int v2r(int key){...}
int r2v(int key){...}
int pre(int key){...}
int nxt(int key){...}
}T1;
New即新建节点。
分裂
分裂，顾名思义，是要将一颗无旋 Treap 分裂成两颗，叫做 $x$ 和 $y$，其中我们可以传进去一个值 $val$ 或者 $size$，代表将这颗无旋 Treap 以权值 $val$ 或者大小 $size$ 分界分裂成两颗无旋 Treap。其中 $x$ 的节点的权值都小于等于 $val$ 或者 左子树大小 等于 $size$。
上面的两张分裂方法被称为按值分裂和按大小分裂。
因为按值分裂与按大小分裂相似，所以下文只讲按值分裂。
举个例子：
首先这是一颗无旋 Treap，编号即为 $v$，默认已经满足堆性质，当前节点 $cur$ 为 $8$。
假设 $val$ 为 $5$，因为 $8\ge5$，所以节点 $8$ 及其右子树都归属于 $y$。
但是发现，左子树内也有可能有节点的 $v$ 大于 $val$，所以我们还需要继续处理递归处理左子树。
比如当前节点 $cur$ 为 $4$，因为 $4\le5$，所以 $4$ 及其左子树属于 $x$ 。
现在又要处理 $cur$ 为 $6$ 的时候了。
发现了没有？我们只需要递归处理就可以了。
下面是最终的结果：
那么我们如何将一个节点加入 $x$ 或 $y$ 呢？
我们可以用两个指针 $p$ 和 $q$ 表示遍历到 $cur$ 的时候 $x$ 和 $y$ 新加入的节点。
发现一个性质：如果 $cur$ 属于 $x$，那么 $cur$ 的左子树也属于 $x$，并且也是 $p$ 的左子树；如果 $cur$ 属于 $y$，那么 $cur$ 的右子树也属于 $y$，并且也是 $q$ 的右子树。
所以对于 $v(cur)\le val$ 时，只需要将 $cur$ 加入 $x$ 并且递归查询 $cur$ 的右子树，反之同理。
Code
void splitv(int root,int key,int &x,int &y)//按值分裂
{
if(!root)x=y=0;
else if(v(root)<=key)
{
x=root;//这里传的是引用，所以等于把root加入x中
splitv(r(root),key,r(x),y);//root的左子树属于x，查找x的右子树
pushup(root);
}
else
{
y=root;
splitv(l(root),key,x,l(y));
pushup(root);
}
}
void splits(int root,int s,int &x,int &y)//按大小分裂
{
if(!root)x=y=0;
else if(s(l(root))<s)
{
x=root;
splits(r(root),s-s(l(root))-1,r(x),y);
pushup(root);
}
else
{
y=root;
splits(l(root),s,x,l(y));
pushup(root);
}
}
//使用：
splitv(root,val,x,y);//返回以x和y为根的两个子树
关于上面的pushup，是这个：
void pushup(int x){s(x)=s(l(x))+s(r(x))+1;}
就是用来计算子树大小的，当然也可以维护其他的东西，比如最大子段和。
合并
把树分裂那么一定要合并回去。
为了让无旋 Treap 满足堆的性质，所以要在合并的时候动手脚。
假设我们要合并两颗无旋 Treap $x$ 和 $y$。
这里有个前提：$x$ 中所有节点的 $v$ 必须小于等于 $y$ 中最小的 $v$，否则无法保证 BST。
还是用两个指针 $p$ 和 $q$ 表示遍历 $x$ 和 $y$ 时的节点。
现在已知 $p$ 是小于 $q$ 的，那么要么把 $p$ 放在 $q$ 的左子树，要么把 $q$ 放在 $p$ 的右子树。
谁当父亲就取决于 $w$ 的值。
如果把 $p$ 放在 $q$ 的右子树，那么 $p$ 的左子树不变，把 $p$ 的右子树与 $q$ 继续合并。
反之同理。
int merge(int x,int y)
{
if\(!x\||!y)return x^y;
else if(w(x)>w(y))
{
r(x)=merge(r(x),y);
pushup(x);
return x;
}
else
{
l(y)=merge(x,l(y));
pushup(y);
return y;
}
}
//用法：
root=merge(x,y) //返回值即为根
插入
恭喜你已经理解了最难的那一部分。
对于插入一个值为 $key$ 的数，我们先将树以 $key$ 分裂成 $x$ 和 $y$ 两部分，这样就满足 $x\le key\le y$，就可以直接合并。
void insert(int key)
{
int x,y;
splitv(root,key-1,x,y);
root=merge(merge(x,New(key)),y);
}
删除
先通过按值分裂来找出 $key$ 的位置，再通过按大小分裂找出一个 $v$ 为 $key$ 的节点。
然后合并除了这个节点剩下的两颗子树即可。
void remove(int key)
{
int x,y,z;
splitv(root,key-1,x,y);
splits(y,1,y,z);
root=merge(x,z);
}
查询排名
先按值分裂，即可得出小于 $key$ 的数的个数，最后加一即可。
int v2r(int key)
{
int x,y,ans;
splitv(root,key-1,x,y);
ans=s(x)+1;
root=merge(x,y);//别忘了合并回去
return ans;
}
查询第 $k$ 大
按大小分裂成两颗子树 $x$ 和 $y$，那么答案一定是 $x$ 中最大的数。
那么只需要从 $x$ 的根一路向右找即可。
int r2v(int key)
{
int x,y,ans,now;
splits(root,key,x,y);//返回的是x和y的根
now=x;
while(r(now))now=r(now);
ans=v(now);
root=merge(x,y);
return ans;
}
前驱
以 $key-1$ 按值分裂，得到两颗树 $x$ 和 $y$，其中 $x<key$，所以 $x$ 中最大值即为 $key$ 的前驱。
int pre(int key)
{
int x,y,now,ans;
splitv(root,key-1,x,y);
now=x;
while(r(now))now=r(now);
ans=v(now);
root=merge(x,y);
return ans;
}
后继
以 $key$ 按值分裂，得到两颗树 $x$ 和 $y$，其中 $key<y$，所以 $y$ 中最小值即为 $key$ 的后继。
int nxt(int key)
{
int x,y,now,ans;
splitv(root,key,x,y);
now=y;
while(l(now))now=l(now);
ans=v(now);
root=merge(x,y);
return ans;
}
现在你已经会普通平衡树了，现在来试试文艺平衡树吧！
文艺平衡树
跟普通平衡树一样，只不过我们是将数的位置当成 $v$ 即可。
考虑反转操作怎么实现，发现只用交换区间中所有节点的左右儿子即可。
记得用懒标记，否则暴力下传直接 T。
输出中序遍历即可。
Code
struct FHQ
{
int cnt,root;
struct sss
{
int r,l,s,w,v,tag;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define s(x) tree[x].s
#define w(x) tree[x].w
#define v(x) tree[x].v
#define tag(x) tree[x].tag
}tree[100005];
void build(){cnt=0;}
int New(int x)
{
w(++cnt)=rand();
v(cnt)=x;
s(cnt)=1;
return cnt;
}
void pushup(int x){s(x)=s(l(x))+s(r(x))+1;}
void pushdown(int x)
{
if(tag(x))
{
swap(l(x),r(x));
tag(l(x))^=1;
tag(r(x))^=1;
tag(x)=0;//发现反转后再反转等于没反转，所以使用异或
}
}
void splits(int root,int s,int &x,int &y)
{
pushdown(root);//下传标记
if(!root)x=y=0;
else if(s(l(root))<s)
{
x=root;
splits(r(root),s-s(l(root))-1,r(x),y);
pushup(root);
}
else
{
y=root;
splits(l(root),s,x,l(y));
pushup(root);
}
}
int merge(int x,int y)
{
if\(!x\||!y)return x^y;
else if(w(x)>w(y))
{
pushdown(x);
r(x)=merge(r(x),y);
pushup(x);
return x;
}
else
{
pushdown(y);
l(y)=merge(x,l(y));
pushup(y);
return y;
}
}
void insert(int key)
{
int x,y;
splits(root,key-1,x,y);
root=merge(merge(x,New(key)),y);
}
void remove(int key)
{
int x,y,z;
splits(root,key,x,z);
splits(x,key-1,x,y);
if(y)y=merge(l(y),r(y));
root=merge(merge(x,y),z);
}
void reverse(int l,int r)
{
int x,y,p;
splits(root,r,x,y);
splits(x,l-1,x,p);//找出反转区间
tag(p)^=1;
root=merge(merge(x,p),y);
}
void print(int x)
{
pushdown(x);
if(l(x))print(l(x));
printf("%d ",v(x));
if(r(x))print(r(x));
}
}T1;
后记
原本是在数据结构学习笔记里面写了，但是嫌那个太潦草了，于是有了这个。
可持久化平衡树还没学，有空再补。