Splay 文艺平衡树

前言：

平衡树是一种很有用的数据结构，在很多高级数据结构中都有很多用处。

我们需要熟练掌握 Splay树虽然它的代码很长很长（一百多行吧…

简述Splay树：

Splay是一种数据结构 ( 废话），它的每个节点的的左儿子比这个节点小，每个节点的右儿子比这个节点大，跟 treap 差不多，但是实现的时间可能要比 treap 慢。
树的旋转是 splay 的基础，对于一个二叉查找树来说，树的旋转不破坏查找树的结构

Splaying:

简述就是要口糊的，现在我们来看看 Splay Tree 的基本操作Splaying
为了让被查询的条目更接近树根，Splay-Tree 采用的树的旋转操作，同时保证了二叉排序树的性质不变
我们设要旋转的节点为 x ,x 的父亲节点是 p ， p 的父亲节点为 y ,我们在旋转的时候要考虑三种情况：
节点 x 是 p 的左儿子还是右儿子
节点 p 是否为根节点，如果不是的话，可以进行旋转操作
p 为 y 的左儿子还是右儿子
旋转的时候还有三种基本操作：
当 p 为根节点时，若 x 为 p 的左孩子时右旋，反之左旋

当 p 不为根节点时，且 x ，p 同为左儿子或者右儿子时，若同为左儿子，则进行右旋，反之左旋

当 p 不为根节点时，且 x , p 不同为左儿子或者右儿子时，若 p 为左儿子 x 为右儿子，先将 x 左旋再右旋，若 p 为右儿子 x 为左儿子时，先将 x 右旋再左旋

我觉得旋转的操作还是很好写的，列出那么多情况只是方便理解罢了…会了 Splaying ，我觉得 Splay-Tree 已经会了一半了…
还有一件很重要的事（我终于会挂图片了Makedown真坑…）

Splay-Tree 的具体操作：

access：

access（i）表示我们返回 i 的指针，如果点 i 出现在 Splay-Tree 中，否则我们返回空指针
我们设树根为 root ，从树根向下寻找若找到含有 i 的节点 x ，就Splaying x ,返回 x 的指针，结束访问操作
如果我们遇到了空指针，代表我们要访问的 i 不在 Splay-Tree 中，我们就只能在树的最后一个非空节点进行一次 Splaying 操作，然后返回空指针
另外，如果这一棵树是空的，我们忽略 Splaying 的操作…

join：

我把树的插入和删除操作放在了后面，我们先来看一下合并 join 操作和分裂 split 操作
join 是将树 T1，与 T2 合并，包含两棵树的所有节点，并返回合并后的树
操作先假设 T1 的所有节点都小于 T2，操作结束之后会销毁 T1,T2
我们先访问 T1 中的最大节点 i ，访问结束后，i 就变成了 T1 的根节点，它的右孩子为空。然后我们将 T2 作为 i 的右子树（这时 i 已经成为 T1 的根节点）并返回完成后的新树，完成操作

split：

我们分裂一棵树并且返回两棵树 T1 和 T2 ，T1 包括所有小于等于 i 的节点，T2 包含所有大于 i 的节点，操作完成后销毁原树
我们先访问（access）i ，然后再根据新节点的左儿子和右儿子的值来进行切断操作，并返回形成的两棵树…

insert：

现在我们看看插入和删除的操作
insert（i，T）表示我们将点 i 插入到树 T 中，我们首先执行 split 操作，然后将 T 换成一个包含 i 的根节点的新树，这个根节点的左右两棵子树就是 split 返回的 T1 和 T2

delete：

从树中删除节点 i ，我们首先执行访问（access） i ，然后将 T 变成 i 的左子树和右子树合并（join）之后的新树
我觉得在理解合并（join)和分裂（split）操作之后是很容易理解插入（insert）和删除（delete）操作的
另外，在基础操作理解之后，我们来看看更优的插入和删除操作

更优的插入（insert）和删除（delete）：

insert：我们先查找 i ，把遇到的空指针替换成一个含有 i 的新节点，再 Splaying 这个由空节点替换后的节点
delete：我们查找含有 i 的节点，设这个节点为 x ，它的父亲节点为 y ,把 x 的左右子树合并之后，再把 y 进行 Splaying 操作

很多东西我也不多做解释了，毕竟手码那么多字也不易，我觉得我写的还是比较容易看懂的。只要认真用心看的话，以上的操作是能够理解的

Splay-Tree的区间操作：

有了以上那么多的操作方法，相信对 Splay-Tree 的理解已经很深了，我们现在只需要学习对 Splay-Tree 的查询操作，就可以运用 Splay-Tree 解题了

区间查询与修改

实际上，Splay-Tree 的中序遍历，即为我们要维护的数列，我们要如何在 Splay-Tree 中表示出某个区间呢
假设我们现在要提取区间 [a,b]，我们先将 a 前面一个数对应的节点旋转到根，将 b 的后面一个数对应的节点转到根的右边，可以发现，这时候根右边的左子树就对应了区间 [a,b]，我们来看一张图…

是不是很好理解？然后我们利用以上的区间操作就可以实现线段树的功能，在这里我们不做多解释，就讲一下区间修改
我们需要用到类似于线段树的延迟标记。对于每一个节点，我们额外记录一个或几个标记，表示以这个节点为根的子树是否进行了某种操作，而且这种操作会影响这个节点的子节点
当我们进行旋转或者别的操作时，我们就下放这些操作，维护该节点的子节点信息，若我们不设置这些延迟标记的话，在进行这些操作的时候就更改子节点的信息，如果这些节点在之后的操作并没有被询问到，那么这次修改的就没有意义了…这也是为什么我们需要延迟标记…

