splay

zuytong · 2020-07-28 08:53:00 · 个人记录

link to cnblog

LCT 的前置知识：

splay 是一种二叉搜索树，满足中序遍历是原序列，支持区间插入、删除、查询等操作

基本操作：旋转

进阶操作：双旋

顺链：先父亲再自己

折链：先自己再父亲

可证明双旋复杂度是均摊 O(\log n) 的

初始化：先建一个 -INF 和一个 INF 结点

查找 num 的前驱/后继：不断向下找，记录沿途最优解；当访问到空节点时，将上一个（最后一个）访问点翻到根的位置，并返回答案

插入/删除 num：将 num 的前驱 y 翻转到根的位置，将 num 的后继 x 翻转到 y 的右儿子处；最后对 y 的左儿子 进行操作

查找 rank / 得到 num 的 rank：和普通的二叉树做法相同；注意 -INF 结点的存在，rank 要相应加减

数组实现

指针实现（不推荐）

文艺平衡树

要支持区间翻转

当要翻转 [l,r] 时，我们将 l-1 翻转到根的位置，r+1 翻转到 l-1 的右儿子处；这时 r+1 的左子树就代表 [l,r]

我们给 r+1 的左儿子打上一个 tag

在查找 l-1,~r+1 以及最后遍历时将 tag 下传即可