【蒟蒻数据结构】伸展树Splay

Author： jvruo
发布时间：July 23, 2018
6383views
One comment
23488字数
Categories：蒟蒻数据结构

我们在之前的BLOG已经多次提到了，平衡树的本质是BST(二叉查找树)，而平衡树的作用是为了加速二叉查找树，但不添加任何内容，可以说是BST的加速版。但是Splay却恰好相反，为了得到更多的功能，splay牺牲了时间和空间，其本质目的不是为了加速二叉排序树，而是为了增加一些普通二叉排序树所不具有的功能，所以splay可以称得上是BST的ex版，所以splay从本质目的上来说已经算不上是平衡树了，所以我们给他一个名称——伸展树。

什么是SPLAY

伸展树（Splay Tree），也叫分裂树，是一种二叉排序树，它能在O(log n)内完成插入、查找，删除和区间翻转操作。它由丹尼尔·斯立特Daniel Sleator 和罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明的。

在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个非常贪的方法，在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。

它的优势在于不需要记录用于平衡树的冗余信息。

正常来说伸展树可以当作普通版平衡树，加强版平衡树和加强版线段树来用，下面我们就来重点谈论一下这两种用法和具体实现方法。

普通版平衡树用法

经典例题

作为加强版的平衡树，伸展树可以完成平衡树能做到的任何操作，即可以当作普通的平衡树完成平衡树的所有操作，不信？让我们来看一看平衡树最经典而又完全的例题吧：

[Luogu P3369] 【模板】普通平衡树
题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

插入 x 数
删除 x 数(若有多个相同的数，因只删除一个)
查询 x 数的排名(排名定义为比当前数小的数的个数 +1 。若有多个相同的数，因输出最小的排名)
查询排名为 x 的数
求 x 的前驱(前驱定义为小于 x ，且最大的数)
求 x 的后继(后继定义为大于 x ，且最小的数)

输入输出格式
输入格式：
第一行为 n ，表示操作的个数,下面 n 行每行有两个数 opt 和 x ，opt 表示操作的序号(1≤opt≤6 )

输出格式：
对于操作 3,4,5,6每行输出一个数，表示对应答案

输入输出样例
输入样例#1：
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
输出样例#1：
106465
84185
492737
说明
时空限制：1000ms,128M

对，这就是平衡树最基本的例题了，我们之前在二叉查找树和Treap的BLOG里都引用了这道例题，因为这道例题实在是太经典了，基本涵盖了平衡树的所有基本操作，所以这次我们也无法免俗地来看看如何用splay来解决这道题目。

SPLAY写法

在这里我们还是和Treap一样从头到尾一步一步教你学会写最基本的Splay！

定义结构体

int root;//根节点是谁
struct trnode
{
    int d,n,c,f,son[2];//d为值，f为父亲编号，c为控制的节点个数，n为同值节点的个数 
}tr[110000];int len;//树上有几个节点

对于每一个节点，我们要存储六个值——本身的值d，父亲是谁f，以我为根节点的子树有几个节点c，与我值相同的点有多少个n，左儿子是谁son[0]，以及右儿子是谁son[1]。至于为什么我写的是son[]数组而不是l，r在后面的程序你就知道了，这会让你的程序好写很多。

更新控制节点数

int update(int x)//更新x控制的节点数 
{
    int lc=tr[x].son[0];
    int rc=tr[x].son[1];
    tr[x].c=tr[lc].c+tr[rc].c+tr[x].n;
}

这个也是二叉平衡树的基本操作了，对于任意一个节点控制的子树大小，在操作过后是会发生变化的。这时，就要对点控制子树大小进行更新，这时子树大小就是左子树大小+右子树大小+我这个点存储的点的数量。

添加一个点

int add(int d,int f)//添加值为d的点，认f为父亲，f认它为孩子 
{
    len++;
    tr[len].d=d;tr[len].n=1;tr[len].c=1;
    tr[len].f=f; if(d<tr[f].d)tr[f].son[0]=len; else tr[f].son[1]=len;
    tr[len].son[0]=0;tr[len].son[1]=0;
}

和二叉查找树一样，在插入一个值为x的点时，如果树上之前没有值为x的点，我们就要开创一个值为x的点。在这个模块中，我们就实现添加值为d的点，给这点初始化一下，然后认f为父亲，f认它为孩子。

rotate旋转

int rotate(int x,int w)
{
    int f=tr[x].f,ff=tr[f].f;//在旋转之前先确定好x的父亲和爷爷
    //开始旋转建立关系
    int r,R;//r表示儿辈，R表示父辈 

    r=tr[x].son[w],R=tr[x].f;//x的儿子准备当x父亲的新儿子 
    tr[R].son[1-w]=r;
    if(r!=0)tr[r].f=R;

    r=x,R=ff;//x准备当他爷爷新孩子 
    if(tr[R].son[0]==f) tr[R].son[0]=r; else tr[R].son[1]=r;
    tr[r].f=R;

    r=f,R=x;//x的父亲当x的儿子 
    tr[R].son[w]=r; 
    tr[r].f=R; 

    update(f);
    update(x); 
}

和Treap一样，Splay的单次旋转也分为左旋和右旋，而且旋转方法完全一样，就让我我们一起来复习一下吧：

我们知道，旋转分为两种，左旋和右旋，比如我们要把x旋转向上，为了不破坏二叉查找树的性质，那么左旋和右旋是这样的：

单次旋转的程序也和Treap完全相同，在程序中，w=0时为左旋，w=1时为右旋，不理解的同学可以先去看一下Treap的旋转操作。

Splay操作

int splay(int x,int rt)//该函数是为了让x变为rt的孩子，无论是左孩子还是右孩子 
{
    while(tr[x].f!=rt)//如果rt是x的父亲，那么什么也不用做；不然就把x往上旋转 
    {
        int f=tr[x].f,ff=tr[f].f;//准备x的父亲和爷爷 
        if(ff==rt)//如果x的爷爷就是rt，那么只要x向上旋转一次（相当于跳一层） 
        {
            if(tr[f].son[0]==x)  rotate(x,1)  ;  else  rotate(x,0)  ;
        }

              if(tr[ff].son[0]==f  &&  tr[f].son[0]==x)  {rotate(f,1);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[1]==x)  {rotate(f,0);rotate(x,0);}
        else  if(tr[ff].son[0]==f  &&  tr[f].son[1]==x)  {rotate(x,0);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[0]==x)  {rotate(x,1);rotate(x,0);}

    }
    if(rt==0) root=x;
}

这个函数的目的是什么呢？就是不管x在多下面，都要把x旋转上来变成rt的孩子。具体是是怎么操作的呢？

实现我们先看一下，如果rt是x的父亲，那么什么也不用做；不然就把x往上旋转，那旋转多少步呢？我们先看一下，设x的父亲为f，ff为x的爷爷。

如果x的爷爷就是rt，那么只要x向上旋转一次（相当于跳一层）。如果ff还是rt下面的点，那么我们就先把x旋转上来到ff的位置，具体就根据f和ff的关系和x和f的关系，分为左左，右右，左右，右左四种情况，对应的代码就是

                  if(tr[ff].son[0]==f  &&  tr[f].son[0]==x)  {rotate(f,1);rotate(x,1);}
            else  if(tr[ff].son[1]==f  &&  tr[f].son[1]==x)  {rotate(f,0);rotate(x,0);}
            else  if(tr[ff].son[0]==f  &&  tr[f].son[1]==x)  {rotate(x,0);rotate(x,1);}
            else  if(tr[ff].son[1]==f  &&  tr[f].son[0]==x)  {rotate(x,1);rotate(x,0);}

具体怎么理解呢？我们一个一个来看：

对于第一种情况，也就是左左的情况，我们只要把f右旋，再把x右旋即可：

对于第二种情况，也就是右右的情况，我们只要把f左旋，再把x左旋即可：

对于第三种情况，也就是左右的情况，我们只要把x左旋，再把x右旋即可：

对于第四种情况，也就是右左的情况，我们只要把x右旋，再把x左旋即可：

是不是很简单易懂啊ovo

