# 课前零食：把一段话翻过来

> “文艺平衡树”是竞赛圈一个俏皮叫法：它通常不是指某一种额外发明的平衡条件，而是指把一段序列藏进平衡树的中序遍历，然后优雅地做翻转、剪贴、求和。值可以是字母、温度、角色台词；树真正维护的是它们的**位置关系**。今天我们就拿一句话开刀。

## 本节目标

学完后，你能：

- 从数组翻转中段的搬动代价，提出“把序列表示成一棵树”的需求；
- 区分按键有序树与隐式序列树：后者按中序位置而非元素值走路；
- 用子树大小找到第 k 个位置，并说出它维护的状态语义；
- 用两个哨兵和两次 Splay 把区间 [l,r] 暴露为一棵完整子树；
- 解释 Lazy 翻转为何只交换左右孩子并翻转标记，不必立刻触碰全部后代。

## 前置知识与课前自测

前置：序列下标、二叉树中序、子树大小。若已完成 [让刚访问的点靠近你](00-课前零食-让刚访问的点靠近你.md)，会更顺；还没完成也可先从本节的纸上实验理解模型。

1. 数组中翻转长度 k 的一段，至少会触碰多少个位置？
2. 序列 [7,2,7] 中，值 7 能唯一决定“第几个元素”吗？
3. 一棵树若维护 left_size，怎样寻找中序第 k 个节点？

<details><summary>先写答案：自测答案</summary>

1. 通常要读写 O(k) 个位置。2. 不能，重复值会让“按值找位置”失效。3. k≤left_size 去左；k=left_size+1 就是当前点；否则去右，并令 k 减去 left_size+1。

</details>

## 互动规则：先把“文字”当成位置卡，而不是字符

在纸上写一排卡片：

~~~text
A  B  C  D  E  F
1  2  3  4  5  6
~~~

贯穿任务有三步：翻转区间 [2,5]、询问 [2,5] 的元素数、再翻转 [1,6]。纸上仍写四栏：**对象**（哪一段卡片）、**状态**（size、sum、rev）、**动作**（分出还是暴露哪一段）、**账本**（中序位置是否仍等于逻辑序列）。先猜结果，再看图或程序。

“文艺”不在于把字母写得漂亮；它有趣在于，整段文本好像被一只手翻了过来，而程序只在根附近改了几条指针和一个小标签。

## 从零搭框架：从笨拙的数组编辑到隐式位置

### 第 0 步：先让数组亲自搬一次

将 B,C,D,E 反转，得到 A,E,D,C,B,F。若还要每次询问区间和或最小值，数组可以预处理前缀；但一次中段翻转之后，许多前缀信息全失效，重新建表又要 O(n)。

> 停顿 0：若连续做 reverse(2,5)、reverse(1,6)、reverse(3,4)，数组里哪些位置会被反复触碰？你能指出被重复维护的“前缀账本”吗？

<details><summary>展开：瓶颈不是不会 reverse，而是每次都铺开整段</summary>

第一次至少触碰 B,C,D,E，第二次触碰全部六项；任何依赖原顺序的前缀摘要都要跟着更新。我们想让“一个连续区间”在结构中成为一个可整体拿起的对象，而非散落在数组许多格里。

</details>

### 第 1 步：不要让元素值充当树的键

若把字母/数值当 BST 键，重复字母、相同分数会没有唯一位置；更糟的是，字典序与句子位置毫无关系。隐式平衡树只要求：**中序遍历的第 1、2、3……个节点，就是序列的第 1、2、3……项。**

于是节点不必存排序键，但必须存：

$$
size[u]=size[left[u]]+1+size[right[u]].
$$

这份 size 就是“这张卡左边藏了多少张卡”的账本。

![隐式键不是 value，而是中序位置](../插图/11-平衡树/00-文艺-01-隐式位置与size.svg)

> 停顿 1：在一棵中序为 A,B,C,D,E,F 的树中，若节点 D 左子树 size 为 3，D 是第几项？若要找第 5 项，第一次比较 k 与什么数？

<details><summary>展开：位置会随旋转变化，语义不会</summary>

D 是第 4 项；找第 5 项先比较 5 与 left_size+1=4，所以去右并把 k 改为 1。树形如何旋转不重要，只要每次改孩子后 pull，逻辑中序位置就正确。

</details>

### 第 2 步：先用三段思想把目标隔离

任何区间操作都可先在脑中切成：

~~~text
前缀 | 目标区间 | 后缀
~~~

FHQ Treap 会真的做两次 split；Splay 常用一个更戏剧化的动作：让目标区间变成某个节点的左子树。想取得 [l,r]，需要一对恰好夹住它的边界：

