Index

• Splay
• • 说在前面
  • splay树的基本思路
  • 基本的定义
  • splay函数
  • • 旋转 rotate
    • 伸展 splay
  • 插入 insert
  • 前驱&后继 pre&nxt
  • 求数的排名和排名上的数
  • 删除 deleted
  • 合并 join
  • 分离 split
  • 求最值 min&max
  • 翻转 turn
  • 其他区间操作(以SuperMemo为例)
  • • 翻译
    • 一个个来
  • 代码
  • • 普通平衡树
    • 文艺平衡树
    • SuperMemo
  • Splay的优缺点
  • 参考文章

Splay

说在前面

关于二叉平衡树是什么以及AVL树的实现
用vector实现普通平衡树！
qwq

标题好长！
真是声势浩大，徒有其表。

splay树的基本思路

出于某些原因（cache原理），在访问了某个节点之后，接下来有90%的概率很频繁地再次访问该节点，如果能把这个大概率会被多次访问的结点放到离树根尽可能近的地方，那么就可以节省不少的时间。
（大概如此）

所以要想办法把最近访问的结点扔到距离根节点尽可能近的位置。

著名计算机学家tarjan就想到了办法。

基本的定义

不写这个后文进行不下去啊。

const int MAXN=102030;
struct Splay_Tree
{
	int val,c[2],up;//c[0]代表左儿子，c[1]代表右儿子,up代表父亲
}tree[MAXN];

bool which(int pos)
{
	return tree[tree[pos].up].c[1]==pos;
}//返回pos是它父亲的哪个儿子

splay函数

splay的意思是伸展。
接下来给出的splay函数，能够在保证一直保持着BST的结构的同时，把某个节点伸展到根去。

怎么做呢？
参考AVL树，我们可以一点一点地把这个点旋转上去。

旋转 rotate

就以上图为例子，假设被旋转点在目标点的左下方。
现在，我们要把红色点转到它的父亲橙色点的上面。

嗯哼哼（试图吸引注意力），我是红点。
rotate的基本思路就是，让我右上方的父亲（因为在右边所以比我大）成为我的右儿子。

我父亲之前在我的哪上方，那就让他去我的哪下方。

然而这样就会有另外三对父子关系收到了威胁。

也就是说……

我原来的右儿子（粉色）将何去何从？
我原来的爷爷（蓝色）的儿子（橙色）怎么就没了？
我原来的兄弟（紫色）的父亲（就是我的父亲橙色）怎么就没了？

不要慌张，我们冷静分析。
现在，
需要爸爸的：粉色 紫色 红色
需要儿子的：橙色（一左一右） 蓝色
正好都是三个，看来可以平均分。

这样就没问题了。

橙色点的右儿子还是它的右儿子（紫色）。
红色点的右儿子（粉色）就接在新的右儿子（橙色）下面，当左儿子。
然后再让红色点接到原来的爷爷（蓝色）下面。

（我写了些什么？）

如果红点在橙色点的右下角那就照照镜子反过来。

也就是说，
如果我的父亲在我的右上方，也就是我是我父亲的左儿子。
那么就把我的父亲拉下来成为我的新的右儿子。
此时，我的父亲的左儿子就不是我了，我的右儿子的位置被挤占了（没了和父亲（我）的连接），我爷爷的儿子也没有了。
于是让我原来的右儿子成为我的原来的父亲（现在新的右儿子）的左儿子，然后我篡权夺位，成为我原来爷爷的新儿子。

因此rotate函数可以这么写：

void rotate(int pos)
{
	int up=tree[pos].up,upup=tree[up].up,is=which(pos);
	
	//如果我是我父亲的左儿子(is=0)的话，就让我的右儿子当我父亲的新的左儿子，我父亲成为我的右儿子
	tree[up].c[is]=tree[pos].c[!is],tree[tree[pos].c[!is]].up=up;
	tree[pos].c[!is]=up,tree[up].up=pos;//爸爸认儿子的同时要记得儿子认爸爸啊
	
	//我的新爸爸就是我原来的爷爷，我原来的爷爷的新的儿子就是我
	tree[pos].up=upup;
	if(upup) tree[upup].c[tree[upup].c[1]==up]=pos;
	//当然如果爷爷是虚空（原来的爸爸就是根节点）的话，就不能爸爸认儿子了
	//还有还有，因为父子关系发生了说不清道不明的改变，所以这里不好用which，要用which一开始定义的时候的用
}