查找节点地址

int findip(int d)//找值为d的节点的地址，PS：如果不存在值为d的点，就找接近d的点（可能大也可能小） 
{
    int x=root;
    while(tr[x].d!=d)
    {
        if(d<tr[x].d)
        {
            if (tr[x].son[0]==0) break;
            else x=tr[x].son[0];
        }
        else//if(d>tr[x].d) 
        {
            if (tr[x].son[1]==0) break;
            else x=tr[x].son[1];
        }
    } 
    return x;
}

和二叉查找树一样，在操作当中我们需要多次寻找值为d的点在哪（比如删除节点），或者接近d的值在哪（比如加入一个节点，找到后插到它的儿子位置就好了）。我们就只需要从root开始，一层层往下，由于我们知道在二叉查找树当中，每个节点的左子节点都小于它，右子节点都大于它。所以我们只要一层层判断向左儿子走，右儿子走还是不走（找到值一样的点或者没有对应的儿子了）就好了。

插入数值为d的点

int ins(int d)//插入数值为d的点 
{
    if(root==0){ add(d,0); root=len; return 0; }
    int x=findip(d);

    if(tr[x].d==d)
    {
        tr[x].n++;
        update(x);
        splay(x,0);
    }
    else
    {
        add(d,x);
        update(x);
        splay(len,0);
    }

}

和二叉查找树一样，在插入一个值的时候，我们需要分两种情况进行讨论：

1.这棵树是空的
那么我们只要add一个点，然后root就是这点，就可以了。

2.这棵树不是空的
那么我们可以运用之前讲到的find函数，找到值为d的点在哪里。若存在值为d的点，那么直接这个点的n++就好了，代表多了一个这个值的点；若不存在值为d的点，这表示值为d的点应该出现在找到的这个点的儿子节点上，且这个儿子节点必为空，不然的话会继续findip()下去，找到的就不是这个点了。这个时候直接在找到点的对应儿子节点加上我们要添加的点就好了。

最后由于Splay的特殊策略，我们还要把新加入的节点splay到根节点。

删除数值为d的点

int del(int d)
{
    int x=findip(d);splay(x,0);

    if(tr[x].n>1){tr[x].n--; update(x); return 0;}
         if(tr[x].son[0]==0 && tr[x].son[1]==0){root=0;len=0;}
    else if(tr[x].son[0]==0 && tr[x].son[1]!=0){root=tr[x].son[1];tr[root].f=0;}
    else if(tr[x].son[0]!=0 && tr[x].son[1]==0){root=tr[x].son[0];tr[root].f=0;}
    else//if(tr[x].son[0]!=0 && tr[x].son[1]!=0)
    {
        int p=tr[x].son[0];
        while(tr[p].son[1]!=0)p=tr[p].son[1];
        splay(p,x);

        int r=tr[x].son[1],R=p;

        tr[R].son[1]=r;
        tr[r].f=R;

        root=R;tr[root].f=0;
        update(R);

    }
}

对比二叉查找树，splay有了旋转操作，对于删除操作的处理就简单很多了。如果这个点出现多次，即tr[x].n>1，那就直接减去一个，即tr[x].n即可。现在我们来讨论一下tr[x].n=1的情况：我们首先先把待删除点找到，然后旋转到根节点，接下来分四种情况进行讨论：

1.这个点没有左右儿子：又由于这时这个点以及旋转到了根节点，它又没有左右儿子，那删除后，这颗splay就空了，直接把根设为空，树的大小设为0即可。

2.这个点只有左子树：此时的操作也很简单，由于只有左节点，直接把整颗左子树顶上来，让左儿子当根节点就好了。

3.这个点只有右子树：此时的操作和2相似，由于只有右节点，直接把整颗右子树顶上来，让右儿子当根节点就好了。

4.既有左儿子又有右儿子：这个时候由于有了旋转操作就很好写。之前我们探讨过，当x作为根节点被删除时，把它左子树的最大值放到根节点，二叉搜索树的性质不会发生变化，那我们只要在这个时候把左子树的最右点旋转到左子树的根，把这个点设置为根，由于这个点在左子树种最大，所以此时它一定没有右儿子。所以直接把删除点的右儿子拼到它的右儿子上就好了。

寻找值为d的点的排名

int findpaiming(int d)//寻找值为d的点的排名 
{
    int x=findip(d);splay(x,0);
    return(tr[tr[x].son[0]].c+1);
}

这个操作也很简单，我们只要找到这个点的位置，设为x。把x旋转到根，根据二叉查找树的性质，左子树的所有元素都小于它，所以此时它的排名就是左子树大小加一。

寻找排名为d的点的值

int findshuzi(int k)//寻找排名为d的点的值
{
    int x=root;
    while(1) 
    {
        int lc=tr[x].son[0],rc=tr[x].son[1];
             if(k<=tr[lc].c) x=lc;
        else if(k>tr[lc].c+tr[x].n){k=k-tr[lc].c-tr[x].n;x=rc;}
        else break;
    }
    splay(x,0);
    return(tr[x].d);
}

和二叉查找树一样，我们要查询排名为x的数，那么我们就从根节点出发，遇到每一个节点都问一下这个点包含了多少个点啊，我们记为n，这个点的左子树有多少个点啊，我们记为l，这个右子树包含了多少点啊，我们记为r。

那么如果我们的k<=l,那就不用怀疑了，我们要查找的数在左子树里，且在左子树里也是第k大，递归去找左子树就好了。

如果我们的k>l+n,那么也不用怀疑了，这个点不可能在左子树和这个点上了，一定出现在右子树，且在右子树的排名为k-tr[lc].c-tr[x].n，注意，是k-tr[lc].c-tr[x].n，不是第k!!!这时我们递归去找右子树就好了。

剩下的情况呢？不在左子树也不在右子树，那是我们现在到的这个点了呀！直接输出就可以了！

寻找一个数的前驱

int findqianqu(int d)
{
    int x=findip(d);splay(x,0);

    if(tr[x].d>=d && tr[x].son[0]!=0)
    {
        x=tr[x].son[0];
        while(tr[x].son[1]!=0)x=tr[x].son[1];
    }

    if(tr[x].d>=d)x=0;
    return(tr[x].d);
}

这个操作也很简单，首先由于我们读入的这个数不一定在我们的二叉查找树上，所以我们先用findip()先把和这个数大小相近的点找到。

然后我们进行判断，如果此时我们得到的点的值小于读入的值，那就不用怀疑，前驱就是我们得到的点的值了，反之，我们就要把找到的点旋转到根，然后去找左子树的最大值，由于findip是和读入的数最接近的点，所以此时在左子树中找到的点一定小于读入点，所以为要求的前驱。

如果这时又没有左子树，那就没有前驱了，返回0就好了。

寻找一个数的后继

int findhouji(int d)
{
    int x=findip(d);splay(x,0);

    if(tr[x].d<=d && tr[x].son[1]!=0)
    {
        x=tr[x].son[1];
        while(tr[x].son[0]!=0)x=tr[x].son[0];
    }

    if(tr[x].d<=d)x=0;
    return(tr[x].d);
}

和找前驱类似，所以我们先用findip()先把和这个数大小相近的点找到。

然后我们进行判断，如果此时我们得到的点的值大于读入的值，那就不用怀疑，后继就是我们得到的点的值了，反之，我们就要把找到的点旋转到根，然后去找右子树的最小值，由于findip是和读入的数最接近的点，所以此时在右子树中找到的点一定大于读入点，所以为要求的前驱。

如果这时又没有右子树，那就没有后继了，返回0就好了。

主程序

int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int cz,x;
        scanf("%d%d",&cz,&x);
        if(cz==1)ins(x);
        if(cz==2)del(x);
        if(cz==3)printf("%d\n",findpaiming(x));
        if(cz==4)printf("%d\n",findshuzi(x));
        if(cz==5)printf("%d\n",findqianqu(x));
        if(cz==6)printf("%d\n",findhouji(x));
    }
    return 0; 
}

这部分非常简单，无脑套函数就好了。

完整代码

