03-Splay伸展与区间暴露.md 5.2 KB
Splay：伸展、势能与双哨兵区间暴露
建议先完成 让刚访问的点靠近你，再用 把一段话翻过来 预演双哨兵和 Lazy。前者从旋转的中序证据出发，后者把区间真的夹成一棵子树。
本节目标
理解 Splay 通过 zig/zig-zig/zig-zag 把访问点伸到目标父亲，掌握按值有序集与按排名序列两种模式，并用双哨兵把任意区间暴露为一棵子树。
前置知识与课前自测
前置：BST 旋转、子树大小、Lazy 翻转。
- Splay 是否靠随机数保持平衡？
- 为什么连续同向的祖孙关系要先旋父亲（zig-zig）？
- 加左右哨兵后，原序列第 l 项前驱的全树排名是多少？
答案
1. 不靠；单次可能线性，但访问序列摊还 $O(\log n)$。 2. 它能按势能分析压缩整条同向重链；只反复旋当前点不能得到标准摊还界。 3. l；左哨兵占排名 1，原第 l 项排名 l+1。问题动机与核心知识
Splay 不维护颜色/随机优先级。每次访问后把目标伸到根或指定父亲：
- 父亲就是目标父亲：zig；
- 当前点与父亲同向：先旋父亲再旋当前点；
- 方向相反：连续旋当前点两次。
它保持 BST 中序不变，并把近期访问点移近根。Sleator–Tarjan 势能分析给出摊还对数，但不能声称每次最坏对数。
隐式序列中加入左右哨兵。要暴露原区间 $[l,r]$：把前驱（全树第 l）伸到根，再把后继（全树第 r+2）伸成前驱右儿子；后继的左子树恰是目标区间。
实现指南
- 旋转前把从目标祖先到目标的 Lazy 全部 push，避免按逻辑排名旋错。
- 每次改儿子和父亲后按自底向上 pull。
- 删除根时断开左右树，再把左树最大点伸到根并接右树。
- 哨兵参与 size 但不参与区间 sum，值设 0。
精选例题 1：Order statistic set
来源与题意
- SPOJ-ORDERSET Order statistic set
- 维护无重复整数集合：插入、删除、第 k 小、统计严格小于 x 的个数。
Hint 1
按键建 Splay，维护 size。Hint 2
每次查找最后访问点也伸到根，维持自调整性质。Observations、Editorial 与证明
BST 中序即升序。countLess(x) 走树：若当前键小于 x，则左子树和当前点全部计入并转右，否则转左。kth 用左 size 决策。插删保持 BST 顺序，旋转只改变形状不改变中序，因此四种操作语义正确；Splay 定理给出操作序列摊还 $O(\log n)$。
核心伪代码与附件
splay(x, goal):
push all ancestors
while parent(x) != goal:
if parent(parent(x)) == goal: rotate(x)
else if x and parent(x) have same direction: rotate(parent(x)); rotate(x)
else: rotate(x); rotate(x)
精选例题 2：Reversals and Sums
来源与题意
- CSES-2074 Reversals and Sums
- 动态序列支持区间翻转与区间和。
Hint 1
用双哨兵把区间暴露为后继的左子树。Hint 2
翻转对子树打 rev；求和直接读该子树 sum。Observations
- 两次 Splay 后区间成为完整子树，操作不再需要递归分裂/合并。
- 哨兵消除了 l=1、r=n 的空前驱/后继特判。
- 区间翻转保持和不变，只交换儿子并延迟下传。
Editorial 与正确性证明
选择区间前驱 x 与后继 y。中序中所有目标元素严格位于 x,y 之间；把 x 伸根、y 伸到 x 下后，若 y 左子树缺或多元素就会违反 BST 中序连续性，因此它恰是目标区间。读取 sum 或应用 rev 后，pull y、x 恢复摘要。每操作摊还 $O(\log n)$。
核心伪代码与附件
x = kth(l) # left sentinel included
splay(x, root)
y = kth(r + 2)
splay(y, parent=x)
segment = left_child(y)
reverse: apply_rev(segment)
sum: segment.sum
扩展与联系
HDU-3487 Play with Chain 和 POJ-3580 SuperMemo 可继续训练剪贴、循环移位、区间加与最小值。FHQ 更易写分裂合并，Splay 更擅长围绕访问位置暴露区间；应按操作接口选择。
总结与自检
- 三种伸展情形分别怎样旋？
- Splay 保证的是单次还是摊还复杂度？
- 双哨兵区间的前驱/后继排名为何是 l 与 r+2？
- 为什么旋转前要沿祖先链 push？
课后训练建议
先只实现有序集并与 std::set 对拍，再加隐式序列。调试区间暴露时打印中序排名、x、y 和目标子树长度，优先排查哨兵偏移。