Splay 总结

\(Splay\) 是一种二叉搜索树，在我的理解中它是通过特殊的旋转方式使得其单次操作均摊复杂度为 \(log\) 级别的一种数据结构。

除此之外，另外一些性质是二叉搜索树本身就具有的。

在一棵 \(Splay\) 中，每个结点维护着整个子树以及它本身的信息，树中每个结点与它的左右儿子之间的附加权值满足二叉搜索树的关系。

且它的中序遍历结果的结点附加权值是递增的，也就是说如果附加权值是下标，那么一个子树对应着一段连续的区间，这样就可以支持区间修改包括翻转操作了。

复杂度方面就不详细说了，大概就是每次感觉最坏要 \(O(n)\) 时，就把走到的结点旋转到根节点，这样就问题不大了 \(233\)。

接下来简单介绍一下基本操作。

0. \(pushup,pushdown\) : 更新当前结点的信息/下传懒标记。

1. \(rotate\) : 在满足二叉搜索树性质的同时，交换一对父子的关系。

void rotate_(int x) {
	int y = par[x], z = par[y], k = chk_(x), w = ch[x][k^1];
	if (z) ch[z][chk_(y)] = x;
	par[x] = z, par[w] = y, ch[y][k] = w;
	par[y] = x, ch[x][k^1] = y;
	pushup_(y), pushup_(x);
}

2. \(splay\) : 将指定结点旋转到指定结点的儿子处，若结点为 \(0\)，就旋转到根。

void splay_(int x, int ed = 0) {
	for (int p = par[x]; p != ed; rotate_(x), p = par[x])	
		if (par[p] != ed) rotate_(chk_(p) == chk_(x) ? p : x);
	if (!ed) root = x;
}

这些便是基本的操作了，找第 \(k\) 大的结点按照二叉搜索树的方法找就是了。

接下来讲点关键的东西。

1. 每次要提取某个结点的信息时，需要将根节点到它路径上结点的懒标记依次下传以保证信息的及时性。

2. 更新了结点信息以后，如果是子树修改的话要打上懒标记，并且从下往上更新祖先维护的信息，或者下传当前结点标记然后把当前结点转到根。

3. 区间反转操作相当于将子树内部所有点的左右儿子翻转即可。

4. 关于懒标记，可以认为是延缓更新子树内部信息的一种手段，它的对象是固定的，每次要改变树的形态时，要先把影响的结点的标记依次下传。

5. 如何提取区间 \(l...r\) 呢？可以先把 \(l - 1\) 转到根，再把 \(r + 1\) 转到 \(l - 1\) 的儿子处，由于二叉搜索树的性质，此时 \(r + 1\) 的左儿子的整个子树即为 \(l...r\)。从上面的操作可以看出需要哨兵结点来保证 \(l - 1,r + 1\) 的存在。

6. 建树的方法可以参照线段树的方式，每次选取中间结点作为父亲，将左半段作为其左儿子，右半段作为其右儿子，递归建树即可。

线段树能干的 \(Splay\) 大概都能干，是不是很厉害？

Splay 总结

原文：https://www.cnblogs.com/ympc2005/p/14204047.html