splay树

概念

splay树也是一种二叉查找树，同时也会通过旋转的操作保证一定的平衡。与普通的平衡树 (AVL) 相区别的是它可以将需要的节点不断向根节点旋转，这个过程被称作伸展。splay树可以高效的完成区间删除、区间插入、区间翻转以及其他二叉排序树的功能。这里以 HDU-3487为例，介绍splay树的一些基本功能。

基本结构

splay树的结构跟 AVL 基本一致，一般需要记录每个节点的子节点、父节点编号，权值和子树大小。因为有一些区间操作，lazytag再次帮上了忙，在本次例题中用于记录区间是否被翻转。

struct N
{
    int val;
    int ch[2];//0为左节点编号，1为右节点编号
    int fa;//父节点编号
    int size;//子树大小
    int lazytag;//值为1和0，表示区间是否被翻转
};

因为有旋转这种操作存在，所以树的根节点并不是固定的，所以还需要定义一个变量 rt 记录当前的根节点。

建树

建树的方法可以分为在线和离线两种。在线方式就是不断地插入新节点，离线方式接近线段树的建树方法。一般来说离线的方式时间复杂度更低，但是不是所有情况都能用。本次例题可以使用离线方式。

void build(int l, int r, int i)
{
    if(l > r) return;//判定边界
    //初始化
    Tree[i].lazytag = 0;
    Tree[i].ch[0] = Tree[i].ch[1] = 0;
    Tree[i].fa = i >> 1;//又是熟悉的认爹方式
    Tree[i >> 1].ch[i & 1] = i;//显然从编号的奇偶可以看出他是左节点还是右节点
    int mid = (l + r) >> 1;
    Tree[i].val = mid;
    if(l == r)
    {
        Tree[i].size = 1;
        return;
    }
    //注意这里跟平时的二分不一样，我们要扣掉中间的mid
    build(l, mid - 1, i << 1);
    build(mid + 1, r, i << 1 | 1);
    pushUp(i);//这里是用于更新节点所在的子树大小(两个子节点size的和再加 1)
}

旋转

单次旋转的思路跟 AVL 中的 LL 和 RR 完全一致。不过在 AVL中旋转的目的是维护子树的平衡，而这里的目的是与父节点交换位置

int get(int i)
{
    return Tree[Tree[i].fa].ch[1] == i;
}

void rotate(int i)
{
   int fai = Tree[i].fa;//爹
   int t = get(i);//自己和爹的关系，0为左，1为右
   int a = Tree[i].ch[!t];//自己即将失去的子树
   int fafa = Tree[fai].fa;//祖父节点
   Tree[i].ch[!t] = fai;
   Tree[fai].fa = i;
   Tree[fai].ch[t] = a;
   Tree[a].fa = fai;
   Tree[i].fa = fafa;
   Tree[fafa].ch[(fai == Tree[fafa].ch[1])] = i;
   pushUp(fai);//更新size
   pushUp(i);
}

伸展splay

这里就是splay最核心的操作。splay树为了提高搜索效率，要求我们把使用频率更高的节点放在靠上的位置。实现这一需求的方法就是当我们每次访问完一个节点后都必须要把它旋转到根节点的位置。但是为了维护住树的平衡性，我们在旋转的时候并不是一路跑到黑，具体规则如下：

1. 如果自己和父节点的关系与父节点和祖父节点的关系相同 (例如父节点是祖父节点的左子节点，同时自己也是父节点的左子节点) ，那么就先将父节点向上旋转，再自己向上旋转。
2. 但是如果父节点就是目标位置，那么只需要自己向上旋转一次。
3. 如果不满足第一条，也只需要自己向上旋转一次。

代码大概长这样

