[洛谷日报第62期]Splay简易教程
洛谷科技2018-10-02 23:31
简介
二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；左、右子树也分别为二叉排序树
同样的序列，因为排序不同，可能会生成不同的二叉排序树，查找效率性对就不一定了。如果是二叉排序树退化成一条链，效率就很低。
伸展树（Splay）是一种平衡二叉树，即优化后的二叉查找树。伸展树可以自我调整，这就要依靠伸展操作Splay(x,S)，使得提升效率。
多图预警
图片均为原创，协议为CC0，尽量保留原地址。
劼司机的图片风格太赞啦
前置技能
线段树。
变量定义
N：常量，节点个数。
ch[N][2]：二维数组，ch[x][0]代表x的左儿子，ch[x][1]代表x的右儿子。
val[N]：一维数组，val[x]代表x存储的值。
cnt[N]：一维数组，cnt[x]代表x存储的重复权值的个数。
par[N]：一维数组，par[x]代表x的父节点。
size[N]：一维数组，size[x]代表x子树下的储存的权值数（包括重复权值）。
各种操作
chk操作
辅助操作，查询一个节点位于其父节点的方向。
pushup操作
辅助操作，更新size数组的值。
旋转(rotate)
Splay使用旋转保持平衡。所以旋转是最重要的操作，也是最核心的操作。
Splay旋转后，中序遍历和Splay的合法性不变。
比如最开始的树是这样子的：
现在我们想把2号点搞到号点的位置。
那么2下面的子树就有1,3,4,5。一种比较优秀的玩法是这样的：
那么我们可以考虑这么操作：
先把4→2的边改成4→3。再把6→4的边改成6→2。最后把2→3的边改成2→4。
第一次连边
第二次连边
第三次连边
连边前(原图)
旋转操作有四种。自行模拟后发现：
旋转后，父节点会将连向需旋转的该子节点的方向的边连向该子节点位于其父节点方向的反方向的节点。
令x = 该节点, y = par[x], k = chk(x), w = ch[x][k^1]，则ch[y][k] = w; par[w] = y;
旋转后，爷爷节点会将连向父节点的边连向需旋转的该节点。
ch[z][chk(y)] = x; par[x] = z;
旋转后，需旋转的该节点会将连向该子节点位于其父节点方向的反方向的子节点的边连向其父节点。
ch[x][k^1] = y; par[y] = x;
综合一下，得到下列代码(可见自然语言是多么的无力)：
伸展(splay)
将一个节点一路rotate到指定节点的儿子。
注意，如果该节点、该父节点和该爷爷节点「三点一线」，那么应该先旋转父节点。
此处进行的操作是将3 splay到根节点。
原图
旋转父节点后
旋转自身后
剩下的情况自行模拟(没图片)了。
并且注意处理爷爷节点已经是目标的情况。
find操作
辅助操作，将最大的小于等于的数所在的节点splay到根。
插入(insert)
从根节点开始，一路搜索下去。如果节点存在则直接自增cnt的值。否则新建节点并与父节点连边。
因为新建节点时可能会拉出一条链，所以新建节点后需要将该节点splay到根节点。沿途的rotate操作可以使平衡树恢复平衡。
查询k大(kth)
从根节点开始，一路搜索下去。每次判断要走向哪个子树。注意考虑重复权值。
查询rank(rank)
并不需要专门写操作。将该节点find到根后返回左子树的权值数即可。
前驱(pre)
将该节点find到根后返回左子树最右边的节点即可。
后继(succ)
同理，返回右子树最左边的节点即可。
删除(remove)
显然，任何一个数的前驱和后继之间只有它自身。
令该点的前驱为，后继为。
那么可以考虑把前驱splay到根，后继splay到前驱的右儿子，那么后继的左儿子就是要删除的点。
最后判特判权值数大于的情况即可。
区间反转
考虑线段树维护区间标记的方法，将其移植到Splay即可。
打标记时，将和分别旋转到根节点和根节点右儿子处，那么的左子树即是区间。在其根处打上标记然后在查询大和输出中序遍历时下传标记即可。
// 这张图有点小
区间打标记
平衡树像线段树一样，可以打标记。但是有一个不同点，就是平衡树的每个节点都有权值。所以更新标记时和线段树不一样，要考虑自身节点的权值。
因为Splay可以直接提取指定区间，所以Splay的区间操作在某些意义上比线段树还好写。
例题 P2042 维护数列(https://www.luogu.org/problemnew/show/P2042)
策爷：“splay/块状链表的自虐题。”
看到插入、删除、反转就很容易想到fhq-treapSplay。
简化版问题
如果只考虑修改、求和、求最大子段和，就可以直接用线段树解决。
考虑维护la[N]、ra[N]、gss[N]、sum[N]、upd[N]，分别代表最大前缀和、最大后缀和、最大子段和、区间和和修改标记。
初始化la、ra时，在选与不选之间取max即可。gss则初始化为叶子的值即可。
la[x] = ra[x] = max(0, sum[x]); gss[x] = sum[x];
考虑如何维护la、ra、gss和sum。
再考虑如何维护upd。
upd的存储方式其实有两种：一种是把需要更新的值存储起来，另一种是修改时直接更新完毕，然后再打上bool标记。这里我采用的是后者。
下传也简单。将整个区间set成同一个值后，la、ra和gss的更新与初始化有些相似。
la和ra的代码不变，gss改成在选全部与选一个之间取max(题目要求必须选一个)。
没了？当然还有。
完整版问题
现在多了插入、删除和区间反转，维护方法相似。这里我们先考虑每个点都有权值后的变化。
其中用括号括起来的是增加的部分。
考虑同时下传反转和set两个标记。如果区间全部设置为一个值，反转也就没有意义了。所以处理顺序是set→反转。
pushdown的完整代码如下：
垃圾回收
这个毒瘤题非常恶心，卡我空间，只好写个辣鸡垃圾回收。
删除的时候，把要删除的节点全部加到一个队列里。等到要插入的时候，优先使用队列里的点。
代码很好理解。
其他用途
Splay因为其超强的区间操作能力，所以也作为LCT的辅助树使用。
Splay也可以搭配仙人掌剖分树链剖分，把一些序列上的题目出到仙人掌树上。
代码
下面附上我那常数巨大的代码，供参考用：
普通平衡树
文艺平衡树
P2042
本文发布于洛谷日报，特约作者：tiger0132
原文地址：https://tiger0132.blog.luogu.org/slay-notes
举报/反馈
0
0
收藏
分享
