简介

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

原理

普通二叉排序树很容易因为变成一条链而导致时间复杂度大大增加，而Splay则通过伸展来不断地变换树的形态，这样即使出现了链也很快会被打破当前链的状态，从而大大降低了复杂度。

所以有事没事就Splay一下，当你发现你有几个点T掉的时候，很有可能就是你Splay太少了。

均摊复杂度 O(nlog2n) 。

伸展实现

Splay的伸展用到了旋转。这个旋转和Treap一样。只是要分情况讨论如何旋转。

下面我们来讨论伸展：

1.当x的爷爷是目标节点时，此时只需根据情况左旋/右旋就好了

2.当x的爷爷不是目标节点时 ​ ①：当x,y,z不在一条直线上时 ​ ②：当x,y,z在同一条直线上时 总结一下，当x,y,z不在同一条直线上时先旋转x，在同一条直线上时先旋转y，然后再旋转x。

代码实现：

void rtt(int x,int &w){//x表示当前节点,w表示目标节点 int y=t[x].fa,z=t[y].fa,l=(t[y].to[1]==x),r=l^1; //根据x是y的左儿子还是右儿子来确定左旋或右旋 if (y==w) w=x; else t[z].to[t[z].to[1]==y]=x; //如果y有父亲(z)的话就把x接到z上 t[t[x].to[r]].fa=y,t[y].fa=x,t[x].fa=z; t[y].to[l]=t[x].to[r],t[x].to[r]=y; //把x的另一个儿子给y,y变成z的儿子 pshp(y),pshp(x);//pushup用来重新计算这个节点的其他量 } void splay(int x,int &w){ while (x!=w){ int y=t[x].fa,z=t[y].fa; if (y!=w) if (t[z].to[0]==y^t[y].to[0]==x) rtt(x,w); else rtt(y,w); rtt(x,w); } }

操作

基本操作

Splay支持一般BST的基本操作，因为其他操作大同小异，所以这里只讲讲插入/删除操作。

想看其他操作的同学戳Treap

插入：

因为Splay不需要记录键值来维护堆的性质，所以它的插入变得简单很多。根据它的权值确定位置后直接插入即可。

代码：

void nsrt(int &x,int w,int fa){ if (!x){ t[x=++nd].w=w,t[x].fa=fa; splay(x,rt); return; } nsrt(t[x].to[t[x].w<w],w,x); }

删除：把需要删除的节点Splay到根，然后将它的左子树合并到x的后继上，把右子树的父亲清零即可。

当然反过来把右子树合并到前驱也是可以的。或者和Treap一样把它Splay到叶子节点。

因为博主太菜没有做到需要删除的题目，没有代码。但是子树合并到前驱/后继上的代码还是有的： 见骗流量传送门里的tp/bttm。

区间操作

Splay当然可以维护区间啦！

建树

那么怎么把一个区间对应到Splay上呢？

首先， id[i] 表示位置i对应的节点编号。

设一个区间 [L,R] ，中间位置为mid，那么 [L,R] 就对应着以mid为根的子树。其中 [L,MID) 对应mid的左子树， (MID,R] 对应mid 的右子树。

这个对应的操作我们可以同线段树一样写一个build来实现。

void build(int l,int r,int fa){ if (l>r) return; int mid=(l+r)>>1,x=id[mid]; if (l==r){ t[x].mx=t[x].sum=a[l],t[x].t1=t[x].t2=0; t[x].l=t[x].r=max(a[l],0),t[x].sz=1; } build(l,mid-1,mid),build(mid+1,r,mid); t[x].w=a[mid],t[x].fa=id[fa]; t[id[fa]].to[mid>=fa]=x; }

查找区间

当我们需要找到 [L,R] 这个区间时，把L-1伸展到根，把R+1伸展到根的右节点，那么 [L,R] 这段区间就是R+1的左子树。

然后我们就可以进行各种区间操作了。

因为需要L-1和R+1，实际操作时我们要多建两个节点来应付 [1,n] 的操作。而0节点作为空节点，所以一般都把区间往右平移一格，虚拟节点即为1和n+2。

int srch(int x,int w){//寻找节点位置 int l=t[x].to[0]; if (t[l].sz+1==w) return x; if (t[l].sz>=w) return srch(l,w); return srch(t[x].to[1],w-t[l].sz-1); } int sprt(int l,int r){//把[l,r]分离出来 int p=srch(rt,l),q=srch(rt,r+2); //因为平移过，所以l-1变成l，r+1变成r+2 splay(p,rt);splay(q,t[p].to[1]); return t[q].to[0];//返回r+1的左子树 }

区间各种奇怪操作

有了查找区间这个操作后，我们就可以搞很多事情。下面举一些例子：

插入一整段区间：先把这个区间建成一颗平衡树，找到需要插入的位置 [x,x+1] ，直接把根接到x+1的左子树上即可。

删除一整段区间：找到要删除的区间，把R+1的左子树直接清零

区间翻转：这个操作比较典型。翻转区间就是交换mid的左右子树。然而我们不可能一次性把所有的mid都换一遍。所以我们可以把需要翻转的区间打个Tag，然后不断下传Tag即可。

当然区间操作远远不止这些，可以根据需要记录一些东西来实现。

以上操作的代码见这里的nsrt/dlt/rvrs