void splay(int i, int goal)//goal代表目标位置的父节点，这个目标位置不一定是根节点 为了方便，根节点的父节点编号为 0
{
    while(Tree[i].fa != goal)
    {
        int fai = Tree[i].fa;//爹
        int fafa = Tree[fai].fa;//爷
        pushDown(fafa);//这几个pushdown用于处理下放lazytag
        pushDown(fai);
        pushDown(i);
        if(fafa != goal && get(fai) == get(i))
        {
            rotate(fai);//转爹
        }
        rotate(i);//转自己
    }
    if(goal == 0) rt = i;//如果目标位置是根节点，那么根节点编号就需要更新一下
}

区间操作

如果splay的伸展操作其实还有妙用。因为splay树拥有二叉排序树的性质，所以我们可以由此方便的获取一些区间。

这是一个二叉排序树，对于被涂上色的部分来说，他们恰好可以代表区间 (a1, a3)。而当我们可以使用splay操作后，我们可以把我们想要的节点旋转到 编号 1 和 3 的位置，此时这棵子树上的所有元素就组成了我们想要的区间。想要删除区间？把这颗子树删了就行；想要翻转区间？直接去改这个子树的 lazytag；想要移动区间？先把这棵树拿下来，再把目标位置和它的相邻位置转上去，把树接回去就好了……这里就是splay树最优美的地方。这里附上例题用到的区间移动和区间翻转。

void cut(int a, int b, int c)
{
    //为了防止越界，我在树中多加了两个边界元素 0 和 n ，但是因此所有数字都要串一位，区间翻转那里也有这一部分
    a++;
    b++;
    c++;
    int aa = findx(a - 1);// 在二叉排序树中寻找第 x 小的值的位置，因为跟AVL写法一样，这里就不放了
    splay(aa, 0);// 把 a-1转到根节点
    int bb = findx(b + 1);
    splay(bb, rt);// 把 b+1转到根节点的右节点
    int now = Tree[Tree[rt].ch[1]].ch[0]; // 那么根节点的右节点的左子树就是我们要的区间，保存好
    Tree[Tree[rt].ch[1]].ch[0] = 0;//暂时删掉
    pushUp(Tree[rt].ch[1]);
    pushUp(rt);
    int cc = findx(c);
    splay(cc, 0);//把要插入的位置前一个节点转到根节点
    int dd = findx(c + 1);
    splay(dd, rt);//把要插入的位置后一个节点转到根节点的右节点
    Tree[now].fa = Tree[rt].ch[1];//把刚刚找到的区间接到新的位置
    Tree[Tree[rt].ch[1]].ch[0] = now;
    pushUp(Tree[rt].ch[1]);
    pushUp(rt);
}

void flip(int a, int b)
{
    a++;
    b++;
    int aa = findx(a - 1);
    splay(aa, 0);
    int bb = findx(b + 1);
    splay(bb, rt);
    Tree[Tree[Tree[rt].ch[1]].ch[0]].lazytag ^= 1;
}

HDU3487

最后放上完整代码。代码的个人风格比较重，ac 了之后也没有继续优化，可能存在一些小问题和一些过于冗杂的写法，欢迎大家一起讨论！

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

inline int read()
{
    int num = 0, fu = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') fu = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){num = (num << 3) + (num << 1) + ch - '0'; ch = getchar();}
    return num * fu;
}

int n, m;

struct N
{
    int val;
    int ch[2];
    int fa;
    int size;
    int lazytag;
};
N Tree[300010 << 2];
int rt = 1;

void pushUp(int i)
{
    Tree[i].size = Tree[Tree[i].ch[0]].size + Tree[Tree[i].ch[1]].size + 1;
}

void pushDown(int i)
{
    if(Tree[i].lazytag)
    {
        swap(Tree[i].ch[0], Tree[i].ch[1]);
        int lson = Tree[i].ch[0], rson = Tree[i].ch[1];
        if(lson) Tree[lson].lazytag ^= 1;
        if(rson) Tree[rson].lazytag ^= 1;
        Tree[i].lazytag = 0;
    }
}