- 左边界：原序列第 l 项之前的节点；
- 右边界：原序列第 r 项之后的节点。

两端没有前驱或后继怎么办？给序列两侧各放一个永不参与答案的哨兵 L、R。完整中序变为 L,A,B,C,D,E,F,R；这不是多余装饰，而是把所有边界情况变成同一种情况。

> 停顿 2：在带左哨兵的完整中序中，原区间 [2,5] 左边界的全树排名是多少？右边界之后的节点全树排名又是多少？

<details><summary>展开：两次排名的偏移</summary>

完整排名是 L=1，A=2，B=3，C=4，D=5，E=6，F=7，R=8。原 [2,5] 的左边界是 A，排名 l=2；右边界之后是 F，排名 r+2=7。记住“左边界取 l、右边界取 r+2”，就不用为 l=1 或 r=n 写特判。

</details>

### 第 3 步：让两道边界把区间夹成一棵子树

令 x=kth(l)，y=kth(r+2)。先把 x splay 到根，再把 y splay 到 x 的右儿子位置。因为中序中所有目标元素严格在 x 与 y 之间，y 的左子树恰好就是 [l,r]。

![双哨兵把任何区间夹成后继的左子树](../插图/11-平衡树/00-文艺-02-双哨兵与区间暴露.svg)

~~~text
expose(l, r):
    x = kth(l)          # 左哨兵已计入排名
    splay(x, goal=null)
    y = kth(r + 2)
    splay(y, goal=x)
    return left_child(y)
~~~

这叫区间暴露（interval exposure）。它解决的瓶颈是“连续区间在树上并不天然是一棵子树”；两次 Splay 后，目标变成一棵真的可整体操作的子树。

## 问题动机：翻一整段，不想逐项翻

得到目标子树 mid 后，最笨的办法是中序列出它、反转列表、逐个塞回。可反转一棵二叉树的中序，只需对每个节点交换左右孩子；若直接递归每个节点仍是 O(length)。Lazy 标记让我们先对根写一笔“这整棵树待翻转”，等以后真的走进孩子再下传。

## 步步式引导：一个 rev 标签如何替一整段人跑腿

### 1. 对一个子树根应用翻转

~~~text
apply_rev(u):
    swap(left[u], right[u])
    rev[u] = rev[u] XOR 1
~~~

交换左右会把该子树的中序整体倒过来；两次翻转应抵消，所以标签用 XOR/布尔取反复合。若节点维护 sum，翻转不改变和；若维护首字符、尾字符或方向敏感哈希，则更新规则必须跟着交换，不能只偷懒改一个 rev。

> 停顿 3：对 A,B,C,D,E,F 暴露 [2,5] 后，只在 mid 根调用 apply_rev。此时若你立刻中序遍历、却从不 push，为什么可能读到旧顺序？什么时候必须把 rev 下传？

<details><summary>展开：标记代表逻辑顺序，访问才兑现细节</summary>

根交换儿子已让整棵 mid 的逻辑顺序反向，但孙辈可能还带着未兑现的方向。下一次要沿孩子指针找第 k 个、继续 split/splay 或输出时，应先 push，把父亲的翻转动作传给孩子。只读已由摘要正确维护的 size/sum 时不一定要展开所有后代。

</details>

### 2. 为什么 Splay 前要 push 祖先链

Splay 会根据“x 是父亲左还是右儿子”决定旋转。若祖先带 rev，逻辑上的左/右与当前裸指针可能不同。于是从目标祖先到 x 的路径必须先自顶向下 push；这是文艺平衡树最容易出现的“明明旋对了，字符串却倒着”的 bug 来源。

### 3. 文艺树不等于只能翻转

目标子树一旦暴露，sum、min、max、hash、最大子段和都可作为摘要；区间加、赋值、翻转等 Lazy 也可组合，只是每种标记都要明确：

1. 它作用于哪个摘要；
2. 两个标记先后到来时如何复合；
3. push 时对子树做什么。

不能因为一棵树“文艺”就把任意操作混上去；例如区间排序会改变大量相对顺序，通常没有一个常数大小 Lazy 能表达。

## 核心知识：序列语义、结构语义与摘要语义

| 账本 | 维护什么 | 何时更新 |
|---|---|---|
| 中序语义 | 节点排列就是逻辑序列 | 旋转、split/merge 后仍须保住 |
| size | 子树含多少位置 | 每次改孩子后 pull |
| 摘要 | sum/min/hash 等区间答案 | pull 或 apply 标记时 |
| rev | 这棵子树还欠一次方向翻转 | apply 时复合，走入孩子前 push |

