lessons/课程/11-平衡树/03-Splay伸展与区间暴露.md

Splay：伸展、势能与双哨兵区间暴露

建议先完成 让刚访问的点靠近你，再用 把一段话翻过来 预演双哨兵和 Lazy。前者从旋转的中序证据出发，后者把区间真的夹成一棵子树。

本节目标

理解 Splay 通过 zig/zig-zig/zig-zag 把访问点伸到目标父亲，掌握按值有序集与按排名序列两种模式，并用双哨兵把任意区间暴露为一棵子树。

前置知识与课前自测

前置：BST 旋转、子树大小、Lazy 翻转。

1. Splay 是否靠随机数保持平衡？
2. 为什么连续同向的祖孙关系要先旋父亲（zig-zig）？
3. 加左右哨兵后，原序列第 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)

完整 C++17 附件

精选例题 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

完整 C++17 附件

扩展与联系

HDU-3487 Play with Chain 和 POJ-3580 SuperMemo 可继续训练剪贴、循环移位、区间加与最小值。FHQ 更易写分裂合并，Splay 更擅长围绕访问位置暴露区间；应按操作接口选择。

总结与自检

1. 三种伸展情形分别怎样旋？
2. Splay 保证的是单次还是摊还复杂度？
3. 双哨兵区间的前驱/后继排名为何是 l 与 r+2？
4. 为什么旋转前要沿祖先链 push？

课后训练建议

先只实现有序集并与 std::set 对拍，再加隐式序列。调试区间暴露时打印中序排名、x、y 和目标子树长度，优先排查哨兵偏移。