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

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

## 本节目标

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

## 前置知识与课前自测

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

1. Splay 是否靠随机数保持平衡？
2. 为什么连续同向的祖孙关系要先旋父亲（zig-zig）？
3. 加左右哨兵后，原序列第 l 项前驱的全树排名是多少？

<details><summary>答案</summary>

1. 不靠；单次可能线性，但访问序列摊还 $O(\log n)$。
2. 它能按势能分析压缩整条同向重链；只反复旋当前点不能得到标准摊还界。
3. l；左哨兵占排名 1，原第 l 项排名 l+1。

</details>

## 问题动机与核心知识

Splay 不维护颜色/随机优先级。每次访问后把目标伸到根或指定父亲：

- 父亲就是目标父亲：zig；
- 当前点与父亲同向：先旋父亲再旋当前点；
- 方向相反：连续旋当前点两次。

它保持 BST 中序不变，并把近期访问点移近根。Sleator–Tarjan 势能分析给出摊还对数，但不能声称每次最坏对数。

![zig、zig-zig、zig-zag 的旋转顺序](../插图/11-平衡树/03-Splay-01-三种旋转.svg)

隐式序列中加入左右哨兵。要暴露原区间 $[l,r]$：把前驱（全树第 l）伸到根，再把后继（全树第 r+2）伸成前驱右儿子；后继的左子树恰是目标区间。

![双哨兵如何把目标区间暴露为一棵子树](../插图/11-平衡树/03-Splay-02-双哨兵暴露.svg)

## 实现指南

- 旋转前把从目标祖先到目标的 Lazy 全部 push，避免按逻辑排名旋错。
- 每次改儿子和父亲后按自底向上 pull。
- 删除根时断开左右树，再把左树最大点伸到根并接右树。
- 哨兵参与 size 但不参与区间 sum，值设 0。

## 精选例题 1：Order statistic set

### 来源与题意

- [SPOJ-ORDERSET Order statistic set](https://vjudge.net/problem/SPOJ-ORDERSET)
- 维护无重复整数集合：插入、删除、第 k 小、统计严格小于 x 的个数。

<details><summary>Hint 1</summary>按键建 Splay，维护 size。</details>
<details><summary>Hint 2</summary>每次查找最后访问点也伸到根，维持自调整性质。</details>

### Observations、Editorial 与证明

BST 中序即升序。`countLess(x)` 走树：若当前键小于 x，则左子树和当前点全部计入并转右，否则转左。`kth` 用左 size 决策。插删保持 BST 顺序，旋转只改变形状不改变中序，因此四种操作语义正确；Splay 定理给出操作序列摊还 $O(\log n)$。

### 核心伪代码与附件

```text
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 附件](../../参考实现/11-平衡树/SPOJ-ORDERSET.cpp)

## 精选例题 2：Reversals and Sums

### 来源与题意

- [CSES-2074 Reversals and Sums](https://vjudge.net/problem/CSES-2074)
- 动态序列支持区间翻转与区间和。

<details><summary>Hint 1</summary>用双哨兵把区间暴露为后继的左子树。</details>
<details><summary>Hint 2</summary>翻转对子树打 rev；求和直接读该子树 sum。</details>

### Observations

- 两次 Splay 后区间成为完整子树，操作不再需要递归分裂/合并。
- 哨兵消除了 l=1、r=n 的空前驱/后继特判。
- 区间翻转保持和不变，只交换儿子并延迟下传。

### Editorial 与正确性证明

选择区间前驱 x 与后继 y。中序中所有目标元素严格位于 x,y 之间；把 x 伸根、y 伸到 x 下后，若 y 左子树缺或多元素就会违反 BST 中序连续性，因此它恰是目标区间。读取 sum 或应用 rev 后，pull y、x 恢复摘要。每操作摊还 $O(\log n)$。

### 核心伪代码与附件

```text
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 附件](../../参考实现/11-平衡树/CSES-2074.cpp)

## 扩展与联系

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

## 总结与自检

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

## 课后训练建议

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