伸展 splay

我们发现通过rotate我们能在不改变树的平衡性的同时让某个点上升一层，但是这离我们的目标（旋转到根节点）还差得远。

所以就有了splay操作：让某个结点通过一次又一次rotate转到根节点。比方说：

逆流而上的你眼前或许有无数曲折崎岖道路，也许离终点遥遥无期，但是，
结 点             到 达 根 源                       叶 子 结 点 \small 结点~~~~~~~~~~~到达根源~~~~~~~~~~~~~~~~~~~~~叶子结点 结点           到达根源                     叶子结点
  人 一 定 要 有 梦 想 ， 没 有 梦 想 和 咸 鱼 有 什 么 区 别 ？ ！ ~人一定要有梦想，没有梦想和咸鱼有什么区别？！  人一定要有梦想，没有梦想和咸鱼有什么区别？！

（这就是你四暗刻一向听的时候碰碰杠杠做对对还一张dora没有翻出来的原因？）

所以谁能告诉我这个“逆流而上的你”是什么啊还消不掉！（见下图）

咳咳，话说回来，逆流而上的你眼前或许有无数曲折崎岖道路，也许离终点遥遥无期，但是，绝无无法行走的路 （定义如此，走不了就不叫路了） ，只要你想要到达，就没有无法克服的障碍，只要你想办法的话。
在你一步一步往上rotate的时候，你的道路大概可以分为以下三类，六种：

还有一类没有画上去，就是爸爸就是根节点，没有爷爷的情况，这个直接一个rotate就解决了。

折线形没有什么好说的，一步一步rotate上去吧。
关于直线型：就是我是爸爸的a儿子，我爸爸是我爷爷的a儿子的情况。
科学家们告诉我们，这个时候应该先rotate(爸爸)，再rotate(我)。
如果仍然是一直埋头苦干rotate(我)，这样的自平衡方法叫做Spaly；而先rotate(父亲)，再rotate(我)的自平衡方法叫做splay。
如下图：

乍一看差不多，甚至某道题目(BZOJ1036树的统计Count)我把splay换成了spaly会快一些(5600ms->5000ms)，但是咨询了Freopen/Kyle/wk大佬后，Freopen/Kyle/wk告诉我，“可以证明splay更优，而且出数据的时候可以卡spaly。”
（所以说科学家等于wk?）

哇。

总结一下：

情况	应对方法
我爸爸是根，我没有爷爷	rotate(我)
我，我爸爸，我爷爷呈一条直线	rotate(父),rotate(我)
我，我爸爸，我爷爷呈一条折线	rotate(我),rotate(我)

所以就可以得到splay函数：

void splay(int pos)
{
	while(tree[pos].up)
	{
		if(tree[tree[pos].up].up && which(tree[pos].up)==which(pos)) rotate(tree[pos].up);
		rotate(pos);
	}
	root=pos;//一个全局变量root来记录splay树的根
}

当然，用splay操作可以使一个节点上升到它上面的任意一个结点

插入 insert

和正常的二叉平衡树一样，先找到对应的位置，直接插入，没问题的。
然后再spaly到根节点上去。

void insert(int pos,int val,int up) //调用的时候就用insert(root,某个值,0)
{
	if(!pos)
	{
		tree[++n].val=val,tree[n].up=up;
		tree[up].c[tree[n].val>tree[up].val]=n;//认别人做爸爸的同时，别人也要认你做儿子
		splay(pos);
		//此时不同的题有不同的操作
		return ;
	}
	insert(tree[pos].c[val>tree[pos].val],val,pos);
	//这里默认每个点的值都不同，如果相同的话就在不同的题里面有不同的处理方式
}

前驱&后继 pre&nxt

也有叫upper和lower的，还有等等名字。
和一般的二叉平衡树没有什么区别。