#include<cstdio>
#include<cstring>
using namespace std;
int root;
struct trnode
{
    int d,n,c,f,son[2];//d为值，f为父亲编号，c为控制的节点个数，n为同值节点的个数 
}tr[110000];int len;

int update(int x)//更新x控制的节点数 
{
    int lc=tr[x].son[0];
    int rc=tr[x].son[1];
    tr[x].c=tr[lc].c+tr[rc].c+tr[x].n;
}

int add(int d,int f)//添加值为d的点，认f为父亲，f认它为孩子 
{
    len++;
    tr[len].d=d;tr[len].n=1;tr[len].c=1;
    tr[len].f=f; if(d<tr[f].d)tr[f].son[0]=len; else tr[f].son[1]=len;
    tr[len].son[0]=0;tr[len].son[1]=0;
}

int rotate(int x,int w)
{
    int f=tr[x].f,ff=tr[f].f;//在旋转之前先确定好x的父亲和爷爷
    //开始旋转建立关系
    int r,R;//r表示儿辈，R表示父辈 

    r=tr[x].son[w],R=tr[x].f;//x的儿子准备当x父亲的新儿子 
    tr[R].son[1-w]=r;
    if(r!=0)tr[r].f=R;

    r=x,R=ff;//x准备当他爷爷新孩子 
    if(tr[R].son[0]==f) tr[R].son[0]=r; else tr[R].son[1]=r;
    tr[r].f=R;

    r=f,R=x;//x的父亲当x的儿子 
    tr[R].son[w]=r; 
    tr[r].f=R; 

    update(f);
    update(x); 
}

int splay(int x,int rt)//该函数是为了让x变为rt的孩子，无论是左孩子还是右孩子 
{
    while(tr[x].f!=rt)//如果rt是x的父亲，那么什么也不用做；不然就把x往上旋转 
    {
        int f=tr[x].f,ff=tr[f].f;//准备x的父亲和爷爷 
        if(ff==rt)//如果x的爷爷就是rt，那么只要x向上旋转一次（相当于跳一层） 
        {
            if(tr[f].son[0]==x)  rotate(x,1)  ;  else  rotate(x,0)  ;
        }

              if(tr[ff].son[0]==f  &&  tr[f].son[0]==x)  {rotate(f,1);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[1]==x)  {rotate(f,0);rotate(x,0);}
        else  if(tr[ff].son[0]==f  &&  tr[f].son[1]==x)  {rotate(x,0);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[0]==x)  {rotate(x,1);rotate(x,0);}

    }
    if(rt==0) root=x;
}

int findip(int d)//找值为d的节点的地址，PS：如果不存在值为d的点，就找接近d的点（可能大也可能小） 
{
    int x=root;
    while(tr[x].d!=d)
    {
        if(d<tr[x].d)
        {
            if (tr[x].son[0]==0) break;
            else x=tr[x].son[0];
        }
        else//if(d>tr[x].d) 
        {
            if (tr[x].son[1]==0) break;
            else x=tr[x].son[1];
        }
    } 
    return x;
}

int ins(int d)//插入数值为d的点 
{
    if(root==0){ add(d,0); root=len; return 0; }
    int x=findip(d);

    if(tr[x].d==d)
    {
        tr[x].n++;
        update(x);
        splay(x,0);
    }
    else
    {
        add(d,x);
        update(x);
        splay(len,0);
    }

}

int del(int d)
{
    int x=findip(d);splay(x,0);

    if(tr[x].n>1){tr[x].n--; update(x); return 0;}
         if(tr[x].son[0]==0 && tr[x].son[1]==0){root=0;len=0;}
    else if(tr[x].son[0]==0 && tr[x].son[1]!=0){root=tr[x].son[1];tr[root].f=0;}
    else if(tr[x].son[0]!=0 && tr[x].son[1]==0){root=tr[x].son[0];tr[root].f=0;}
    else//if(tr[x].son[0]!=0 && tr[x].son[1]!=0)
    {
        int p=tr[x].son[0];
        while(tr[p].son[1]!=0)p=tr[p].son[1];
        splay(p,x);

        int r=tr[x].son[1],R=p;

        tr[R].son[1]=r;
        tr[r].f=R;

        root=R;tr[root].f=0;
        update(R);

    }
}

int findpaiming(int d)//寻找值为d的点的排名 
{
    int x=findip(d);splay(x,0);
    return(tr[tr[x].son[0]].c+1);
}

int findshuzi(int k)//寻找排名为d的点的值
{
    int x=root;
    while(1) 
    {
        int lc=tr[x].son[0],rc=tr[x].son[1];
             if(k<=tr[lc].c) x=lc;
        else if(k>tr[lc].c+tr[x].n){k=k-tr[lc].c-tr[x].n;x=rc;}
        else break;
    }
    splay(x,0);
    return(tr[x].d);
} 

int findqianqu(int d)
{
    int x=findip(d);splay(x,0);

    if(tr[x].d>=d && tr[x].son[0]!=0)
    {
        x=tr[x].son[0];
        while(tr[x].son[1]!=0)x=tr[x].son[1];
    }

    if(tr[x].d>=d)x=0;
    return(tr[x].d);
}

int findhouji(int d)
{
    int x=findip(d);splay(x,0);

    if(tr[x].d<=d && tr[x].son[1]!=0)
    {
        x=tr[x].son[1];
        while(tr[x].son[0]!=0)x=tr[x].son[0];
    }

    if(tr[x].d<=d)x=0;
    return(tr[x].d);
}

int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int cz,x;
        scanf("%d%d",&cz,&x);
        if(cz==1)ins(x);
        if(cz==2)del(x);
        if(cz==3)printf("%d\n",findpaiming(x));
        if(cz==4)printf("%d\n",findshuzi(x));
        if(cz==5)printf("%d\n",findqianqu(x));
        if(cz==6)printf("%d\n",findhouji(x));
    }
    return 0; 
}

加强版平衡树

既然说它是加强版平衡树，那么它肯定能做到一些普通平衡树做不到的操作，比如最经典的，维护区间翻转后整个数列的样子。

经典例题

[luogu P3391]文艺平衡树
【题意描述】
写一种数据结构，来维护一个有序数列，其中需要提供以下操作：
翻转一个区间，例如原有序序列是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] 数据保证 1 < =l < = r < =n
（n,m < =100000）
【输出格式】
输出一行n个数字，表示原始序列经过m次变换后的结果
Sample Input
5 3
1 3
1 3
1 4
Sample Output
4 3 2 1 5

很明显，这道题要我们维护一个支持区间翻转的序列，那么一般的平衡树就已经做不了了，但是我们的SPLAY可以呀。

首先我们考虑如何翻转一个区间？假如我们要翻转[2,3,4]首先我们要先把这个区间分离出来，我们先把2-1，也就是1旋转到根，再把4+1也就是5旋转到1的右儿子，那么5的左儿子不就是我们要求的区间了吗？如下图：

那分离出区间后呢？就很简单了呀只要对这颗子树的每个点的区间进行翻转就可以了呀！

那样有的同学就会问了，如果是翻转[1,n]，这样就没有l-1和r+1了，怎么办？很简单，我们只要存储n+2个点，把【1，n】放到【2，n+1】即可解决。

那旋转后的序列怎么输出呢？我们发现由于此时的SPLAY基于的二叉排序树所基于的是在序列里的位置(即对于每个点，左子树的点排的都比它前，右子树的点排的都比它后)，所以只要中序遍历即可了。

程序也只要在原程序上进行一点点的增添。

增添的程序

定义结构体

struct trnode
{
    int d,n,c,f,son[2];//d为值，f为父亲编号，c为控制的节点个数，n为同值节点的个数 
    bool fz;//定义这个节点为根的子树是否需要翻转 
    trnode(){fz=false;}
}tr[110000];int len,llen;

对比普通平衡树的用法，在这里我们多了一个需要存储的量fz，表示这个点的左右子树是否需要翻转，true为是，false则不是。和lazy-tag的思路一样，在这个点左右子树交换后，fz会下传到左右儿子节点。

对序列翻转操作