Splay 通过摊还 O(log n) 的两次伸展暴露区间；一次 apply_rev 为 O(1)，所以翻转、区间查询的摊还复杂度通常为 O(log n)。FHQ Treap 以两次 split 加 merge 达到期望 O(log n)，接口不同，核心都是“把连续区间变成独立子树”。

## 实现指南

- 两个哨兵也参与 size；若维护 sum，哨兵 value 取 0，输出时不把它们当正文。
- 完整序列下 kth 的 k 从 1 开始；先固定“原序列下标从 1 开始”的约定，才不会把 l 与 l+1 混掉。
- expose 后修改 mid，随后要从 y 向上 pull，至少更新 y 和 x；本节互动程序也会检查根摘要。
- splay 前收集目标到 goal 之上的祖先链，倒序 push；只 push x 自己是不够的。
- 翻转对 sum 是不变的，但对前后缀、哈希和最大字段常有方向；设计摘要前先写出反转后的变换公式。
- 若只需静态区间和，Fenwick/线段树简单得多；文艺树的价值在于动态改变顺序。

## 纸上模拟：把 B,C,D,E 夹住后翻过去

完整中序是 L,A,B,C,D,E,F,R。对原 [2,5]，先填写：

| 项目 | 你应写下的内容 |
|---|---|
| x=kth(l) |  |
| y=kth(r+2) |  |
| y.left 的中序 |  |
| apply_rev 后逻辑中序 |  |
| 去掉哨兵后的最终序列 |  |

<details><summary>展开：一次暴露的完整答案</summary>

x=A，y=F，y.left 的中序为 B,C,D,E。对它 apply_rev 后为 E,D,C,B；全序列为 L,A,E,D,C,B,F,R，去掉哨兵即 A,E,D,C,B,F。注意 A 和 F 是夹子，不属于被翻转对象。

</details>

再做 reverse(1,6)。这次 x=L、y=R；它看起来像特殊边界，哨兵恰好让它与普通区间使用同一行 expose 伪代码。这就是哨兵最值得的地方：少的不是两行 if，而是一类容易错的思维分叉。

## 互动小实验室

运行 [把一段话翻过来.py](../../互动程序/11-平衡树/00-把一段话翻过来.py)。程序先请你预测 [2,5] 的边界 x、y，再用带双哨兵的隐式 Splay 暴露该区间。可输入：

- show：打印当前正文、中序位置和哨兵位置；
- rev 2 5：翻转一段；
- sum 2 5：查询一段数字摘要；
- expose 2 5：只展示两次 Splay 后 y.left 的区间；
- check：拿普通列表作小规模验算，检查 size、sum、parent 与逻辑序列。

先写下你认为 y.left 应是哪几张卡，再执行 expose。若输出与预期不同，优先检查排名是否把左哨兵算进去了。

## 扩展与联系

- “文艺平衡树”是竞赛语境的昵称；可以用 Splay、FHQ Treap、甚至 Rope 一类结构实现动态序列，关键是中序位置和区间切分。
- [隐式 FHQ Treap 正式课](02-隐式FHQ-Treap序列操作.md)用 split/merge 暴露同一类区间；[Splay 正式课](03-Splay伸展与区间暴露.md)用双哨兵展示另一种接口。
- 字符串哈希做区间翻转时，通常要同时维护正向与反向哈希；只维护一个方向会失去 O(1) 合并能力。
- 若操作只有区间翻转、没有插删，某些题可用离线技巧或块状结构；先比较约束，别为了名字“文艺”而过度建树。

## 总结与自检

1. 为什么隐式序列树不能把 value 当 BST 键？
2. 原区间 [l,r] 在双哨兵 Splay 中如何选择两道边界？
3. rev 为什么要交换左右孩子并 XOR 标记？
4. 哪些时机必须 push Lazy？

<details><summary>自检答案</summary>

重复值与位置无关；x 是 kth(l)，y 是 kth(r+2)，目标为 y.left；交换改变中序方向、XOR 表示两次抵消；走向孩子、按排名定位和旋转前的祖先链都必须兑现逻辑标记。

</details>

## 一周预热安排

- 第 1 天：用数组连续翻三段，记录哪些前缀信息反复失效。
- 第 2 天：给一棵小树标 size，手找第 1、4、6 项。
- 第 3 天：在 L,A,B,C,D,E,F,R 上手做一次 expose(2,5)。
- 第 4 天：手做 apply_rev，并写下哪次访问需要 push。
- 第 5 天：运行互动程序后进入[隐式 FHQ Treap](02-隐式FHQ-Treap序列操作.md)或[Splay 区间暴露](03-Splay伸展与区间暴露.md)。