//默认了各个数不相同，不过知道了原理之后想怎么样都无所谓吧
int pre(int val) 
{
	int pos=root,ans=-2147483647;
	while(pos)
	{
		if(tree[pos].val<val) ans=max(ans,tree[pos].val);
		pos=tree[pos].c[val>tree[pos].val];
	}
	return ans;
}
//所谓前驱就是小于某个值的最大值，也可以说是这个点的左子树里面最靠右的那个端点。
	
int nxt(int val)
{
	int pos=root,ans=2147483647;
	while(pos)
	{
		if(tree[pos].val>val) ans=min(ans,tree[pos].val);
		pos=tree[pos].c[val>tree[pos].val];
	}
	return ans;
}
//基本上是复制之前写AVL的时候写的那个

求数的排名和排名上的数

我称之为： g e t r a n k ( ) getrank() getrank()和 r a n k g e t ( ) rankget() rankget()。

如果采用惰性方法的话就很方便。
现在我们给每个节点新增两个变量，cnt和siz。
cnt代表这个点上重复有多少个数。比方说val=1的点的cnt=4，就代表插入了4个1，都被塞到同一个点里。
siz代表子树里数的个数（也就是说，不是子树点的个数，而是子树里各个点的cnt的值的和）
这样子的话，插入和删除会有些许变化。记得在树的结构或者点的cnt改变的时候pushup一下来维护siz。（也就是insert和delete和splay的时候→也就是splay的时候）到时候给出普通平衡树模板的时候一并看吧。

然后rankget，就是和找前驱差不多了，用找前驱的方法加上siz这个变量就可以轻松把前驱是谁转换成求前驱有几个的问题了。就是找到前驱然后把前驱的siz+1就是答案了。

然后是getrank，感觉像find和getrank的结合体，有了siz和cnt，我们就知道每个pos的val所对应的排名的区间是多少了。就是 [ t r e e [ t r e e [ p o s ] . c [ 0 ] ] . s i z + 1 , t r e e [ t r e e [ p o s ] . c [ 0 ] ] . s i z + t r e e [ p o s ] . c n t ] \bold{\left[tree[tree[pos].c[0]].siz+1,tree[tree[pos].c[0]].siz+tree[pos]t\right]} [tree[tree[pos].c[0]].siz+1,tree[tree[pos].c[0]].siz+tree[pos].cnt]，如果在这个范围里，那么就找到了，如果给定的排名在这个排名区间的左边，那就说明我们要找的数比当前的数要小，那么就向左二分下去，如果在右边就向右边。
需要稍微注意一下的是，向右边搜的时候，给定的排名要减去 ( t r e e [ t r e e [ p o s ] . c [ 0 ] ] . s i z + t r e e [ p o s ] . c n t ) (tree[tree[pos].c[0]].siz+tree[pos]t) (tree[tree[pos].c[0]].siz+tree[pos].cnt)，因为当前节点的siz是它的左儿子+右儿子+自己，比方说左儿子和右儿子是[1,2,3,4,5,6,7]和[8,9,10]找第八名，当然应该在右儿子里面找了，但是右儿子只有3个数没有第8名,所以把8-7（左儿子的siz）得到1，我们应该在右儿子里面查询第1大的数。

void pushup(int pos)
{
	tree[pos].siz=tree[tree[pos].c[0]].siz+tree[tree[pos].c[1]]+tree[pos]t;
}
//目前的pushup只有siz一个，因为查找前驱后继不会改变数的形态更不会改变siz所以不pushup

//调用的时候调用getrank(val,root)，对了，还有可能找不到，所以记得特判
int getrank(int val,int pos)
{
	if(pos==0) return 2147483647;
	if(val==tree[pos].val) return tree[tree[pos].c[0]].siz+1;
	else  
	{
		if(val<tree[pos].val) return getrank(val,tree[pos].c[0]);
		else return getrank(val,tree[pos].c[1])+tree[tree[pos].c[0]].siz+tree[pos]t;
	}
}

int rankget(int rak,int pos)
{
	if(pos==0) return -2147483647;
	if(rak>=tree[tree[pos].c[0]].siz+1 && rak<=tree[tree[pos].c[0]].siz+tree[pos]t) return tree[pos].val;
	else
	{
		if(rak<tree[tree[pos].c[0]].siz+1)  return rankget(rak,tree[pos].c[0]);
		return rankget(rak-tree[tree[pos].c[0]].siz-tree[pos]t,tree[pos].c[1]);
	}
}