int fz(int x,int y)
{
    int lc=findshuzi(x-1),rc=findshuzi(y+1);
    splay(lc,0);
    splay(rc,lc);
    int p=tr[rc].son[0];
    tr[p].fz=1-tr[p].fz;
    splay(p,0);

}

正如上面所说，我们只要把l-1旋转到头，r+1旋转到l-1的右儿子，那么r+1的左儿子就是我们要的区间了，给这颗子树的根节点打上标记就好了。

左右儿子交换与标记下传

int whfz(int x)//对x点进行左右子树翻转 
{
    tr[x].fz=false;
    int lc=tr[x].son[0],rc=tr[x].son[1];
    swap(tr[x].son[0],tr[x].son[1]);
    tr[lc].fz=1-tr[lc].fz;
    tr[rc].fz=1-tr[rc].fz;
}

翻转操作要做的事非常简单，就是把左右儿子交换，把fz标记下传，经此而已。

操作前的翻转

int findip(int d)//找值为d的节点的地址，PS：如果不存在值为d的点，就找接近d的点（可能大也可能小） 
{
    int x=root;
    while(tr[x].d!=d)
    {
        if(tr[x].fz==true)whfz(x);
        if(d<tr[x].d)
        {
            if (tr[x].son[0]==0) break;
            else x=tr[x].son[0];
        }
        else//if(d>tr[x].d) 
        {
            if (tr[x].son[1]==0) break;
            else x=tr[x].son[1];
        }
    } 
    return x;
}

int findshuzi(int k)//寻找排名为d的点的值
{
    int x=root;
    while(1) 
    {
        if(tr[x].fz==true)whfz(x);
        int lc=tr[x].son[0],rc=tr[x].son[1];
             if(k<=tr[lc].c) x=lc;
        else if(k>tr[lc].c+tr[x].n){k=k-tr[lc].c-tr[x].n;x=rc;}
        else break;
    }
    splay(x,0);
    return(tr[x].d);
}

我们发现在基本所有涉及到点所有操作中，都会有一步操作：判断当前到的点有没有翻转标记，有，就实行上一步的翻转操作。

我们再来看看比较特殊的splay：

int splay(int x,int rt)//该函数是为了让x变为rt的孩子，无论是左孩子还是右孩子 
{
    while(tr[x].f!=rt)//如果rt是x的父亲，那么什么也不用做；不然就把x往上旋转 
    {
        int f=tr[x].f,ff=tr[f].f;//准备x的父亲和爷爷 
        if(ff==rt)//如果x的爷爷就是rt，那么只要x向上旋转一次（相当于跳一层） 
        {
            if(tr[f].son[0]==x)  rotate(x,1)  ;  else  rotate(x,0)  ;
        }
            if(tr[x].fz==true)whfz(x);
            if(tr[f].fz==true){tr[f].fz=false;tr[x].fz=true;}

              if(tr[ff].son[0]==f  &&  tr[f].son[0]==x)  {rotate(f,1);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[1]==x)  {rotate(f,0);rotate(x,0);}
        else  if(tr[ff].son[0]==f  &&  tr[f].son[1]==x)  {rotate(x,0);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[0]==x)  {rotate(x,1);rotate(x,0);}

    }
    if(rt==0) root=x;
}

比较特殊的，在splay中，由于要考虑到当前点，当前点的父亲，当前点的爷爷三个点，所以不仅要考虑当前点的翻转操作，还有考虑到父亲节点的翻转操作，正如:

到这里，很多人会说，对于当前点的翻转很好懂，但是对于父亲节点，你都没有翻转啊，只是改了一下标记，这行得通吗？当然，我给你举一个例子：

假如我们要把蓝色节点旋转到绿色节点的位置，那么绿色节点就是父亲，由于旋转是不改变序列的顺序的，所以我们先看一下若不旋转，直接把父亲节点的子树下所有节点左右儿子互换，序列长这样：

同样的，我们从另一个角度，将操作点先向上旋转，变成这样：

再按照上面所说的，将父亲节点的fz变为false，把向上翻转的点的fz设为true，即把操作点向上翻转后，再把整颗子树的每个点的左右儿子交换后，变成这样：

我们发现两种操作的中序遍历结果一样，代表两种操作是等价的，那么具体为什么是等价感兴趣的同学可以自行证明。

查找中序遍历

int dfs(int x)
{
    if(tr[x].fz==true)whfz(x);
    if(tr[x].son[0]!=0)dfs(tr[x].son[0]);
    llen++;a[llen]=tr[x].d;
    if(tr[x].son[1]!=0)dfs(tr[x].son[1]);
    return 0;
}

这个就很简单了，按照正常中序遍历——左根右遍历即可，记得在看到fz=true的点时要记得交换左右子树并把标记下传。

完整代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int root;
struct trnode
{
    int d,n,c,f,son[2];//d为值，f为父亲编号，c为控制的节点个数，n为同值节点的个数 
    bool fz;//定义这个节点为根的子树是否需要翻转 
    trnode(){fz=false;}
}tr[110000];int len,llen;

int n,m,o,p,js,jl,x,y;
int a[110000];

int update(int x)//更新x控制的节点数 
{
    int lc=tr[x].son[0];
    int rc=tr[x].son[1];
    tr[x].c=tr[lc].c+tr[rc].c+tr[x].n;
}

int add(int d,int f)//添加值为d的点，认f为父亲，f认它为孩子 
{
    len++;
    tr[len].d=d;tr[len].n=1;tr[len].c=1;
    tr[len].f=f; if(d<tr[f].d)tr[f].son[0]=len; else tr[f].son[1]=len;
    tr[len].son[0]=0;tr[len].son[1]=0;
}

int whfz(int x)//对x点进行左右子树翻转 
{
    tr[x].fz=false;
    int lc=tr[x].son[0],rc=tr[x].son[1];
    swap(tr[x].son[0],tr[x].son[1]);
    tr[lc].fz=1-tr[lc].fz;
    tr[rc].fz=1-tr[rc].fz;
}

int rotate(int x,int w)
{
    int f=tr[x].f,ff=tr[f].f;//在旋转之前先确定好x的父亲和爷爷
    //开始旋转建立关系
    int r,R;//r表示儿辈，R表示父辈 

    r=tr[x].son[w],R=tr[x].f;//x的儿子准备当x父亲的新儿子 
    tr[R].son[1-w]=r;
    if(r!=0)tr[r].f=R;

    r=x,R=ff;//x准备当他爷爷新孩子 
    if(tr[R].son[0]==f) tr[R].son[0]=r; else tr[R].son[1]=r;
    tr[r].f=R;

    r=f,R=x;//x的父亲当x的儿子 
    tr[R].son[w]=r; 
    tr[r].f=R; 

    update(f);
    update(x); 
}

int splay(int x,int rt)//该函数是为了让x变为rt的孩子，无论是左孩子还是右孩子 
{
    while(tr[x].f!=rt)//如果rt是x的父亲，那么什么也不用做；不然就把x往上旋转 
    {
        int f=tr[x].f,ff=tr[f].f;//准备x的父亲和爷爷 
        if(ff==rt)//如果x的爷爷就是rt，那么只要x向上旋转一次（相当于跳一层） 
        {
            if(tr[f].son[0]==x)  rotate(x,1)  ;  else  rotate(x,0)  ;
        }
            if(tr[x].fz==true)whfz(x);
            if(tr[f].fz==true){tr[f].fz=false;tr[x].fz=true;}

              if(tr[ff].son[0]==f  &&  tr[f].son[0]==x)  {rotate(f,1);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[1]==x)  {rotate(f,0);rotate(x,0);}
        else  if(tr[ff].son[0]==f  &&  tr[f].son[1]==x)  {rotate(x,0);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[0]==x)  {rotate(x,1);rotate(x,0);}

    }
    if(rt==0) root=x;
}

int findip(int d)//找值为d的节点的地址，PS：如果不存在值为d的点，就找接近d的点（可能大也可能小） 
{
    int x=root;
    while(tr[x].d!=d)
    {
        if(tr[x].fz==true)whfz(x);
        if(d<tr[x].d)
        {
            if (tr[x].son[0]==0) break;
            else x=tr[x].son[0];
        }
        else//if(d>tr[x].d) 
        {
            if (tr[x].son[1]==0) break;
            else x=tr[x].son[1];
        }
    } 
    return x;
}

