Splay 学习笔记

Kuriyama_Mirai · 2022-05-06 22:45:37 · 个人记录

Splay 是一种由 Tarjan 发明的，可在不维护额外信息的情况下动态平衡，且可合并的数据结构。

基本操作

将一个结点 u 向上旋转。

不是一般性地，设 u 是其父亲 f 的左儿子。则操作后 f 的父亲变为 u，u 的父亲变为 f 的原父亲，u 的右儿子变为 f，u 的右子树成为 f 的左子树。右儿子的情况是对称的。

将一个结点 u 不断旋转到根。

一种平凡的想法是不断地将其上旋。这种做法有一个显著的问题：如果原树有一条长链，那么经过操作后这条长链依然存在（有可能成为一条长路径），不够优秀。

一个简单的解决方案是这样子：将父亲一并考虑，如果父亲存在且与自己类型相同，那么先旋转父亲，否则先旋转自己。处理完这个后再旋转自己。这种做法可以将长链上的结点变得“更多分叉”，使得复杂度正确。

为了保证复杂度正确，我们需要在每次操作后都保证调用的目标结点成为了根。

暴力插入，然后 Splay。

先让 u 成为根。如果左右子树不是都非空，那么做法是平凡的；否则找到左子树的最大值并将其旋转到左子树的根（实际编写可以利用 Predecessor 函数找到 u 的值的前驱），并将右子树直接连接到左子树的根的右儿子上。

就像 BST 一样查询，最后 Splay 即可。

维护一个 multiset，支持 Insert 到 nth 的六种名次树基本操作，操作数 \le 10^5，值域为 [-10^7,10^7]。

link: https://loj.ac/p/104

code: https://loj.ac/s/1458387

翻转一个区间。

让 l-1 成为根，r+1 成为它的右儿子。r+1 的左儿子即为 [l,r] 的树。直接打翻转标记。

为了避免分类讨论，通常会添加 0 号结点与 n+1 号结点。

给定一个序列，进行 q 次 Reverse 后求最终序列。n,q\le 10^5。

link: https://loj.ac/p/105

code: https://loj.ac/s/1460866