删除 deleted

因为delete这个函数名已经有了，所以加了一个d。

采用惰性删除。

现在要分好几种情况来讨论。

首先，如果cnt-1之后还有剩余，就平安无事什么也不用干，cnt–就是了。

如果cnt==1，也就是删除了这个点就没有了：
（说实话空留一个cnt=0的点在那里浪费时间空间好像没什么问题啊）
先把这个要删除的东西splay到根节点处。

如果要删除的点（目前已经splay到根了），没有儿子： 这棵树的最后的一个数被你删了，这棵树完了。
如果只有一个儿子：那么就直接把这个根节点移除掉，并把根节点的位置传给那个儿子。

如果有两个儿子的话：
把前驱找到并splay上来，然后把被删除点的右儿子接到前驱的右边，自己消失掉。

void deleted(int val)
{
	getrank(val);//随便整一下把目标点splay上来
	if(--tree[root]t) return;//如果删掉一个还有剩余，就无事发生
	if(!tree[root].c[0] && !tree[root].con[1]) root=0;//如果连根无子无孙，那这棵树就没了
	else if(!tree[root].c[1]) root=tree[root].c[0],tree[root].up=0,pushUp(root);
	else if(!tree[root].c[0]) root=tree[root].c[1],tree[root].up=0,pushUp(root);
	//如果只有一个儿子，那就让那个儿子接替自己的位置
	else 
	{
		int pre=tree[root].c[0],pos=root;
		while(tree[pre].c[1]) pre=tree[pre].c[1];
		//找前驱
		splay(pre),tree[tree[pos].c[1]].up=root,tree[root].c[1]=tree[pos].c[1],pushup(root);
		//把前驱再转上来，现在目标点（pos）就是根节点的右儿子
	}
}

现在普通平衡树的各个功能就写好了。
然后是，

合并 join

有一颗Splay树（记为S1）的所有节点都比另一颗Splay树（记为S2）的最小的节点小的时候，

于是让S1最大的节点Splay到S1的根，然后把S2接到S1的右下方。

好鸡肋的功能。
图来自杨思雨的论文。

分离 split

给定数x，把一颗splay树分成两棵树，其中一棵树的值都小于x，另一颗都大于x。
首先把x这个点splay到根，然后它的左子树和右子树即为所求。

求最值 min&max

这个就一直往左or右走就是了。

翻转 turn

现在来考虑做文艺平衡树。
文艺平衡树要我们支持对一个数列进行区间翻转再输出。

首先，为了把用一棵树来存一个数列，所以和普通的SBT不同（普通的SBT的中序遍历是一个不下降序列）的，现在我们维护的splay树的中序遍历是这个区间本身。也就是从按权值不下降排序到下标不下降排序。

举个例子就是一个数组{1,3,4,5,6,7,2,4,5,2}，在一个普通的Splay树中，它的中序遍历是{1,2,2,3,4,4,5,5,6,7}，在支持区间翻转的Splay树中，中序遍历是**{1,3,4,5,6,7,2,4,5,2}**。

然后怎么区间翻转呢？

先建一颗树，按照题目所要求的，就假设N=12，那么数列就是{1,2,3,4,5,6,7,8,9,10,11,12}，建成splay树以后可以长这个样子：

上图的确是跑splay的时候跑出来的。

现在我们可以看到，中序遍历就是{1,2,3,4,5,6,7,8,9,10,11,12}，假设现在我们要翻转区间[l,r]，比方说[4,6]，就是图中绿点的区间：

我们先想办法把这个区间给独立出来。
那么我们先把r+1这个点Splay到根节点，也就是Splay(7)。

转上来了。

然后再把l-1转到r+1的左儿子，也就是Splay(3,tree[root].c[0])。
毕竟上文说了，可以把一个点splay到它上方任意一个节点，而它肯定在根节点的左侧，那么根节点的左儿子一定在它的上方。

现在我们就把要操作的区间独立出来了，就是根的左儿子的右子树。（是一颗树）
那么现在就可以做很多事情了。