int findshuzi(int k)//寻找排名为d的点的值
{
    int x=root;
    while(1) 
    {
        if(tr[x].fz==true)whfz(x);
        int lc=tr[x].son[0],rc=tr[x].son[1];
             if(k<=tr[lc].c) x=lc;
        else if(k>tr[lc].c+tr[x].n){k=k-tr[lc].c-tr[x].n;x=rc;}
        else break;
    }
    splay(x,0);
    return(tr[x].d);
} 

int fz(int x,int y)
{
    int lc=findshuzi(x-1),rc=findshuzi(y+1);
    splay(lc,0);
    splay(rc,lc);
    int p=tr[rc].son[0];
    tr[p].fz=1-tr[p].fz;
    splay(p,0);

}

int ins(int d)//插入数值为d的点 
{
    if(root==0){ add(d,0); root=len; return 0; }
    int x=findip(d);

    if(tr[x].d==d)
    {
        tr[x].n++;
        update(x);
        splay(x,0);
    }
    else
    {
        add(d,x);
        update(x);
        splay(len,0);
    }

}

int dfs(int x)
{
    if(tr[x].fz==true)whfz(x);
    if(tr[x].son[0]!=0)dfs(tr[x].son[0]);
    llen++;a[llen]=tr[x].d;
    if(tr[x].son[1]!=0)dfs(tr[x].son[1]);
    return 0;
} 

int main()
{
    len=0;root=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n+2;i++)ins(i);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        x++;y++;
        fz(x,y);
    }

    llen=0;dfs(root);
    for(int i=2;i<llen;i++)printf("%d ",a[i]-1);
    return 0; 
}

加强版线段树

什么？平衡树还能当线段树来用？确实如此！我们来稍微修改一下上面这个例子：

[luogu 还没这题]粗鄙平衡树
【题意描述】
首先读入一个序列，
写一种数据结构，来维护这一个数列，其中需要提供以下操作：

翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，
结果是5 2 3 4 1
2.查找一个区间的最大值
【输入格式】
第一行为n,m n表示初始序列有n个数，
第二行n个数，代表这个序列开始时的数
m表示操作次数，接下来m行每行三个数[o,l,r] ,若o=1则翻转区间【l，r】，若o=2，查找区间【l，r】的最大值，数据保证 1 < =l < = r < =n
（n,m < =100000）
【输出格式】
每行一个数字，代表最大值。

这道题是不是让人耳目一新，但也是很好实现的。这道题的难点在于要在上一题的基础上支持对区间最值的查询。那就很简单了，只要在每个点加入一个存储值max，表示以这个点为根的子树的最大值，在每次update的时候顺便维护一下max值就好了，应该还是很好想到的，就不给出详细的代码了。

结语

在这篇BLOG中，我们彻底了解了splay的一些基本用法，请你务必好好消化这数据结构，因为splay真的超！级!重！要！希望你喜欢这篇BLOG！

Last modification：July 25th, 2018 at 04:18 pm

If you think my article is useful to you, please feel free to appreciate

One comment

校园
July 8th, 2023 at 03:47 pm

woshi

Reply

【蒟蒻数据结构】伸展树Splay

jvruo • 2018 年 07 月 23 日

我们在之前的BLOG已经多次提到了，平衡树的本质是BST(二叉查找树)，而平衡树的作用是为了加速二叉查找树，但不添加任何内容，可以说是BST的加速版。但是Splay却恰好相反，为了得到更多的功能，splay牺牲了时间和空间，其本质目的不是为了加速二叉排序树，而是为了增加一些普通二叉排序树所不具有的功能，所以splay可以称得上是BST的ex版，所以splay从本质目的上来说已经算不上是平衡树了，所以我们给他一个名称——伸展树。

什么是SPLAY

它的优势在于不需要记录用于平衡树的冗余信息。

正常来说伸展树可以当作普通版平衡树，加强版平衡树和加强版线段树来用，下面我们就来重点谈论一下这两种用法和具体实现方法。

普通版平衡树用法

经典例题

[Luogu P3369] 【模板】普通平衡树
题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

插入 x 数
删除 x 数(若有多个相同的数，因只删除一个)
查询 x 数的排名(排名定义为比当前数小的数的个数 +1 。若有多个相同的数，因输出最小的排名)
查询排名为 x 的数
求 x 的前驱(前驱定义为小于 x ，且最大的数)
求 x 的后继(后继定义为大于 x ，且最小的数)

输入输出格式
输入格式：
第一行为 n ，表示操作的个数,下面 n 行每行有两个数 opt 和 x ，opt 表示操作的序号(1≤opt≤6 )

输出格式：
对于操作 3,4,5,6每行输出一个数，表示对应答案

输入输出样例
输入样例#1：
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
输出样例#1：
106465
84185
492737
说明
时空限制：1000ms,128M

SPLAY写法

在这里我们还是和Treap一样从头到尾一步一步教你学会写最基本的Splay！

定义结构体

int root;//根节点是谁
struct trnode
{
    int d,n,c,f,son[2];//d为值，f为父亲编号，c为控制的节点个数，n为同值节点的个数 
}tr[110000];int len;//树上有几个节点

更新控制节点数

int update(int x)//更新x控制的节点数 
{
    int lc=tr[x].son[0];
    int rc=tr[x].son[1];
    tr[x].c=tr[lc].c+tr[rc].c+tr[x].n;
}

添加一个点

int add(int d,int f)//添加值为d的点，认f为父亲，f认它为孩子 
{
    len++;
    tr[len].d=d;tr[len].n=1;tr[len].c=1;
    tr[len].f=f; if(d<tr[f].d)tr[f].son[0]=len; else tr[f].son[1]=len;
    tr[len].son[0]=0;tr[len].son[1]=0;
}

rotate旋转

int rotate(int x,int w)
{
    int f=tr[x].f,ff=tr[f].f;//在旋转之前先确定好x的父亲和爷爷
    //开始旋转建立关系
    int r,R;//r表示儿辈，R表示父辈 

    r=tr[x].son[w],R=tr[x].f;//x的儿子准备当x父亲的新儿子 
    tr[R].son[1-w]=r;
    if(r!=0)tr[r].f=R;

    r=x,R=ff;//x准备当他爷爷新孩子 
    if(tr[R].son[0]==f) tr[R].son[0]=r; else tr[R].son[1]=r;
    tr[r].f=R;

    r=f,R=x;//x的父亲当x的儿子 
    tr[R].son[w]=r; 
    tr[r].f=R; 

    update(f);
    update(x); 
}

和Treap一样，Splay的单次旋转也分为左旋和右旋，而且旋转方法完全一样，就让我我们一起来复习一下吧：

我们知道，旋转分为两种，左旋和右旋，比如我们要把x旋转向上，为了不破坏二叉查找树的性质，那么左旋和右旋是这样的：

单次旋转的程序也和Treap完全相同，在程序中，w=0时为左旋，w=1时为右旋，不理解的同学可以先去看一下Treap的旋转操作。

Splay操作

int splay(int x,int rt)//该函数是为了让x变为rt的孩子，无论是左孩子还是右孩子 
{
    while(tr[x].f!=rt)//如果rt是x的父亲，那么什么也不用做；不然就把x往上旋转 
    {
        int f=tr[x].f,ff=tr[f].f;//准备x的父亲和爷爷 
        if(ff==rt)//如果x的爷爷就是rt，那么只要x向上旋转一次（相当于跳一层） 
        {
            if(tr[f].son[0]==x)  rotate(x,1)  ;  else  rotate(x,0)  ;
        }

              if(tr[ff].son[0]==f  &&  tr[f].son[0]==x)  {rotate(f,1);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[1]==x)  {rotate(f,0);rotate(x,0);}
        else  if(tr[ff].son[0]==f  &&  tr[f].son[1]==x)  {rotate(x,0);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[0]==x)  {rotate(x,1);rotate(x,0);}

    }
    if(rt==0) root=x;
}

