平衡树之Splay 学习笔记

chlchl · 2022-03-19 22:05:19 · 个人记录

前言

Splay 是我认为三种平衡树难度最高的了，涉及到双旋（我连 Treap 单旋都一知半解，搞双旋？做梦）。

前置芝士：BST（二叉搜索树）、Treap 旋转基础。

简介

既然有了 Treap，为什么要 Splay 呢？

1. Treap 依靠随机数生成优先级，有时要靠脸拿分；
2. 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<bits/stdc++.h>
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<bits/stdc++.h>
#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 作为常数较小的平衡树，自然是更高效的。

平衡树这东西，不能急。多看图，多看代码注释，代码多写注释，就可以慢慢理解了。