比方说翻转，对于这个独立出来的子树，要翻转相当于交换每个节点的左右儿子，但是来如果要交换的话，那么就会很麻烦，况且一个区间被多次翻转之后，很有可能翻转回来，就浪费很多时间空间。

所以打懒标记吧。
标记一下这个点是否要翻转左右儿子，输出的时候如果有标记就翻转地输出。
然后每次翻转区间的时候不需要对整个区间打标记，只需要在最上面的那个点那里打标记就行了。
如果要访问这个区间里没有打过标记的点，那么必然会访问刚才打过标记的那个“最上面那个点”，那么在访问那个点的时候就把标记下传给儿子们，接下来访问某个儿子，访问这个儿子的时候再下传给它的儿子……直到我们访问到要找的那个点，此时它已经得到懒标记了，而整个过程几乎没有浪费时间在给暂时无关的结点打标记上。

代码就丢在文艺平衡树里面吧。

对了对了，因为要访问 l − 1 \bold {l-1} l−1和 r + 1 \bold {r+1} r+1这两个结点，所以为了不在翻转区间 [ 1 , x ] \bold {[1,x]} [1,x]或 [ x , n ] \bold {[x,n]} [x,n]的时候爆掉，要在1号点之前加一个-inf，在n号点之后加一个inf，既然这样那么哪个点对应哪个值就一定要想清楚了。

其他区间操作(以SuperMemo为例)

Your friend, Jackson is invited to a TV show called SuperMemo in which the participant is told to play a memorizing game. At first, the host tells the participant a sequence of numbers, A 1 , A 2 , . . . A n {A1, A2, ... An} A1,A2,...An. Then the host performs a series of operations and queries on the sequence which consists:

A D D   x   y   D ADD ~x~ y ~D ADD x y D: Add D to each number in sub-sequence A x . . . A y {Ax ... Ay} Ax...Ay For example, performing “ A D D   2   4   1 ADD ~2 ~4 ~1 ADD 2 4 1” on 1 , 2 , 3 , 4 , 5 {1, 2, 3, 4, 5} 1,2,3,4,5results in 1 , 3 , 4 , 5 , 5 {1, 3, 4, 5, 5} 1,3,4,5,5
R E V E R S E   x   y REVERSE ~x ~y REVERSE x y: reverse the sub-sequence A x . . . A y {Ax ... Ay} Ax...Ay. For example, performing “ R E V E R S E   2   4 REVERSE ~2 ~4 REVERSE 2 4” on 1 , 2 , 3 , 4 , 5 {1, 2, 3, 4, 5} 1,2,3,4,5 results in 1 , 4 , 3 , 2 , 5 {1, 4, 3, 2, 5} 1,4,3,2,5
R E V O L V E   x   y   T REVOLVE ~x ~y ~T REVOLVE x y T: rotate sub-sequence A x . . . A y {Ax ... Ay} Ax...Ay T times. For example, performing “ R E V O L V E   2   4   2 REVOLVE ~2~ 4 ~2 REVOLVE 2 4 2” on 1 , 2 , 3 , 4 , 5 {1, 2, 3, 4, 5} 1,2,3,4,5 results in 1 , 3 , 4 , 2 , 5 {1, 3, 4, 2, 5} 1,3,4,2,5
I N S E R T   x   P INSERT~ x ~P INSERT x P: insert P after Ax. For example, performing “ I N S E R T   2   4 INSERT~ 2~ 4 INSERT 2 4” on 1 , 2 , 3 , 4 , 5 {1, 2, 3, 4, 5} 1,2,3,4,5 results in 1 , 2 , 4 , 3 , 4 , 5 {1, 2, 4, 3, 4, 5} 1,2,4,3,4,5
D E L E T E   x DELETE ~x DELETE x: delete Ax. For example, performing “ D E L E T E   2 DELETE ~2 DELETE 2” on 1 , 2 , 3 , 4 , 5 {1, 2, 3, 4, 5} 1,2,3,4,5 results in 1 , 3 , 4 , 5 {1, 3, 4, 5} 1,3,4,5
M I N   x   y MIN ~x~ y MIN x y: query the participant what is the minimum number in sub-sequence A x . . . A y {Ax ... Ay} Ax...Ay. For example, the correct answer to “ M I N 2   4 MIN 2 ~4 MIN2 4” on 1 , 2 , 3 , 4 , 5 {1, 2, 3, 4, 5} 1,2,3,4,5 is 2 2 2
To make the show more interesting, the participant is granted a chance to turn to someone else that means when Jackson feels difficult in answering a query he may call you for help. You task is to watch the TV show and write a program giving the correct answer to each query in order to assist Jackson whenever he calls.