这个函数的目的是什么呢？就是不管x在多下面，都要把x旋转上来变成rt的孩子。具体是是怎么操作的呢？

实现我们先看一下，如果rt是x的父亲，那么什么也不用做；不然就把x往上旋转，那旋转多少步呢？我们先看一下，设x的父亲为f，ff为x的爷爷。

                  if(tr[ff].son[0]==f  &&  tr[f].son[0]==x)  {rotate(f,1);rotate(x,1);}
            else  if(tr[ff].son[1]==f  &&  tr[f].son[1]==x)  {rotate(f,0);rotate(x,0);}
            else  if(tr[ff].son[0]==f  &&  tr[f].son[1]==x)  {rotate(x,0);rotate(x,1);}
            else  if(tr[ff].son[1]==f  &&  tr[f].son[0]==x)  {rotate(x,1);rotate(x,0);}

具体怎么理解呢？我们一个一个来看：

对于第一种情况，也就是左左的情况，我们只要把f右旋，再把x右旋即可：

对于第二种情况，也就是右右的情况，我们只要把f左旋，再把x左旋即可：

对于第三种情况，也就是左右的情况，我们只要把x左旋，再把x右旋即可：

对于第四种情况，也就是右左的情况，我们只要把x右旋，再把x左旋即可：

是不是很简单易懂啊ovo

查找节点地址

int findip(int d)//找值为d的节点的地址，PS：如果不存在值为d的点，就找接近d的点（可能大也可能小） 
{
    int x=root;
    while(tr[x].d!=d)
    {
        if(d<tr[x].d)
        {
            if (tr[x].son[0]==0) break;
            else x=tr[x].son[0];
        }
        else//if(d>tr[x].d) 
        {
            if (tr[x].son[1]==0) break;
            else x=tr[x].son[1];
        }
    } 
    return x;
}

插入数值为d的点

int ins(int d)//插入数值为d的点 
{
    if(root==0){ add(d,0); root=len; return 0; }
    int x=findip(d);

    if(tr[x].d==d)
    {
        tr[x].n++;
        update(x);
        splay(x,0);
    }
    else
    {
        add(d,x);
        update(x);
        splay(len,0);
    }

}

和二叉查找树一样，在插入一个值的时候，我们需要分两种情况进行讨论：

1.这棵树是空的
那么我们只要add一个点，然后root就是这点，就可以了。

最后由于Splay的特殊策略，我们还要把新加入的节点splay到根节点。

删除数值为d的点

int del(int d)
{
    int x=findip(d);splay(x,0);

    if(tr[x].n>1){tr[x].n--; update(x); return 0;}
         if(tr[x].son[0]==0 && tr[x].son[1]==0){root=0;len=0;}
    else if(tr[x].son[0]==0 && tr[x].son[1]!=0){root=tr[x].son[1];tr[root].f=0;}
    else if(tr[x].son[0]!=0 && tr[x].son[1]==0){root=tr[x].son[0];tr[root].f=0;}
    else//if(tr[x].son[0]!=0 && tr[x].son[1]!=0)
    {
        int p=tr[x].son[0];
        while(tr[p].son[1]!=0)p=tr[p].son[1];
        splay(p,x);

        int r=tr[x].son[1],R=p;

        tr[R].son[1]=r;
        tr[r].f=R;

        root=R;tr[root].f=0;
        update(R);

    }
}

2.这个点只有左子树：此时的操作也很简单，由于只有左节点，直接把整颗左子树顶上来，让左儿子当根节点就好了。

3.这个点只有右子树：此时的操作和2相似，由于只有右节点，直接把整颗右子树顶上来，让右儿子当根节点就好了。

寻找值为d的点的排名

int findpaiming(int d)//寻找值为d的点的排名 
{
    int x=findip(d);splay(x,0);
    return(tr[tr[x].son[0]].c+1);
}

寻找排名为d的点的值

int findshuzi(int k)//寻找排名为d的点的值
{
    int x=root;
    while(1) 
    {
        int lc=tr[x].son[0],rc=tr[x].son[1];
             if(k<=tr[lc].c) x=lc;
        else if(k>tr[lc].c+tr[x].n){k=k-tr[lc].c-tr[x].n;x=rc;}
        else break;
    }
    splay(x,0);
    return(tr[x].d);
}

那么如果我们的k<=l,那就不用怀疑了，我们要查找的数在左子树里，且在左子树里也是第k大，递归去找左子树就好了。

剩下的情况呢？不在左子树也不在右子树，那是我们现在到的这个点了呀！直接输出就可以了！

寻找一个数的前驱

int findqianqu(int d)
{
    int x=findip(d);splay(x,0);

    if(tr[x].d>=d && tr[x].son[0]!=0)
    {
        x=tr[x].son[0];
        while(tr[x].son[1]!=0)x=tr[x].son[1];
    }

    if(tr[x].d>=d)x=0;
    return(tr[x].d);
}

这个操作也很简单，首先由于我们读入的这个数不一定在我们的二叉查找树上，所以我们先用findip()先把和这个数大小相近的点找到。

如果这时又没有左子树，那就没有前驱了，返回0就好了。

寻找一个数的后继

int findhouji(int d)
{
    int x=findip(d);splay(x,0);

    if(tr[x].d<=d && tr[x].son[1]!=0)
    {
        x=tr[x].son[1];
        while(tr[x].son[0]!=0)x=tr[x].son[0];
    }

    if(tr[x].d<=d)x=0;
    return(tr[x].d);
}

和找前驱类似，所以我们先用findip()先把和这个数大小相近的点找到。

如果这时又没有右子树，那就没有后继了，返回0就好了。

主程序

int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int cz,x;
        scanf("%d%d",&cz,&x);
        if(cz==1)ins(x);
        if(cz==2)del(x);
        if(cz==3)printf("%d\n",findpaiming(x));
        if(cz==4)printf("%d\n",findshuzi(x));
        if(cz==5)printf("%d\n",findqianqu(x));
        if(cz==6)printf("%d\n",findhouji(x));
    }
    return 0; 
}

这部分非常简单，无脑套函数就好了。

完整代码

#include<cstdio>
#include<cstring>
using namespace std;
int root;
struct trnode
{
    int d,n,c,f,son[2];//d为值，f为父亲编号，c为控制的节点个数，n为同值节点的个数 
}tr[110000];int len;

int update(int x)//更新x控制的节点数 
{
    int lc=tr[x].son[0];
    int rc=tr[x].son[1];
    tr[x].c=tr[lc].c+tr[rc].c+tr[x].n;
}

int add(int d,int f)//添加值为d的点，认f为父亲，f认它为孩子 
{
    len++;
    tr[len].d=d;tr[len].n=1;tr[len].c=1;
    tr[len].f=f; if(d<tr[f].d)tr[f].son[0]=len; else tr[f].son[1]=len;
    tr[len].son[0]=0;tr[len].son[1]=0;
}

int rotate(int x,int w)
{
    int f=tr[x].f,ff=tr[f].f;//在旋转之前先确定好x的父亲和爷爷
    //开始旋转建立关系
    int r,R;//r表示儿辈，R表示父辈 

    r=tr[x].son[w],R=tr[x].f;//x的儿子准备当x父亲的新儿子 
    tr[R].son[1-w]=r;
    if(r!=0)tr[r].f=R;

    r=x,R=ff;//x准备当他爷爷新孩子 
    if(tr[R].son[0]==f) tr[R].son[0]=r; else tr[R].son[1]=r;
    tr[r].f=R;

    r=f,R=x;//x的父亲当x的儿子 
    tr[R].son[w]=r; 
    tr[r].f=R; 

    update(f);
    update(x); 
}

