第 14 章 扩充数据结构 (Augmenting Data Structures)
核心结论
-
扩充模式 (Augmentation)：在基础数据结构上加字段以支持新操作——4 步：(1) 选底层结构；(2) 确定要维护的附加信息；(3) 验证附加信息可在基本操作中高效维护；(4) 开发新操作。
-
顺序统计树 (OS-Tree)：红黑树加 size 字段——每节点 x.size = \(x.left.size + x.right.size + 1\)；支持 OS-SELECT (第 i 小)、OS-RANK (排名) 都在 O(lg n) 时间。
-
OS-Tree 维护：插入时沿路径 +1（含旋转处 O(1) 更新），删除时沿路径 -1；总 O(lg n) 时间不变。
-
红黑树扩充定理 (定理 14.1)：若附加字段 f 只依赖 x / x.left / x.right 及其子字段，则 INSERT / DELETE 可在 O(lg n) 维护 f——「f 改变只向上传播」是核心洞察。
-
区间树 (Interval Tree)：红黑树加 max 字段（子树最大 high 端点）+ int 域；INTERVAL-SEARCH 在 O(lg n) 找重叠区间。
-
应用：逆序数（§14.1-7）、交叠区间（§14.3）、Josephus 排列（问题 14-2）、VLSI 矩形检测（§14.3-7）。
|
本章主旨
本章是「数据结构的最后一招」——扩充（augmentation）。当你需要的操作超出「教科书」数据结构直接提供的（插入 / 查找 / 删除 / 最大 / 最小 / 后继）时，往往不必发明全新数据结构，而是在已有结构（如红黑树）上加字段 + 维护规则 + 新操作。本章三个核心：(1) §14.1 顺序统计树——最经典例子（size 字段）；(2) §14.2 扩充的通用定理（定理 14.1）——告诉你何时扩充是 O(lg n) 而不影响原操作；(3) §14.3 区间树——实际工程常见的「重叠查询」应用。本章也是「如何用现有工具解决新问题」的方法论展示。 |
一、核心概念
本章围绕 4 个核心概念展开：从顺序统计树（最经典扩充例子）开始，抽象出扩充红黑树的一般定理，最后用区间树展示实际工程应用。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
顺序统计树 (OS-Tree) |
红黑树 + size 字段（子树节点数）；支持 OS-SELECT（第 i 小）与 OS-RANK（排名）O(lg n)；可作有序字典的「动态中位数」结构。 |
§14.1；size 字段定义：x.size = x.left.size + x.right.size + 1（T:nil.size = 0）。 |
OS-SELECT / OS-RANK 算法 |
OS-SELECT 沿树下降：若 i = r（左子树大小 + 1）→ 当前；i < r → 左子树；i > r → 右子树第 (i - r) 小。OS-RANK 沿父链向上：若当前是右孩子 → 加左子树大小 + 1。 |
§14.1；都 O(h) = O(lg n)；中序遍历中第 i 个与「rank」统一。 |
红黑树扩充定理 (定理 14.1) |
若附加字段 f(x) 只依赖 x / x.left / x.right（及其子字段），则 INSERT / DELETE 维护 f 在 O(lg n) 时间；原因：f 改变只向父节点传播。 |
§14.2；通用工具——下次需要「加字段」时先用定理判定是否高效；旋转是 O(1) 维护 f 的常见途径。 |
区间树 (Interval Tree) |
红黑树 + max 字段（子树最大 high 端点）+ int 域；INTERVAL-SEARCH O(lg n) 找任意与查询区间重叠的区间；用 max 判断「是否需要深入左子树」。 |
§14.3；INTERVAL-SEARCH 正确性：定理 14.2 用循环不变量证明——若左子树无重叠且 max ≥ low，左子树可能包含。 |
二、详细笔记
14.1 顺序统计树 (OS-Tree)
What：在红黑树每个节点加 size 字段（子树节点数），支持 OS-SELECT（找第 i 小）与 OS-RANK（找 x 的排名）操作。
Why：第 9 章的 SELECT 算法虽然线性，但用一次后即「过时」；OS-Tree 让动态集合的「第 i 小」「排名第 i」都 O(lg n) — 支持插入删除。
How：
-
字段定义（§14.1）：x.size = x.left.size + x.right.size + 1；T:nil.size = 0；新节点初始 size = 1。
-
OS-SELECT(x, i) - 找 x 为根的子树中第 i 小：
\[\begin{array}{rl} & \textbf{OS-SELECT}(x, i) \\ 1 & r = x.\text{left}.\text{size} + 1 \\ 2 & \textbf{if } i == r \\ 3 & \quad \textbf{return } x \\ 4 & \textbf{elseif } i < r \\ 5 & \quad \textbf{return } \textbf{OS-SELECT}(x.\text{left}, i) \\ 6 & \textbf{else } \textbf{return } \textbf{OS-SELECT}(x.\text{right}, i - r) \end{array}\] -
OS-RANK(T, x) - 找 x 在 T 中的排名（1-indexed）：
\[\begin{array}{rl} & \textbf{OS-RANK}(T, x) \\ 1 & r = x.\text{left}.\text{size} + 1 \\ 2 & y = x \\ 3 & \textbf{while } y \neq T.\text{root} \\ 4 & \quad \textbf{if } y == y.\text{p}.\text{right} \\ 5 & \quad\quad r = r + y.\text{p}.\text{left}.\text{size} + 1 \\ 6 & \quad y = y.\text{p} \\ 7 & \textbf{return } r \end{array}\] -
维护 size（INSERT）：
-
阶段 1（沿树下降）：对路径上每个节点 + 1（含新节点 size = 1）。
-
阶段 2（最多 2 次旋转）：LEFT-ROTATE 加
x.size = y.size; y.size = x.left.size + x.right.size + 1（y 在前，x 在后）。
-
-
维护 size（DELETE）：阶段 1 沿路径 - 1；阶段 2 旋转同 INSERT。
-
复杂度：OS-SELECT / OS-RANK 都 O(lg n)；维护 size 总 O(lg n)，不增渐近时间。
When： . 动态集合 + 频繁查「第 i 小 / 排名第 i」 → OS-Tree。 . 静态集合 → 第 9 章的 SELECT；但已知 SELECT 后无法动态更新。 . 计数逆序（练习 14.1-7） → 用 OS-Tree 累加左边未出现次数 = O(n lg n)。
Example（图 14.1）：OS-SELECT(T.root, 17)： * x = 26, r = 12+1 = 13；i=17 > 13 → 右子树中第 4 小。 * x = 41, r = 5+1 = 6；i=4 < 6 → 左子树中第 4 小。 * x = 30, r = 1+1 = 2；i=4 > 2 → 右子树中第 2 小。 * x = 38, left.size = 1 → r = 2；i=2 → 返回 38。
14.2 扩充红黑树 (定理 14.1)
What：扩充数据结构的通用方法 + 一个让扩充「自动 O(lg n)」的充分条件。
Why：避免每次需要新功能时都重新设计——给出一个「何时直接维护是高效的」判定标准。
How：
-
4 步扩充法（§14.2）：
-
选底层结构：基于红黑树（操作齐全 + 高度有界）。
-
定附加信息：如 size 字段；理想是 O(1) 空间。
-
验证维护：插入 / 删除可 O(lg n) 维护附加信息 —— 核心难点。
-
开发新操作：OS-SELECT、INTERVAL-SEARCH 等。
-
定理 14.1：扩充红黑树：
-
条件：附加字段 f(x) 只依赖 x / x.left / x.right（及其子字段 f）。
-
结论：INSERT / DELETE 维护 f 在 O(lg n) 时间，不影响 O(lg n) 性能。
-
证明要点：f 改变只向父节点传播（局部依赖）；上溯路径 O(lg n)；旋转时局部更新 f（每次 O(1) 或 O(lg n)）。
-
-
示例：
-
size 字段：满足定理 → O(lg n)。
-
黑高字段：满足定理 → 可维护（练习 14.2-2）。
-
节点深度：不满足（依赖整树） → O(n) 维护。
-
When： . 任何「字段只依赖局部」的红黑树扩充 → 定理 14.1 直接给出 O(lg n) 保证。 . 需要 O(n) 字段 → 不能用红黑树（如总节点数、外部统计）。 . 字段需要「跨树」信息 → 高级数据结构（link-cut tree / Euler-tour tree）。
Example（OS-Tree 是定理 14.1 的典范）：f = size，依赖 x.left.size 与 x.right.size；插入沿路径 +1（O(lg n)）；旋转时按图 14.2 更新（O(1)）。
14.3 区间树 (Interval Tree)
What：在红黑树上存储区间 int + max 字段（子树最大 high 端点），支持 INTERVAL-SEARCH（找任意与查询区间重叠的区间）。
Why：实际工程常见需求——时间区间重叠查询（数据库、调度、几何）；O(lg n) 优于朴素的 O(n)。
How：
-
底层结构（步骤 1）：红黑树 + 节点 x 包含区间 x.int（low, high）；x.key = x.int.low。
-
附加信息（步骤 2）：x.max = max 子树中所有区间的 high 端点；满足 x.max = max(x.int.high, x.left.max, x.right.max)。
-
维护 max（步骤 3）：由定理 14.1，INSERT / DELETE O(lg n)；旋转时 O(1) 更新。
-
INTERVAL-SEARCH(T, i)（步骤 4）：
\[\begin{array}{rl} & \textbf{INTERVAL-SEARCH}(T, i) \\ 1 & x = T.\text{root} \\ 2 & \textbf{while } x \neq T.\text{nil } \textbf{ and } i \textbf{ does not overlap } x.\text{int} \\ 3 & \quad \textbf{if } x.\text{left} \neq T.\text{nil } \textbf{ and } x.\text{left}.\text{max} \geq i.\text{low} \\ 4 & \quad\quad x = x.\text{left} \\ 5 & \quad \textbf{else } x = x.\text{right} \\ 6 & \textbf{return } x \end{array}\] -
定理 14.2 正确性：
-
循环不变量：若 T 中存在与 i 重叠的区间，则当前 x 子树必包含之。
-
情形 A（向右）：x.left = NIL 或 x.left.max < i.low → 任取 x.left 中区间 i'：i'.high ≤ x.left.max < i.low → i'.high < i.low → 不重叠。
-
情形 B（向左）：x.left.max ≥ i.low → 存在区间 i' in x.left 子树使 i'.high = x.left.max ≥ i.low；又 i 不重叠 x.int，不重叠 i'；由 i'.high ≥ i.low 推断 i.high < i'.low；故 x.right 中任一区间的 low ≥ i'.low > i.high → 都不重叠。
-
故沿此路径一定找到或确定不存在 → O(lg n)。
-
When： . 时间区间日程查询 → 区间树。 . 空间矩形重叠 → 区间树 + 扫除线（练习 14.3-7）→ O(n lg n)。 . 单点匹配查询（找含点 i 的所有区间）→ 区间树 O(lg n + k)（列出 k 个结果）。
Example（图 14.4 + INTERVAL-SEARCH）：查找 [22, 25]： * x = [16,21] 不重叠；左子树 max = 23 ≥ 22 → 左 x = [8,9] 不重叠；左子树 max = 10 < 22 → 右 x = [15,23] 重叠 → 返回。
三、关键图表
|
核心公式对照表
|
四、思维导图
mindmap
root((第 14 章 扩充数据结构))
OS-Tree
size字段
第i小
排名
维护O(lg n)
四步法
选结构
定字段
验证维护
新操作
定理14.1
局部依赖
父链传播
O(lg n)
区间树
max字段
重叠查询
INTERVAL-SEARCH
定理14.2
应用
逆序数
调度
VLSI
Josephus
方法论
不要重发明
加字段解新题
维护规则五、重点与易错点
-
扩充 vs 重新设计 — 优先尝试扩充（成本低、复用现有结构）；只在 O(lg n) 维护不成立时重新设计。
-
size 字段不能存「整树节点数」（应是子树节点数） — 不然 INSERT 改全部节点——O(n) 不行。
-
OS-SELECT 用 \(r = x.left.size + 1\) — 这是「x 在 x 子树中的排名」；选 i = r 时返回 x。
-
OS-RANK 的 while 循环：y = x 起、y = y.p 终止到根 — 若 y 是右孩子 → 加「父的左子树 + 1」。
-
插入维护 size 时是「沿下降路径」+ 1 — 而不是「整树 + 1」；每节点只 + 1，但 O(lg n) 个节点。
-
删除维护 size 时是「沿 y 上升路径」- 1 — y 是被删除或被 splice 的节点；O(lg n) 步。
-
旋转时更新 size 的顺序 — 必须先更新「子节点」size（LEFT-ROTATE 后 y 变子根），再到 x（x.size = x.left.size + x.right.size + 1）。
-
定理 14.1 的「局部依赖」是关键 — 若 f 依赖整树（如总节点数），则任何插入改全部 → 不适用。
-
区间树 key 用 low 端点 — 这样 BST 性质按 low 排序；max 用 high 而非 low——是「为查询便利的异类」设计。
-
INTERVAL-SEARCH 选「向左」vs「向右」的依据 — 是 left.max ≥ i.low（说明左可能有）+ 不重叠当前的判断。
-
INTERVAL-SEARCH 单调下降可能找不到 — 即使左边可能有，x.int 不重叠仍可能右子树有（max < low 时转右）。
-
「定理 14.2 循环不变量」的直观 — 当前 x 子树若含与 i 重叠的区间，则按 max 规则一定能下降到它。
-
RB-ENUMERATE(x, a, b) = Θ(m + lg n)（练习 14.2-4）— 利用 BST 范围剪枝；先 OS-SELECT(a)，再向后列举到 b。
-
应用：逆序数 = O(n lg n) — 插入每个 A[i] 到 OS-Tree，OS-RANK 给出已插入中比它大的个数（累加 = 逆序数）。
-
应用：Josephus 排列 — 用 OS-Tree 模拟反复删第 m 元素；O(n lg n) 或常数 m 时 O(n)。
-
MIN-GAP 集合（练习 14.3-6） — 维护有序集合 + 子树中相邻差最小 → 区间树扩展。
-
补充：与其他章节的衔接
-
第 9 章（中位数与顺序统计）：OS-Tree 让「动态中位数」「动态第 i 小」成为可能——本章是其动态版本。
-
第 12 / 13 章（BST / 红黑树）：本章以红黑树为底层；B 树（章 18）也可类似扩充。
-
第 15 章（动态规划）：OS-Tree 可作「最长递增子序列」的动态结构。
-
第 17 章（摊还分析）：splay 树 / 伸展操作也涉及树高 / 路径的附加信息维护。
-
第 20 章（van Emde Boas）：另一种有序字典——以 O(lg lg u) 而不是 O(lg n) 时间——也是「非基于比较」的有序结构。
-
第 23 / 24 章（图算法）：图的动态算法（如动态 MST）也用「树 + 附加字段」维持。