平衡树之Splay 学习笔记
平衡树之Splay 学习笔记
chlchl
·
2022-03-19 22:05:19
·
个人记录
前言
Splay 是我认为三种平衡树难度最高的了，涉及到双旋（我连 Treap 单旋都一知半解，搞双旋？做梦）。
前置芝士：BST（二叉搜索树）、Treap 旋转基础。
简介
既然有了 Treap，为什么要 Splay 呢？
Treap 依靠随机数生成优先级，有时要靠脸拿分；
Splay 有独一有二的作用：区间操作（啊其实 fhq_treap 也可以啊，但是啊，有个东西叫做 Link Cut Tree 啊，fhq_treap 维护要多 tm 一个 log 啊，常数还 tm 比 Splay 大啊，讲解还 tm 很少啊，所以没什么人用啊，不过我正在码啊）。
Splay Tree 又被称为伸展树，靠伸展维持 BST 的平衡。
不过，讲双旋之前，还是回顾一下单旋吧（不会的看上面链接）！
放个代码帮助理解：
bool direction(int x, int fa){return spy[fa].son[1] == x;}
void update(int u){spy[u].sz = spy[spy[u].son[0]].sz + spy[spy[u].son[1]].sz + 1;}
void rebuild(int x, int fa, int d){//d 是左边 or 右边的标记
spy[fa].son[d] = x, spy[x].fa = fa;
}
void rotate(int x){
int fa = spy[x].fa, g = spy[fa].fa;
int d = direction(x, fa);//右旋回 0 左旋回 1
rebuild(spy[x].son[d ^ 1], fa, d);//什么旋处理什么儿子
rebuild(x, g, direction(fa, g));
rebuild(fa, x, d ^ 1);//更换 x 和 fa 的父子关系
update(fa), update(x);
}
什么是双旋呢？就是旋两次呗！每次 Splay 要旋转两次才能平衡。这样操作的优势是将 Treap 的单旋再次优化时间，加上其 nbhh 的 Splay 操作，打遍天下无敌手（然鹅 Treap 仍然更快）。
怎么旋呢？
对于一棵有 3 个节点的树，一共有 4 种形态。我们称 zig 为右旋操作，zag 为左旋操作，则四种形态的树分别应该进行以下操作（纯图解说，无讲解文字，但保证能看懂）：
大概就是这样啦！放一下双旋代码：
void splay(int x, int v){//把 x 转到 y 的儿子
if(!v) rt = x;//如果 v=0，那x自然就是根节点
while(spy[x].fa != v){
int f = spy[x].fa, g = spy[f].fa;
if(g != v) direction(f, g) ^ direction(x, f) ? rotate(x) : rotate(f);
//原本要分四种情况，但因为 rotate 合二为一，所以有的情况在 rotate 里讨论了
//利用异或，如果两个方向不同（返回1），就两次单旋，否则就是双旋
rotate(x);//最后一次都是旋转 x
}
}
插入、排名就不瞎哔哔了，与 BST 差不多，根据性质递归就行。但是要讲讲删除：
Splay 的删除做法是将 u 转到根节点之后删掉。那么问题来了，u 被删掉之后，谁来继承根节点的位置呢？不妨画图分析：
答案显而易见：选 u 的后继做新的根节点，可以省去很多事情（debug 也容易很多嘛）。
所以就有了下面这份代码：
void delnode(int u){
splay(u, 0);//先将 u 转到 根节点儿子
if(!spy[rt].son[1]) rt = spy[u].son[0], spy[rt].fa = 0;//转完发现没有右儿子，直接把根定为左儿子
else{
int nxt = spy[u].son[1];
while(spy[nxt].son[0]) nxt = spy[nxt].son[0];//找后继
splay(nxt, u);//将后继转到 u 的儿子
rebuild(spy[u].son[0], nxt, 0);//重构左儿子和后继的父子关系
rt = nxt, spy[nxt].fa = 0;//将根节点变成这个后继
update(rt);
}
}
其余的就和 BST、Treap 等差不多了， 唯一要注意的是每次操作都要旋它个天翻地覆，保证树的随机性，降低链的出现概率。
放个 P3369 的代码：
#include
using namespace std;
const int N = 1e5 + 10;
int n, rt, sum;
struct Splay{
int fa, val, sz, son[2];//0 left, 1 right
} spy[N];
bool direction(int x, int fa){return spy[fa].son[1] == x;}
void update(int u){spy[u].sz = spy[spy[u].son[0]].sz + spy[spy[u].son[1]].sz + 1;}
void rebuild(int x, int fa, int d){//d 是左边 or 右边的标记
spy[fa].son[d] = x, spy[x].fa = fa;
}
void rotate(int x){
int fa = spy[x].fa, g = spy[fa].fa;
int d = direction(x, fa);//右旋回 0 左旋回 1
rebuild(spy[x].son[d ^ 1], fa, d);//什么旋处理什么儿子
rebuild(x, g, direction(fa, g));
rebuild(fa, x, d ^ 1);//更换 x 和 fa 的父子关系
update(fa), update(x);
}
void newnode(int &u, int val, int fa){
u = ++sum;
spy[sum].fa = fa, spy[sum].val = val, spy[sum].sz = 1;
}
void splay(int x, int v){//把 x 转到 y 的儿子
if(!v) rt = x;
while(spy[x].fa != v){
int f = spy[x].fa, g = spy[f].fa;
if(g != v) direction(f, g) ^ direction(x, f) ? rotate(x) : rotate(f);
//原本要分四种情况，但因为 rotate 合二为一，所以有的情况在 rotate 里讨论了
rotate(x);//最后一次都是旋转 x
}
}
void insert(int &u, int fa, int val){
if(!u) newnode(u, val, fa), splay(u, 0);
else if(val < spy[u].val) insert(spy[u].son[0], u, val);
else insert(spy[u].son[1], u, val);
}
void delnode(int u){
splay(u, 0);
if(!spy[rt].son[1]) rt = spy[u].son[0], spy[rt].fa = 0;//转完发现没有右儿子，直接把根定为左儿子
else{
int nxt = spy[u].son[1];
while(spy[nxt].son[0]) nxt = spy[nxt].son[0];//找后继
splay(nxt, u);//将后继转到 u 的儿子
rebuild(spy[u].son[0], nxt, 0);
//重构 u 左儿子和后继的父子的关系，因为 u 已经删掉
rt = nxt, spy[nxt].fa = 0;//将根节点变成这个后继
update(rt);
}
}
void del(int val, int u = rt){
if(spy[u].val == val) delnode(u);
else if(spy[u].val > val) del(val, spy[u].son[0]);
else del(val, spy[u].son[1]);
}
int rnk(int x){
int u = rt, rk = 1, v = 0;
while(u){
if(x <= spy[u].val) v = u, u = spy[u].son[0];
else rk += spy[spy[u].son[0]].sz + 1, u = spy[u].son[1];
}
if(v) splay(v, 0);
return rk;
}
int query(int rk){
int u = rt;
while(u){
if(spy[spy[u].son[0]].sz + 1 == rk){
splay(u, 0);
break;
}else if(spy[spy[u].son[0]].sz >= rk) u = spy[u].son[0];
else rk -= spy[spy[u].son[0]].sz + 1, u = spy[u].son[1];
}
return spy[u].val;
}
int main(){
scanf("%d", &n);
int op, x;
while(n--){
scanf("%d%d", &op, &x);
if(op == 1) insert(rt, 0, x);
else if(op == 2) del(x);
else if(op == 3) printf("%d\n", rnk(x));
else if(op == 4) printf("%d\n", query(x));
else if(op == 5) printf("%d\n", query(rnk(x) - 1));
else if(op == 6) printf("%d\n", query(rnk(x + 1)));
}
return 0;
}
下面，进入重头戏。
独一无二——Splay 区间操作
Splay 独特之处在于它可以支持区间操作，不仅能像线段树一样维护区间和、区间最值，还能维护区间第 k 小、插入、删除节点等逆天操作。配合上 LCT，Splay 绝对是 OI 界中的大 Boss（虽然 NOIp 根本不会考到这个难度）。
我们利用二叉搜索树的性质用 Splay 储存整个数列，并且中序遍历就是整个数列。
当要处理 \lbrack l,r\rbrack 区间时，只要将 l-1 旋到根节点，r+1 旋到 l-1 的右儿子，那么 l-1 右儿子的左子树就是要操作的区间。为什么呢？看图：
看图懂的原理 +1。
然后就跟普通的 Splay 差不多了。放一个 P3372 线段树 1 的Splay：
#include
#define int long long
using namespace std;
const int N = 1e5 + 10;
int rt, num;
int n, q, a[N], s[N], cntemp;
struct Splay_tree{
int val, sum, tag, sz, fa, son[2];
} spy[N];
void newnode(int &u, int p, int k){
if(cntemp) u = cntemp--;//动态开点
else u = ++num;
spy[u].fa = p;
spy[u].sz = 1;
spy[u].tag = spy[u].son[0] = spy[u].son[1] = 0;
spy[u].val = spy[u].sum = k;
}
bool direction(int u, int fa){return spy[fa].son[1] == u;}
//给 r 为根的子树增加值，把当前结点更新，加懒标记
void update_val(int u, int v){
if(u == 0) return;
spy[u].tag += v, spy[u].val += v, spy[u].sum += v * spy[u].sz;//更新区间值
}
void pushup(int u){//更新当前节点的区间和、子树大小
spy[u].sz = spy[spy[u].son[0]].sz + spy[spy[u].son[1]].sz + 1;
spy[u].sum = spy[spy[u].son[0]].sum + spy[spy[u].son[1]].sum + spy[u].val;
}
void pushdown(int u){
if(spy[u].tag){//与线段树相似
update_val(spy[u].son[0], spy[u].tag);
update_val(spy[u].son[1], spy[u].tag);
spy[u].tag = 0;
}
}
void rebuild(int x, int fa, int d){
spy[fa].son[d] = x, spy[x].fa = fa;
}
void rotate(int x){
int fa = spy[x].fa, g = spy[fa].fa;
int d = direction(x, fa);//右旋回 0 左旋回 1
pushdown(fa);
pushdown(x);//任何操作前下放节点，不然就连父亲儿子都找不到了
rebuild(spy[x].son[d ^ 1], fa, d);//什么旋处理什么儿子
rebuild(x, g, direction(fa, g));
rebuild(fa, x, d ^ 1);//更换 x 和 fa 的父子关系
pushup(fa), pushup(x);
}
void Splay(int x, int v){//把 x 转到 y 的儿子
pushdown(x);
if(!v) rt = x;
while(spy[x].fa != v){
int f = spy[x].fa, g = spy[f].fa;
if(g != v) direction(f, g) ^ direction(x, f) ? rotate(x) : rotate(f);
rotate(x);
}
}
int rnk(int u, int k){//查询排名为 k 的数
pushdown(u);//先下放，与线段树一样
int t = spy[spy[u].son[0]].sz + 1;//左子树sz+自身
if(t == k) return u;
if(t > k) return rnk(spy[u].son[0], k);//在左子树中，往下递归
else return rnk(spy[u].son[1], k - t);//在右子树中，往右子树递归，查询排名为 k - t 的数
}
void build(int &o, int l, int r, int p){//与线段树非常相似
if(l > r) return;
int mid = (l + r) >> 1;
newnode(o, p, a[mid]);//建树，新建当前节点
build(spy[o].son[0], l, mid - 1, o);//往左子树递归
build(spy[o].son[1], mid + 1, r, o);//往右子树递归
pushup(o);//更新 o 节点的 val 和 sum
}
void update(int l, int r, int v){//区间增加一个值
Splay(rnk(rt, l), 0);//将第l个点旋转到根结点
Splay(rnk(rt, r + 2), rt);//因为加了个空结点，第 r + 2 个点旋转到根结点的右孩子
update_val(spy[spy[rt].son[1]].son[0], v);//将区间更新
pushup(spy[rt].son[1]);//更新右子树（val更新之后右子树也会改变）
pushup(rt);//更新节点 （根节点就更不用说了）
}
int query(int l, int r){//查询区间的和
Splay(rnk(rt, l), 0);//同 update
Splay(rnk(rt, r + 2), rt);//同 update
return spy[spy[spy[rt].son[1]].son[0]].sum;//那么 spy[spy[rt].son[1]].son[0] 就是需要修改的区间[l, r]
}
main(){
scanf("%lld%lld", &n, &q);
rt = num = cntemp = 0;//cntemp 方便动态开点
spy[rt].son[0] = spy[rt].son[1] = spy[rt].fa = spy[rt].sz = spy[rt].tag = spy[rt].sum = spy[rt].val = 0;//初始化
newnode(rt, 0, -1);//新建两个空节点
newnode(spy[rt].son[1], rt, -1);//新建两个空节点，防止区间操作时旋了个寂寞
for(int i=1;i<=n;i++) scanf("%lld", &a[i]);
build(spy[spy[rt].son[1]].son[0], 1, n, spy[rt].son[1]);//建树（区间建树，所以这么传参）
pushup(spy[rt].son[1]);//更新右子树
pushup(rt);//更新根节点
int op, x, y, z;
while(q--){
scanf("%lld", &op);
if(op == 2){
scanf("%lld%lld", &x, &y);
printf("%lld\n", query(x, y));
}else{
scanf("%lld%lld%lld", &x, &y, &z);
update(x, y, z);
}
}
return 0;
}
重点：花样操作。
花样操作太多了，没办法一一讲解，只能挑几个经典的说说。
区间翻转：P3391 【模板】文艺平衡树
这道题虽然 fhq_treap 做起来好调，但是 Splay 作为常数较小的平衡树，自然是更高效的。
平衡树这东西，不能急。多看图，多看代码注释，代码多写注释，就可以慢慢理解了。