Splay-Tree 优于线段树的功能

我们讲两种操作
如果我们要在 a 后面插入一些数，只需要将要插入的树构造成一棵 Splay-Tree ，然后将 a 转到根，并将 a 后面一个数对应的节点转到 a 的右边，最后把新构造的 Splay-Tree 挂到 a 的右节点的左儿子就行了
如果我们要删除区间 [ a , b ] 内的数，只需要提取区间 [ a , b ] ，直接删除即可
讲完了 Splay-Tree 的操作，我们来看一下模板题…

Splay-Tree的模板题

题目背景

这是一道经典的Splay模板题——文艺平衡树。

题目描述

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1

输入输出格式

输入格式：

第一行为n,m n表示初始序列有n个数，这个序列依次是 ( 1 , 2 , ⋯ n−1 , n ) m 表示翻转操作次数

接下来m行每行两个数 [ l , r ][ l , r ] 数据保证 1 ≤ l ≤ r ≤ n

输出格式：

输出一行n个数字，表示原始序列经过m次变换后的结果

输入输出样例

输入样例#1：

输出样例#1：

4 3 2 1 5

说明

n,m ≤ 100000

解题分析

说实在话 Splay-Tree上面讲的很多了…
还有我觉得洛谷上 Treap 的模板要比这道题好…几乎纯 Splay-Tree
这道题我们需要对 Splay-Tree 进行区间翻转…
上面好像并没有讲怎么进行区间翻转…没关系自己动手丰衣足食
这里平衡树（老是打Splay-Tree太麻烦了…)维护的不再是权值了，题目中按照编号排序，而最后的结果实际上也是求平衡树的中序排序（性质
所以维护权值肯定不对…
如果我们找的点在树中是第 K 个，那么这个数就是树中的第 K 大，所以序列中的位置就变成了区间第 K 大…
而翻转，其实就是把这个节点的子树左右儿子互换即可，我们只需要一直下放标记，然后把左右儿子交换…最后输出平衡树的中序遍历即可…
这种方法还是比较直白的，我不是很想给出证明…洛谷上很多人也这样写…代码还是比较简单的…

AC代码吸氧444ms

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))

using namespace std;

const int N=100010;
int n,m,x,y,root=0,tot=0,l,r;
struct node{
    int ch[2],fa,val,tag,son;
    inline void init(int x,int ff){fa=ch[0]=ch[1]=0;son=1;val=x;fa=ff;}
}a[N];

inline void push_up(int x) {a[x].son=a[a[x].ch[0]].son+a[a[x].ch[1]].son+1;}

inline void push_down(int x){
    if(a[x].tag){
        a[a[x].ch[0]].tag^=1;
        a[a[x].ch[1]].tag^=1;
        a[x].tag=0;
        swap(a[x].ch[0],a[x].ch[1]);
    }
}

inline void rotate(int x){
    re y=a[x].fa;
    re z=a[y].fa;
    re k=a[y].ch[1]==x;
    a[z].ch[a[z].ch[1]==y]=x;
    a[x].fa=z;
    a[y].ch[k]=a[x].ch[k^1];
    a[a[x].ch[k^1]].fa=y;
    a[x].ch[k^1]=y;
    a[y].fa=x;
    push_up(y);push_up(x);
}

inline void splay(int x,int goal){
    while(a[x].fa!=goal){
        re y=a[x].fa;
        re z=a[y].fa;
        if(z!=goal) (a[z].ch[1]==x)^(a[y].ch[1]==y)?rotate(x):rotate(y);
        rotate(x);
    }
    if(goal==0) root=x;
}

inline void insert(int x){
    int u=root,ff=0;
    while(u){
        ff=u;u=a[u].ch[x>a[u].val];
    }
    u=++tot;
    if(ff) a[ff].ch[x>a[ff].val]=u;
    a[u].init(x,ff);
    splay(u,0);
} 

inline int K_th(int x){
    int u=root;
    while(1){
        push_down(u);
        if(a[a[u].ch[0]].son>=x) u=a[u].ch[0];
        else if(a[a[u].ch[0]].son==x-1) return u;
        else x-=a[a[u].ch[0]].son+1,u=a[u].ch[1]; 
    }
}

inline void solve(int x){
    push_down(x);
    if(a[x].ch[0]) solve(a[x].ch[0]);
    if(a[x].val>1&&a[x].val<n+2) printf("%d ",a[x].val-1);
    if(a[x].ch[1]) solve(a[x].ch[1]);
}

int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n+2) insert(i);
    while(m--){
        scanf("%d%d",&x,&y);
        l=K_th(x);r=K_th(y+2);
        splay(l,0);
        splay(r,l);
        a[a[a[root].ch[1]].ch[0]].tag^=1;
    }
    solve(root);
    printf("\n");
    return 0;
}

其实一些解释在上面已经给出了，我也不在代码里加注释了
我觉得还是比较能理解的…

后记

其实我还是想加一道纯平衡树的题的（起码不用想怎么翻转…
有时候练练模板还是好的但是我觉得这篇的篇幅已经很长了…
那就这样吧我觉得很详细了…
还有一件事我好菜啊…
欢迎指正联系方式如下

联系qq： 953559040

微博： IncinblePan

洛谷： SherlockPan