int splay(int x,int rt)//该函数是为了让x变为rt的孩子，无论是左孩子还是右孩子 
{
    while(tr[x].f!=rt)//如果rt是x的父亲，那么什么也不用做；不然就把x往上旋转 
    {
        int f=tr[x].f,ff=tr[f].f;//准备x的父亲和爷爷 
        if(ff==rt)//如果x的爷爷就是rt，那么只要x向上旋转一次（相当于跳一层） 
        {
            if(tr[f].son[0]==x)  rotate(x,1)  ;  else  rotate(x,0)  ;
        }

              if(tr[ff].son[0]==f  &&  tr[f].son[0]==x)  {rotate(f,1);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[1]==x)  {rotate(f,0);rotate(x,0);}
        else  if(tr[ff].son[0]==f  &&  tr[f].son[1]==x)  {rotate(x,0);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[0]==x)  {rotate(x,1);rotate(x,0);}

    }
    if(rt==0) root=x;
}

int findip(int d)//找值为d的节点的地址，PS：如果不存在值为d的点，就找接近d的点（可能大也可能小） 
{
    int x=root;
    while(tr[x].d!=d)
    {
        if(d<tr[x].d)
        {
            if (tr[x].son[0]==0) break;
            else x=tr[x].son[0];
        }
        else//if(d>tr[x].d) 
        {
            if (tr[x].son[1]==0) break;
            else x=tr[x].son[1];
        }
    } 
    return x;
}

int ins(int d)//插入数值为d的点 
{
    if(root==0){ add(d,0); root=len; return 0; }
    int x=findip(d);

    if(tr[x].d==d)
    {
        tr[x].n++;
        update(x);
        splay(x,0);
    }
    else
    {
        add(d,x);
        update(x);
        splay(len,0);
    }

}

int del(int d)
{
    int x=findip(d);splay(x,0);

    if(tr[x].n>1){tr[x].n--; update(x); return 0;}
         if(tr[x].son[0]==0 && tr[x].son[1]==0){root=0;len=0;}
    else if(tr[x].son[0]==0 && tr[x].son[1]!=0){root=tr[x].son[1];tr[root].f=0;}
    else if(tr[x].son[0]!=0 && tr[x].son[1]==0){root=tr[x].son[0];tr[root].f=0;}
    else//if(tr[x].son[0]!=0 && tr[x].son[1]!=0)
    {
        int p=tr[x].son[0];
        while(tr[p].son[1]!=0)p=tr[p].son[1];
        splay(p,x);

        int r=tr[x].son[1],R=p;

        tr[R].son[1]=r;
        tr[r].f=R;

        root=R;tr[root].f=0;
        update(R);

    }
}

int findpaiming(int d)//寻找值为d的点的排名 
{
    int x=findip(d);splay(x,0);
    return(tr[tr[x].son[0]].c+1);
}

int findshuzi(int k)//寻找排名为d的点的值
{
    int x=root;
    while(1) 
    {
        int lc=tr[x].son[0],rc=tr[x].son[1];
             if(k<=tr[lc].c) x=lc;
        else if(k>tr[lc].c+tr[x].n){k=k-tr[lc].c-tr[x].n;x=rc;}
        else break;
    }
    splay(x,0);
    return(tr[x].d);
} 

int findqianqu(int d)
{
    int x=findip(d);splay(x,0);

    if(tr[x].d>=d && tr[x].son[0]!=0)
    {
        x=tr[x].son[0];
        while(tr[x].son[1]!=0)x=tr[x].son[1];
    }

    if(tr[x].d>=d)x=0;
    return(tr[x].d);
}

int findhouji(int d)
{
    int x=findip(d);splay(x,0);

    if(tr[x].d<=d && tr[x].son[1]!=0)
    {
        x=tr[x].son[1];
        while(tr[x].son[0]!=0)x=tr[x].son[0];
    }

    if(tr[x].d<=d)x=0;
    return(tr[x].d);
}

int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int cz,x;
        scanf("%d%d",&cz,&x);
        if(cz==1)ins(x);
        if(cz==2)del(x);
        if(cz==3)printf("%d\n",findpaiming(x));
        if(cz==4)printf("%d\n",findshuzi(x));
        if(cz==5)printf("%d\n",findqianqu(x));
        if(cz==6)printf("%d\n",findhouji(x));
    }
    return 0; 
}

加强版平衡树

既然说它是加强版平衡树，那么它肯定能做到一些普通平衡树做不到的操作，比如最经典的，维护区间翻转后整个数列的样子。

经典例题

[luogu P3391]文艺平衡树
【题意描述】
写一种数据结构，来维护一个有序数列，其中需要提供以下操作：
翻转一个区间，例如原有序序列是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] 数据保证 1 < =l < = r < =n
（n,m < =100000）
【输出格式】
输出一行n个数字，表示原始序列经过m次变换后的结果
Sample Input
5 3
1 3
1 3
1 4
Sample Output
4 3 2 1 5

很明显，这道题要我们维护一个支持区间翻转的序列，那么一般的平衡树就已经做不了了，但是我们的SPLAY可以呀。

那分离出区间后呢？就很简单了呀只要对这颗子树的每个点的区间进行翻转就可以了呀！

那样有的同学就会问了，如果是翻转[1,n]，这样就没有l-1和r+1了，怎么办？很简单，我们只要存储n+2个点，把【1，n】放到【2，n+1】即可解决。

程序也只要在原程序上进行一点点的增添。

增添的程序

定义结构体

struct trnode
{
    int d,n,c,f,son[2];//d为值，f为父亲编号，c为控制的节点个数，n为同值节点的个数 
    bool fz;//定义这个节点为根的子树是否需要翻转 
    trnode(){fz=false;}
}tr[110000];int len,llen;

对序列翻转操作

int fz(int x,int y)
{
    int lc=findshuzi(x-1),rc=findshuzi(y+1);
    splay(lc,0);
    splay(rc,lc);
    int p=tr[rc].son[0];
    tr[p].fz=1-tr[p].fz;
    splay(p,0);

}

正如上面所说，我们只要把l-1旋转到头，r+1旋转到l-1的右儿子，那么r+1的左儿子就是我们要的区间了，给这颗子树的根节点打上标记就好了。

左右儿子交换与标记下传

int whfz(int x)//对x点进行左右子树翻转 
{
    tr[x].fz=false;
    int lc=tr[x].son[0],rc=tr[x].son[1];
    swap(tr[x].son[0],tr[x].son[1]);
    tr[lc].fz=1-tr[lc].fz;
    tr[rc].fz=1-tr[rc].fz;
}

翻转操作要做的事非常简单，就是把左右儿子交换，把fz标记下传，经此而已。

操作前的翻转

int findip(int d)//找值为d的节点的地址，PS：如果不存在值为d的点，就找接近d的点（可能大也可能小） 
{
    int x=root;
    while(tr[x].d!=d)
    {
        if(tr[x].fz==true)whfz(x);
        if(d<tr[x].d)
        {
            if (tr[x].son[0]==0) break;
            else x=tr[x].son[0];
        }
        else//if(d>tr[x].d) 
        {
            if (tr[x].son[1]==0) break;
            else x=tr[x].son[1];
        }
    } 
    return x;
}

int findshuzi(int k)//寻找排名为d的点的值
{
    int x=root;
    while(1) 
    {
        if(tr[x].fz==true)whfz(x);
        int lc=tr[x].son[0],rc=tr[x].son[1];
             if(k<=tr[lc].c) x=lc;
        else if(k>tr[lc].c+tr[x].n){k=k-tr[lc].c-tr[x].n;x=rc;}
        else break;
    }
    splay(x,0);
    return(tr[x].d);
}

我们发现在基本所有涉及到点所有操作中，都会有一步操作：判断当前到的点有没有翻转标记，有，就实行上一步的翻转操作。

我们再来看看比较特殊的splay：

int splay(int x,int rt)//该函数是为了让x变为rt的孩子，无论是左孩子还是右孩子 
{
    while(tr[x].f!=rt)//如果rt是x的父亲，那么什么也不用做；不然就把x往上旋转 
    {
        int f=tr[x].f,ff=tr[f].f;//准备x的父亲和爷爷 
        if(ff==rt)//如果x的爷爷就是rt，那么只要x向上旋转一次（相当于跳一层） 
        {
            if(tr[f].son[0]==x)  rotate(x,1)  ;  else  rotate(x,0)  ;
        }
            if(tr[x].fz==true)whfz(x);
            if(tr[f].fz==true){tr[f].fz=false;tr[x].fz=true;}

              if(tr[ff].son[0]==f  &&  tr[f].son[0]==x)  {rotate(f,1);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[1]==x)  {rotate(f,0);rotate(x,0);}
        else  if(tr[ff].son[0]==f  &&  tr[f].son[1]==x)  {rotate(x,0);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[0]==x)  {rotate(x,1);rotate(x,0);}

    }
    if(rt==0) root=x;
}