void print(int i, int& cnt)
{
    if(i == 0) return;
    pushDown(i);
    print(Tree[i].ch[0], cnt);
    if(Tree[i].val >= 1 && Tree[i].val <= n) printf("%d%c", Tree[i].val, ++cnt == n ? '\n' : ' ');
    print(Tree[i].ch[1], cnt);
}

void build(int l, int r, int i)
{
    if(l > r) return;
    Tree[i].lazytag = 0;
    Tree[i].ch[0] = Tree[i].ch[1] = 0;
    Tree[i].fa = i >> 1;
    Tree[i >> 1].ch[i & 1] = i;
    int mid = (l + r) >> 1;
    Tree[i].val = mid;
    if(l == r)
    {
        Tree[i].size = 1;
        return;
    }
    build(l, mid - 1, i << 1);
    build(mid + 1, r, i << 1 | 1);
    pushUp(i);
}
int get(int i)
{
    return Tree[Tree[i].fa].ch[1] == i;
}

void rotate(int i)
{
   int fai = Tree[i].fa;
   int t = get(i);
   int a = Tree[i].ch[!t];
   int fafa = Tree[fai].fa;
   Tree[i].ch[!t] = fai;
   Tree[fai].fa = i;
   Tree[fai].ch[t] = a;
   Tree[a].fa = fai;
   Tree[i].fa = fafa;
   Tree[fafa].ch[(fai == Tree[fafa].ch[1])] = i;
   pushUp(fai);
   pushUp(i);
}

void splay(int i, int goal)
{
    while(Tree[i].fa != goal)
    {
        int fai = Tree[i].fa;
        int fafa = Tree[fai].fa;
        pushDown(fafa);
        pushDown(fai);
        pushDown(i);
        if(fafa != goal && get(fai) == get(i))
        {
            rotate(fai);
        }
        rotate(i);
    }
    if(goal == 0) rt = i;
}

int findx(int x)
{
    int t = 0;
    int cur = rt;
    while(cur != 0)
    {
        pushDown(cur);
        int now = Tree[Tree[cur].ch[0]].size;
        if(now + t + 1 < x)
        {
            t += now + 1;
            cur = Tree[cur].ch[1];
        }
        else if(now + t + 1 > x)
        {
            cur = Tree[cur].ch[0];
        }
        else
        {
            return cur;
        }
    }
    return 0;
}

void cut(int a, int b, int c)
{
    a++;
    b++;
    c++;
    int aa = findx(a - 1);
    splay(aa, 0);
    int bb = findx(b + 1);
    splay(bb, rt);
    int now = Tree[Tree[rt].ch[1]].ch[0];
    Tree[Tree[rt].ch[1]].ch[0] = 0;
    pushUp(Tree[rt].ch[1]);
    pushUp(rt);
    int cc = findx(c);
    splay(cc, 0);
    int dd = findx(c + 1);
    splay(dd, rt);
    Tree[now].fa = Tree[rt].ch[1];
    Tree[Tree[rt].ch[1]].ch[0] = now;
    pushUp(Tree[rt].ch[1]);
    pushUp(rt);
}

void flip(int a, int b)
{
    a++;
    b++;
    int aa = findx(a - 1);
    splay(aa, 0);
    int bb = findx(b + 1);
    splay(bb, rt);
    Tree[Tree[Tree[rt].ch[1]].ch[0]].lazytag ^= 1;
}

int main()
{
    while(scanf("%d%d", &n, &m))
    {
        if(n == -1 && m == -1) return 0;
        rt = 1;
        build(0, n+1, 1);
        for(int i=1; i<=m; i++)
        {
            char ch = getchar();
            while(ch < 'A' || ch > 'Z') ch = getchar();
            if(ch == 'C')
            {
                int a = read(), b = read(), c = read();
                cut(a, b, c);
            }
            else
            {
                int a = read(), b = read();
                flip(a, b);
            }
        }
        int cnt = 0;
        print(rt, cnt);
    }
    return 0;
}

题单（持续更新中）