经典引文

空间效率：O(n)

时间效率：O(log n)插入、查找、删除

创造者：Daniel Sleator 和 Robert Tarjan

优点：每次查询会调整树的结构，使被查询频率高的条目更靠近树根。

Tree Rotation

树的旋转是splay的基础，对于二叉查找树来说，树的旋转不破坏查找树的结构。

Splaying

Splaying是Splay Tree中的基本操作，为了让被查询的条目更接近树根，Splay Tree使用了树的旋转操作，同时保证二叉排序树的性质不变。

Splaying的操作受以下三种因素影响：

节点x是父节点p的左孩子还是右孩子
节点p是不是根节点，如果不是
节点p是父节点g的左孩子还是右孩子

同时有三种基本操作：

Zig Step

当p为根节点时，进行zip step操作。

当x是p的左孩子时，对x右旋；

当x是p的右孩子时，对x左旋。

Zig-Zig Step

当p不是根节点，且x和p同为左孩子或右孩子时进行Zig-Zig操作。

当x和p同为左孩子时，依次将p和x右旋；

当x和p同为右孩子时，依次将p和x左旋。

Zig-Zag Step

当p不是根节点，且x和p不同为左孩子或右孩子时，进行Zig-Zag操作。

当p为左孩子，x为右孩子时，将x左旋后再右旋。

当p为右孩子，x为左孩子时，将x右旋后再左旋。

应用

Splay Tree可以方便的解决一些区间问题，根据不同形状二叉树中序遍历结果不变的特性，可以将区间按顺序建二叉查找树。

每次自下而上的一套splay都可以将x移动到根节点的位置，利用这个特性，可以方便的利用Lazy的思想进行区间操作。

对于每个节点记录size，代表子树中节点的数目，这样就可以很方便地查找区间中的第k小或第k大元素。

对于一段要处理的区间[x, y]，首先splay x-1到root，再splay y+1到root的右孩子，这时root的右孩子的左孩子对应子树就是整个区间。

这样，大部分区间问题都可以很方便的解决，操作同样也适用于一个或多个条目的添加或删除，和区间的移动。

最后附上自己写的洛谷的模板题的代码：　

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+;

int n,m,root,tot;

struct Node{

  int ch[],size;

  int fa,mark,val;

  void add(int x,int y){

    ch[]=ch[]=mark=;

    val=x;fa=y;size=;}

}t[N];

inline int read()

{

  char ch=getchar();int num=;bool flag=false;

  while(ch<''||ch>''){if(ch=='-')flag=true;ch=getchar();}

  while(ch>=''&&ch<=''){num=num*+ch-'';ch=getchar();}

  return flag?-num:num;

}

inline void pushup(int x)

{

  int l=t[x].ch[],r=t[x].ch[];

  t[x].size=t[l].size+t[r].size+;

}

inline void pushdown(int x)

{

  if(t[x].mark){

    t[t[x].ch[]].mark^=;

    t[t[x].ch[]].mark^=;

    swap(t[x].ch[],t[x].ch[]);

    t[x].mark=;}

}

inline void rotate(int x)

{

  int y=t[x].fa;

  int z=t[y].fa;

  int k=(t[y].ch[]==x);

  t[z].ch[t[z].ch[]==y]=x;

  t[x].fa=z;

  t[t[x].ch[k^]].fa=y;

  t[y].ch[k]=t[x].ch[k^];

  t[x].ch[k^]=y;

  t[y].fa=x;

  pushup(y);pushup(x);

}

inline void splay(int x,int tag)

{

  while(t[x].fa!=tag){

    int y=t[x].fa;

    int z=t[y].fa;

    if(z!=tag)

      (t[y].ch[]==x)^(t[z].ch[]==y)?

    rotate(x):rotate(y);

    rotate(x);

  }

  if(tag==)root=x;

}

inline void insert(int x)

{

  int now=root,fa=;

  while(now)

    fa=now,now=t[now].ch[x>t[now].val];

  now=++tot;

  if(fa)t[fa].ch[x>t[fa].val]=now;

  t[now].add(x,fa);

  splay(now,);

}

inline int find(int x)

{

  int now=root;

  while(){

    pushdown(now);

    if(t[t[now].ch[]].size>=x)now=t[now].ch[];

    else if(t[t[now].ch[]].size+==x)return now;

    else x-=(t[t[now].ch[]].size+),now=t[now].ch[];

  }

}

inline void work(int l,int r)

{

  l=find(l);r=find(r+);

  splay(l,);splay(r,l);

  t[t[t[root].ch[]].ch[]].mark^=;

}

inline void print(int x)

{

  pushdown(x);

  if(t[x].ch[])print(t[x].ch[]);

  if(t[x].val>&&t[x].val<n+)

    printf("%d ",t[x].val-);

  if(t[x].ch[])print(t[x].ch[]);

}

int main()

{

  n=read();m=read();

  for(int i=;i<=n+;i++)

    insert(i);

  for(int i=;i<=m;i++){

    int l=read();int r=read();

    work(l,r);}

  print(root);

  return ;

}

Zig