到这里，很多人会说，对于当前点的翻转很好懂，但是对于父亲节点，你都没有翻转啊，只是改了一下标记，这行得通吗？当然，我给你举一个例子：

同样的，我们从另一个角度，将操作点先向上旋转，变成这样：

我们发现两种操作的中序遍历结果一样，代表两种操作是等价的，那么具体为什么是等价感兴趣的同学可以自行证明。

查找中序遍历

int dfs(int x)
{
    if(tr[x].fz==true)whfz(x);
    if(tr[x].son[0]!=0)dfs(tr[x].son[0]);
    llen++;a[llen]=tr[x].d;
    if(tr[x].son[1]!=0)dfs(tr[x].son[1]);
    return 0;
}

这个就很简单了，按照正常中序遍历——左根右遍历即可，记得在看到fz=true的点时要记得交换左右子树并把标记下传。

完整代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int root;
struct trnode
{
    int d,n,c,f,son[2];//d为值，f为父亲编号，c为控制的节点个数，n为同值节点的个数 
    bool fz;//定义这个节点为根的子树是否需要翻转 
    trnode(){fz=false;}
}tr[110000];int len,llen;

int n,m,o,p,js,jl,x,y;
int a[110000];

int update(int x)//更新x控制的节点数 
{
    int lc=tr[x].son[0];
    int rc=tr[x].son[1];
    tr[x].c=tr[lc].c+tr[rc].c+tr[x].n;
}

int add(int d,int f)//添加值为d的点，认f为父亲，f认它为孩子 
{
    len++;
    tr[len].d=d;tr[len].n=1;tr[len].c=1;
    tr[len].f=f; if(d<tr[f].d)tr[f].son[0]=len; else tr[f].son[1]=len;
    tr[len].son[0]=0;tr[len].son[1]=0;
}

int whfz(int x)//对x点进行左右子树翻转 
{
    tr[x].fz=false;
    int lc=tr[x].son[0],rc=tr[x].son[1];
    swap(tr[x].son[0],tr[x].son[1]);
    tr[lc].fz=1-tr[lc].fz;
    tr[rc].fz=1-tr[rc].fz;
}

int rotate(int x,int w)
{
    int f=tr[x].f,ff=tr[f].f;//在旋转之前先确定好x的父亲和爷爷
    //开始旋转建立关系
    int r,R;//r表示儿辈，R表示父辈 

    r=tr[x].son[w],R=tr[x].f;//x的儿子准备当x父亲的新儿子 
    tr[R].son[1-w]=r;
    if(r!=0)tr[r].f=R;

    r=x,R=ff;//x准备当他爷爷新孩子 
    if(tr[R].son[0]==f) tr[R].son[0]=r; else tr[R].son[1]=r;
    tr[r].f=R;

    r=f,R=x;//x的父亲当x的儿子 
    tr[R].son[w]=r; 
    tr[r].f=R; 

    update(f);
    update(x); 
}

int splay(int x,int rt)//该函数是为了让x变为rt的孩子，无论是左孩子还是右孩子 
{
    while(tr[x].f!=rt)//如果rt是x的父亲，那么什么也不用做；不然就把x往上旋转 
    {
        int f=tr[x].f,ff=tr[f].f;//准备x的父亲和爷爷 
        if(ff==rt)//如果x的爷爷就是rt，那么只要x向上旋转一次（相当于跳一层） 
        {
            if(tr[f].son[0]==x)  rotate(x,1)  ;  else  rotate(x,0)  ;
        }
            if(tr[x].fz==true)whfz(x);
            if(tr[f].fz==true){tr[f].fz=false;tr[x].fz=true;}

              if(tr[ff].son[0]==f  &&  tr[f].son[0]==x)  {rotate(f,1);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[1]==x)  {rotate(f,0);rotate(x,0);}
        else  if(tr[ff].son[0]==f  &&  tr[f].son[1]==x)  {rotate(x,0);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[0]==x)  {rotate(x,1);rotate(x,0);}

    }
    if(rt==0) root=x;
}

int findip(int d)//找值为d的节点的地址，PS：如果不存在值为d的点，就找接近d的点（可能大也可能小） 
{
    int x=root;
    while(tr[x].d!=d)
    {
        if(tr[x].fz==true)whfz(x);
        if(d<tr[x].d)
        {
            if (tr[x].son[0]==0) break;
            else x=tr[x].son[0];
        }
        else//if(d>tr[x].d) 
        {
            if (tr[x].son[1]==0) break;
            else x=tr[x].son[1];
        }
    } 
    return x;
}

int findshuzi(int k)//寻找排名为d的点的值
{
    int x=root;
    while(1) 
    {
        if(tr[x].fz==true)whfz(x);
        int lc=tr[x].son[0],rc=tr[x].son[1];
             if(k<=tr[lc].c) x=lc;
        else if(k>tr[lc].c+tr[x].n){k=k-tr[lc].c-tr[x].n;x=rc;}
        else break;
    }
    splay(x,0);
    return(tr[x].d);
} 

int fz(int x,int y)
{
    int lc=findshuzi(x-1),rc=findshuzi(y+1);
    splay(lc,0);
    splay(rc,lc);
    int p=tr[rc].son[0];
    tr[p].fz=1-tr[p].fz;
    splay(p,0);

}

int ins(int d)//插入数值为d的点 
{
    if(root==0){ add(d,0); root=len; return 0; }
    int x=findip(d);

    if(tr[x].d==d)
    {
        tr[x].n++;
        update(x);
        splay(x,0);
    }
    else
    {
        add(d,x);
        update(x);
        splay(len,0);
    }

}

int dfs(int x)
{
    if(tr[x].fz==true)whfz(x);
    if(tr[x].son[0]!=0)dfs(tr[x].son[0]);
    llen++;a[llen]=tr[x].d;
    if(tr[x].son[1]!=0)dfs(tr[x].son[1]);
    return 0;
} 

int main()
{
    len=0;root=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n+2;i++)ins(i);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        x++;y++;
        fz(x,y);
    }

    llen=0;dfs(root);
    for(int i=2;i<llen;i++)printf("%d ",a[i]-1);
    return 0; 
}

加强版线段树

什么？平衡树还能当线段树来用？确实如此！我们来稍微修改一下上面这个例子：

[luogu 还没这题]粗鄙平衡树
【题意描述】
首先读入一个序列，
写一种数据结构，来维护这一个数列，其中需要提供以下操作：

翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，
结果是5 2 3 4 1
2.查找一个区间的最大值
【输入格式】
第一行为n,m n表示初始序列有n个数，
第二行n个数，代表这个序列开始时的数
m表示操作次数，接下来m行每行三个数[o,l,r] ,若o=1则翻转区间【l，r】，若o=2，查找区间【l，r】的最大值，数据保证 1 < =l < = r < =n
（n,m < =100000）
【输出格式】
每行一个数字，代表最大值。

结语

在这篇BLOG中，我们彻底了解了splay的一些基本用法，请你务必好好消化这数据结构，因为splay真的超！级!重！要！希望你喜欢这篇BLOG！

什么是SPLAY

普通版平衡树用法

经典例题

SPLAY写法

定义结构体

更新控制节点数

添加一个点

rotate旋转

Splay操作

查找节点地址

插入数值为d的点

删除数值为d的点

寻找值为d的点的排名

寻找排名为d的点的值

寻找一个数的前驱

寻找一个数的后继

主程序

完整代码

加强版平衡树

经典例题

增添的程序

定义结构体

对序列翻转操作

左右儿子交换与标记下传

操作前的翻转

查找中序遍历

完整代码

加强版线段树

结语

One comment