翻译

写一个数据结构支持六种操作：
① A D D   x   y   D ADD~ x ~y~ D ADD x y D，对于区间 [ x , y ] [x,y] [x,y]每个数都加上 D D D。
② R E V E R S E   x   y REVERSE ~x~ y REVERSE x y，翻转区间 [ x , y ] [x,y] [x,y]。
③ R E V O L V E   x   y   T REVOLVE ~x ~y ~T REVOLVE x y T，这个厉害了，把区间 [ x , y ] [x,y] [x,y]里的每个数在这个区间里面循环右移 T T T次，举个例子就是： 1 , 2 , 3 , 4 , 5 → 5 , 1 , 2 , 3 , 4 → 4 , 5 , 1 , 2 , 3 → 3 , 4 , 5 , 1 , 2 {1,2,3,4,5}\to {5,1,2,3,4} \to {4,5,1,2,3} \to {3,4,5,1,2} 1,2,3,4,5→5,1,2,3,4→4,5,1,2,3→3,4,5,1,2
④ I N S E R T   x   P INSERT~ x ~P INSERT x P，在 x x x点的后面插入一个值为 P P P的点。
⑤ D E L E T E   x DELETE ~x DELETE x，删掉点 x x x。
⑥ M I N   x   y MIN ~x~ y MIN x y，求区间 [ x , y ] [x,y] [x,y]的最小值。

一个个来

对于ADD操作，先把这个区间独立出来，然后打一个加法懒标记。
对于REVERSE操作，上面有。
对于REVOLVE操作，声势浩大，徒有其表，首先先把T%=(y-x+1);，那么就是把这个区间的后T个数移到前面y-x+1-T个数的前面；那么就是把前y-x+1-T个数REVERSE，把后T个数REVERSE，然后再把整个区间REVERSE就行了。

（这个字体的6写得像4）
对于INSERT操作，因为它要求在某个点后面插入值，所以先把这个值 x x x当成一个区间 [ x , x ] [x,x] [x,x]（数学考试这么写是会被扣分的）把它独立出来，也就是先把 x + 1 x+1 x+1 S p l a y Splay Splay到根节点，再把 x − 1 x-1 x−1 S p l a y Splay Splay到根节点的儿子，那么 x x x就在 x − 1 x-1 x−1的右儿子，然后再把 P P P接上去就是了。
对于DELETE操作，和INSERT一样，把 x x x独立出来以后直接取下来就是了。
对于MIN操作，因为我们的树不是按照数值大小关系来排序的，所以要额外开一个值来记录子树里的最小值，和siz一起push_up。

代码

普通平衡树

咕咕咕

文艺平衡树

咕咕咕

SuperMemo

咕咕咕

Splay的优缺点

相较于AVL和Treap，Splay可以少存一个平衡因子。

Splay还有一个很重要的特性，那就是不稳定性，可能飚的很快，也可能被神秘卡掉。
所以“在严谨场合”不建议使用。

代码实现比AVL要简单一些。

参考文章

以下每一篇都比我的这个好：
伸展树的基本操作与应用 IOI2004国家集训队 杨思雨
https://blog.csdn/a_comme_amour/article/details/79382104
https://wwwblogs/cjyyb/p/7499020.html &https://blog.csdn/qq_30974369/article/details/77587168（并不详细地讲了spaly为什么会被卡）
https://blog.csdn/chenxiaoran666/article/details/81414567
http://wwwblogs/dalt/p/8167168.html（时间复杂度分析）
https://blog.csdn/CABI_ZGX/article/details/82819882 （SuperMemo）
https://blog.csdn/DERITt/article/details/50485008 （更多的区间操作）