个人复习用品

不喜勿喷，右(左)上有叉号，点好

从前有一种树叫做伸展树

每次操作复杂度均摊O(logN)，证明略

有几种旋转操作都可以使其保持平衡。第一种是ZigZag，第二种是Rotate。

这里介绍一下Rotate

void Rotate(int x, int w)
{
	Pushdown(p[p[x]]); Pushdown(p[x]);
	int i = p[x], y = kind[i], cc = p[i]; 
	p[x] = cc; if((kind[x] = y) != 3) son[cc][y] = x;
	p[son[i][w] = cc = son[x][y = 3 - w]] = i; kind[cc] = w;
	son[p[i] = x][kind[i] = y] = i;
	Update(i);
}

void Splay(int x, int y)
{
	Pushdown(x);
	while(p[x] != y)
	{
		int a = kind[x], i = p[x], b = kind[i];
		if(p[i] == y) { Rotate(x, a); break; }
		if(a == b) Rotate(i, a); else Rotate(x, a); Rotate(x, b);
	}
	Update(x); if(y == 0) Root = x;
}

Rotate(x, w)的意义是将x左(w = 2时)或右(w = 1时)旋

每次旋转时影响三代的结点，先下传x的爷爷的标记，再下传x的父亲的标记

用i记录x的父亲，y记录i的属性，cc记录x的爷爷

x的父亲更改为cc，x的属性更改为i的属性

如果cc不是虚拟根，那么把cc的儿子记录为x

如果是左旋，i显然会变成x的右儿子，x的右儿子会被i当做左儿子接受

如果是右旋，i显然会变成x的左儿子，x的左儿子会被i当做右儿子接受

所以在x的左(右)旋意义下，此时y赋值为右(左)旋属性(3-w)，i的左(右)儿子赋值为用cc记录的x的右(左)儿子，cc属性记录为左(右)旋属性(w)。最后处理i，i的父亲变更为x，i的属性变更为y，x的儿子赋值为i，更新一下i的键值。

Splay(x, y)的意义是将x旋转到y下。

Splay(x, y)前，需要将x的标记下传，然后每次用a记录x的属性(1为左儿子,2为右儿子)，i记录x的父亲，b记录i的属性

如果x的爷爷就是y了，那么只需要将x进行Rotate(x, a)就可以把x旋转到y下了

如果x,i都在一条直线上，那么只需要先将i旋转，x再进行相同的旋转就行了

如果不是的话，需要将x进行相应的旋转，此时x代替了i的位置，x也继承了i的属性，只需要再将x进行相应的i属性的旋转就行了