第 14 章数据结构的扩张

工程中很少需要发明全新的数据结构，更常见的是在教科书结构上多存一点信息，再为它写几个新操作。本章在平衡树的每个结点上加一个"子树汇总"字段，就得到了两个在量化里非常实用的结构：顺序统计树（动态集合上的第 \(k\) 小与秩）和区间树（动态区间集合上的重叠查询）。把"子树结点数"换成"子树挂单量"，同一套方法就能在 \(O(\lg n)\) 内回答"市价吃掉 \(Q\) 股要穿透到哪一档、成交均价是多少"。

学习目标

掌握顺序统计树：size 属性的定义与维护，OS-SELECT 与 OS-RANK 的算法和循环不变式。
理解扩张数据结构的四步法，以及为什么要存"子树规模"而不是"全局秩"。
理解定理 14.1：只依赖结点自身与两个孩子的属性，可以在红黑树插入删除中维护而不改变 \(O(\lg n)\)。
掌握区间树的设计、INTERVAL-SEARCH 的正确性证明（区间三分律）。
能把这些结构用在订单簿深度查询、滚动百分位排名、Kendall \(\tau\) 计算、在册订单的时间区间查询上。

读前导读

这一章在解决什么问题。 上一章的红黑树能快速回答"最低卖价""下一档"，但回答不了"第 20 档是哪个价位""市价买 5 万股要吃到第几档"。原因是树只记得"谁比谁大"，不记得"一共有多少"。本章的办法很朴素：在每个结点上多记一个汇总数字，比如"我这一片（子树）一共有多少个价位"或"一共挂了多少股"。有了它，就能像查公司组织架构一样快速定位："总部 300 人，第 20 号员工在哪？左边部门 12 人，所以不在左边；总经理是第 13 号；去右边部门找第 7 号……"每层只看一个数，走 \(\lg n\) 层就到。

这和你做合并报表的思路一模一样：每个子公司报表汇总自己及下属的数字，母公司只需加总直属子公司，不用回到每一张原始凭证。本章的核心定理（定理 14.1）用算法语言说的就是：只要每个结点的汇总值能由"自己 + 两个直接下属的汇总值"算出来，增删一个结点时只需沿着它往上的那条汇报线逐级更新，代价与树高成正比。 反过来，如果某个汇总值依赖树外的信息（比如"我在全公司排第几"），一个新人入职就要让大量人改数，那就不能这么做。

本章第二个结构是区间树，用来管理"时间段"：一笔订单从提交到撤销是一个区间，一次停牌是一个区间。问题是"13:00:00 到 13:00:05 之间有哪些订单在册"。办法同样是在每个结点多记一个汇总值：这一片里最晚结束的时刻。

需要先想起来的数学。

秩与顺序统计量。 秩就是"从小到大排第几"，第 \(i\) 个顺序统计量就是"排第 \(i\) 的那个"。两者互为反函数：OS-SELECT 由名次找元素，OS-RANK 由元素找名次。本册第 09 章已讲过静态版本。
结合律。 运算 \(\otimes\) 满足 \((a\otimes b)\otimes c=a\otimes(b\otimes c)\)，就可以随意加括号、分组计算。加法、取最大值满足；减法不满足（\((5-3)-1\ne5-(3-1)\)）。它保证"先分别汇总左右两半再合并"与"从头加到尾"结果相同。见第 00 册第 08 章读懂数学证明与符号。
循环不变式。 一种证明循环正确的方法：找一句话，证明它在循环开始前成立（初始化）、每走一步仍成立（保持）、循环结束时能推出想要的结论（终止）。它本质是数学归纳法。类比银行日终对账：每笔交易后"账面余额 = 期初 + 累计收入 − 累计支出"都成立，日终余额自然正确。见第 00 册第 08 章。
逆否命题。 "若 P 则 Q"等价于"若非 Q 则非 P"。定理 14.2 的证明用了它。例："若是 A 股则有涨跌停"等价于"若无涨跌停则不是 A 股"。见第 00 册第 08 章。
Kendall \(\tau\)。 统计所有股票两两配对，因子排序与收益排序方向一致的对数减去方向相反的对数，再除以总对数。它是秩相关系数，CFA 里的 Spearman 秩相关是它的近亲。

怎么读这一章。 14.1 节必读，尤其是 OS-SELECT 的例子和 size 的维护。14.2 节的"第 3 步决定成败"和定理 14.1 是本章的思想核心，必读；关于结合律的那段第一次可以只看结论。14.3 节读懂区间树的设计和 INTERVAL-SEARCH 的例子即可，定理 14.2 的证明可以跟着下面的讲解框读一遍。14.3.4 两道思考题可以跳过。14.4 节量化实战必读，订单簿深度查询那部分是本章最直接的应用。

14.1 动态顺序统计

\(n\) 个元素的第 \(i\) 个顺序统计量（order statistic）是第 \(i\) 小的元素。对一个静态无序集合，线性时间选择算法可以在 \(O(n)\) 内求出（本册第 9 章）。若集合在不断变化，每次都重新选择就太慢了。本节让动态集合的任意顺序统计量、以及任意元素的秩（rank）（它在线性序中的位置）都能在 \(O(\lg n)\) 内求出。

14.1.1 顺序统计树

**顺序统计树（order-statistic tree）**是在红黑树每个结点 \(x\) 上增加属性 \(x.size\)——以 \(x\) 为根的子树中内部结点的个数（含 \(x\) 自己）。令哨兵 \(T.nil.size=0\)，则

\[x.size=x.left.size+x.right.size+1.\]

白话解释：\(x.size\) 就是"以 \(x\) 为负责人的这个部门（含下属部门）一共几个人"。公式 \(x.size=x.left.size+x.right.size+1\) 是说：部门人数 = 左边下属部门人数 + 右边下属部门人数 + 负责人自己。哨兵的 size 是 0，相当于"空部门 0 人"，这样叶子结点也能套用同一个公式：\(0+0+1=1\)。

关键字不要求互异。有重复时，元素的秩定义为它在中序遍历中被输出的位置（原书图 14.1 中有两个 14：黑结点里的 14 秩为 5，红结点里的秩为 6）。

14.1.2 查找给定秩的元素：OS-SELECT

def OS_SELECT(x, i):                  # 以 x 为根的子树中第 i 小的结点
    r = x.left.size + 1               # x 在自己子树中的秩
    if i == r:   return x
    elif i < r:  return OS_SELECT(x.left, i)
    else:        return OS_SELECT(x.right, i - r)

\(x.left.size\) 恰是子树中序遍历中排在 \(x\) 之前的结点数，所以 \(r=x.left.size+1\) 是 \(x\) 在子树中的秩。若 \(i>r\)，右子树之前已经有 \(r\) 个元素，要找的是右子树中第 \(i-r\) 小的。

原书例：在图 14.1 中找第 17 小。根 26 的左子树大小 12，秩 13，转右子树找第 \(17-13=4\) 小；结点 41 左子树大小 5，秩 6，转左子树找第 4 小；结点 30 秩 2，转右子树（根 38）找第 \(4-2=2\) 小；38 的左子树大小 1，秩 2，于是 38 就是答案。每次递归下降一层，时间 \(O(\lg n)\)。

金融直觉：把卖方价位按从低到高存进顺序统计树，OS-SELECT(5) 就是"卖五价"，OS-SELECT(1) 是最优卖价。不用扩张时，求卖五价要从最优价起连续求 4 次后继；价位很多、要查第 200 档时，代价就是 200 步。有了 size，不管查第几档都只走一条从根到底的路径，约 \(\lg n\) 步。每一步的判断就像查一份按区间编号的档案柜："左边柜子有 12 份，我要第 17 份，那就不在左边；中间这份是第 13 份；去右边柜子找第 \(17-13=4\) 份。"

14.1.3 求元素的秩：OS-RANK

def OS_RANK(T, x):
    r = x.left.size + 1
    y = x
    while y is not T.root:
        if y == y.p.right:                   # y 是右孩子：父结点及其左子树都排在 x 之前
            r = r + y.p.left.size + 1
        y = y.p
    return r

循环不变式：每次迭代开始时，\(r\) 是 \(x.key\) 在以 \(y\) 为根的子树中的秩。

初始化：\(y=x\)，\(r\) 是 \(x\) 在自身子树中的秩。
保持：\(y\) 上移到 \(y.p\) 时，若 \(y\) 是左孩子，\(y.p\) 及其右子树都在 \(x\) 之后，\(r\) 不变；若 \(y\) 是右孩子，\(y.p\) 和它的左子树都在 \(x\) 之前，加上 \(y.p.left.size+1\)。
终止：\(y\) 到达根时，\(r\) 就是 \(x\) 在整棵树中的秩。

原书例：求图 14.1 中键 38 的秩，循环顶部 \((y.key,r)\) 依次为 \((38,2)\)、\((30,4)\)、\((41,4)\)、\((26,17)\)，返回 17。\(O(\lg n)\)。

推导拆解：把原书例子逐步对上循环里的那一行。起点 \(y=38\)：38 的左子树 1 个结点，所以 38 在自己子树里排第 \(1+1=2\)。 \(y\) 从 38 上移到 30：38 是 30 的右孩子，说明 30 和 30 的左子树都比 38 小。30 的左子树 1 个结点，所以 \(r=2+1+1=4\)。 \(y\) 从 30 上移到 41：30 是 41 的左孩子，说明 41 和它的右子树都比 38 大，不影响名次，\(r\) 仍为 4。 \(y\) 从 41 上移到根 26：41 是 26 的右孩子，26 和它左子树的 12 个结点都比 38 小，\(r=4+12+1=17\)。到根停止。规则一句话："往上走时，每次从右边上来，就把父亲和父亲的左边部门都算到自己前面。"

若手里只有关键字而没有结点指针，可以从根往下走，边走边累加左侧的结点数（习题 14.1-4 的 OS-KEY-RANK）；下文代码的 rank_lt 就是这种写法，它不需要父指针。

14.1.4 维护 size

插入分两个阶段。第一阶段自根向下找插入位置时，把路径上每个结点的 \(size\) 加 1，新结点 \(size=1\)，额外代价 \(O(\lg n)\)。第二阶段向上修复时，结构变化只来自至多 2 次旋转；旋转是局部操作，只有旋转所绕的那条边连接的两个结点的 \(size\) 会失效。在 LEFT-ROTATE 末尾加两行即可：

y.size = x.size
x.size = x.left.size + x.right.size + 1

原书图 14.2：左旋前 \(x.size=19\)、\(y.size=12\)；左旋后 \(y\) 继承 19，\(x\) 重算为 \(6+4+1=11\)。

删除同理：第一阶段从被移除或上移的结点 \(y\) 的原位置向上到根，路径上每个结点 \(size\) 减 1；第二阶段至多 3 次旋转，同样处理。所以带 size 维护的插入、删除仍是 \(O(\lg n)\)。

14.2 如何扩张一个数据结构

扩张一个数据结构分四步：

选择基础数据结构；
确定要在其中维护的附加信息；
检验基础结构上的修改操作能否维护这些附加信息；
设计新操作。

这不是机械的流程，设计往往在几步之间来回试错——如果附加信息不能高效维护，前面的选择就要推翻。以顺序统计树为例：选红黑树是因为它已经高效支持 MIN、MAX、SUCCESSOR、PREDECESSOR；附加 size；验证插入删除能 \(O(\lg n)\) 维护它；开发 OS-SELECT 和 OS-RANK。

第 3 步决定成败。 一个反例：如果每个结点直接存它在整棵树里的秩，OS-SELECT 和 OS-RANK 会更快，但插入一个新的最小元素会让每个结点的秩都加 1，维护代价 \(\Theta(n)\)。存子树规模则插入只影响 \(O(\lg n)\) 个结点。好的附加信息是局部的：它只依赖于子树，不依赖于子树以外的东西。下面的定理把这一点说清楚。

金融直觉：这就是"连续编号凭证"和"分部门小计"的区别。如果每张凭证上都印着它在全年的流水号，年中补录一张 1 月的凭证，后面所有凭证都要改号——\(\Theta(n)\)。如果每个文件夹只在封面写"本夹共几张"，补录一张只需改这张所在文件夹、它的上级文件夹……一直到总档案柜的封面，改动数等于层级数——\(O(\lg n)\)。需要流水号时，现算即可（OS-RANK），也只需 \(O(\lg n)\)。

定理 14.1（红黑树的扩张）：设 \(f\) 是 \(n\) 结点红黑树 \(T\) 上的一个属性，且每个结点 \(x\) 的 \(f\) 值只依赖于 \(x\)、\(x.left\)、\(x.right\) 中的信息（可以包括 \(x.left.f\) 与 \(x.right.f\)）。那么在插入和删除中可以维护所有结点的 \(f\) 值，而不改变这两个操作 \(O(\lg n)\) 的渐近性能。

证明思路. 改变某个结点的 \(f\) 只会影响它的祖先：改 \(x.f\) 可能要改 \(x.p.f\)，再可能改 \(x.p.p.f\)……直到根。树高 \(O(\lg n)\)，所以一次传播 \(O(\lg n)\)。插入第一阶段新结点的 \(f\) 可 \(O(1)\) 算出再向上传播；第二阶段至多 2 次旋转，每次只改变两个结点，各传播 \(O(\lg n)\)。删除第一阶段是局部修改，第二阶段至多 3 次旋转。总计 \(O(\lg n)\)。\(\square\)

很多情况下（比如 size），旋转后只需 \(O(1)\) 更新，不必一路传播到根（习题 14.2-3）。更一般地，若 \(x.f=x_1.a\otimes x_2.a\otimes\cdots\otimes x_m.a\)，其中 \(\otimes\) 是满足结合律的二元运算、\(x_1,\dots,x_m\) 是子树的中序序列，则旋转后 \(f\) 可 \(O(1)\) 更新。求和、最大值、最小值、计数、"矩阵乘积"都满足结合律——这就是线段树等"区间汇总"结构的共同原理。

白话解释：为什么满足结合律的汇总在旋转后能 \(O(1)\) 更新？旋转不改变中序次序 \(\alpha,x,\beta,y,\gamma\)，只改"谁管谁"。旋转前 \(x\) 管 \(\alpha,x,\beta,y,\gamma\) 全部，旋转后 \(y\) 管全部——所以 \(y\) 的新汇总值就是 \(x\) 的旧汇总值，直接继承（对应 size 维护的 y.size = x.size）。\(x\) 现在只管 \(\alpha,x,\beta\)，用"左孩子汇总 ⊗ 自己 ⊗ 右孩子汇总"重算一次即可。结合律保证"按新的分组方式合并"与"按旧方式合并"结果一样。三个子树 \(\alpha,\beta,\gamma\) 本身内容没变，汇总值不用动。

反过来，结点的深度不能作为扩张属性：一次旋转会改变整棵子树里所有结点的深度（习题 14.2-2）。结点的黑高则可以，因为它只依赖孩子。

另一个有用的结论（习题 14.2-4）：不需要任何新属性，就能在 \(\Theta(m+\lg n)\) 时间内输出所有满足 \(a\le k\le b\) 的关键字（\(m\) 为输出个数）——从 \(a\) 的位置开始连续求后继即可。这就是"列出 \([10.00,10.20]\) 之间的所有价位"。

14.3 区间树

14.3.1 区间与区间三分律

闭区间 \([t_1,t_2]\)（\(t_1\le t_2\)）表示 \(\{t\in\mathbb R:t_1\le t\le t_2\}\)。用对象 \(i\) 表示区间，\(i.low=t_1\)，\(i.high=t_2\)。两个区间 \(i\)、\(i'\) **重叠（overlap）**当且仅当 \(i\cap i'\ne\emptyset\)，即

i.low\le i'.high\quad\text{且}\quad i'.low\le i.high.

区间三分律（interval trichotomy）：任意两个区间恰好满足以下三者之一：(a) 重叠；(b) \(i\) 在 \(i'\) 左边，\(i.high<i'.low\)；(c) \(i\) 在 \(i'\) 右边，\(i'.high<i.low\)。

推导拆解：重叠条件为什么是这两个不等式？从反面想更容易。两个区间不重叠只有两种可能：\(i\) 整个在 \(i'\) 左边（\(i\) 结束得比 \(i'\) 开始还早，\(i.high<i'.low\)），或整个在右边（\(i'.high<i.low\)）。把"不重叠"取反，就是两个"不早于"同时成立：\(i.high\ge i'.low\) 且 \(i'.high\ge i.low\)。例：订单 A 在 [9:30, 10:15] 在册，查询窗口 [10:00, 10:30]：\(10{:}15\ge10{:}00\) 且 \(10{:}30\ge9{:}30\)，重叠。这三种情况恰好覆盖全部可能且互不相容，就是"三分律"。符号 \(i\cap i'\ne\emptyset\) 读作"两个集合的交集非空"，即有公共点。

区间天然适合表示"占用一段连续时间的事件"：一笔限价单从提交到撤销或成交的存续期、一次停牌、一个交易时段、一个事件研究的窗口。

14.3.2 按四步法设计区间树

**区间树（interval tree）**维护元素的动态集合，每个元素 \(x\) 带一个区间 \(x.int\)，支持 INTERVAL-INSERT、INTERVAL-DELETE 和 INTERVAL-SEARCH(T, i)（返回任一区间与 \(i\) 重叠的元素，没有则返回 \(T.nil\)）。

步骤 1（基础结构）：红黑树，关键字是低端点 \(x.int.low\)；中序遍历按低端点排序。
步骤 2（附加信息）：\(x.max\) = 以 \(x\) 为根的子树中所有区间高端点的最大值。
步骤 3（维护）：\(x.max=\max(x.int.high,\ x.left.max,\ x.right.max)\)，只依赖结点本身和两个孩子，由定理 14.1 插入删除仍是 \(O(\lg n)\)；实际上旋转后 \(O(1)\) 即可更新。
步骤 4（新操作）：

def INTERVAL_SEARCH(T, i):
    x = T.root
    while x is not T.nil and not overlap(i, x.int):
        if x.left is not T.nil and x.left.max >= i.low:
            x = x.left          # 左子树里可能有重叠区间
        else:
            x = x.right
    return x                    # O(lg n)：只沿一条从根向下的路径

原书例（图 14.4，10 个区间：[0,3]、[5,8]、[6,10]、[8,9]、[15,23]、[16,21]、[17,19]、[19,20]、[25,30]、[26,26]，根为 [16,21]）：

查 \(i=[22,25]\)：根 [16,21] 不重叠；左孩子的 max 为 23 ≥ 22，往左到 [8,9]，不重叠；其左孩子 max 为 10 < 22，往右到 [15,23]，重叠，返回。
查 \(i=[11,14]\)：根不重叠，左孩子 max 23 ≥ 11，往左到 [8,9]；不重叠，左孩子 max 10 < 11，往右到 [15,23]；不重叠，左孩子为空，往右，到达 \(T.nil\)，返回"无"。

白话解释：为什么只按"开始时刻"排序还不够，必须加 max？查"13:00 在册的订单"时，一笔 9:35 提交、14:00 才撤的老单开始得很早，排在树的左边深处。只看开始时刻，你无法判断左边那一大片里有没有"开得早、关得晚"的订单，只能全部翻一遍。max 记录"这一片里最晚的结束时刻"，相当于给每个文件夹贴一个"本夹最晚到期日"标签：如果标签早于你的查询起点，整夹都不可能和查询重叠，直接跳过。

14.3.3 正确性

定理 14.2：INTERVAL-SEARCH 要么返回一个与 \(i\) 重叠的结点，要么返回 \(T.nil\) 且树中没有与 \(i\) 重叠的区间。

证明. 只需讨论在 \(x=T.nil\) 时终止的情况。循环不变式：若 \(T\) 中有与 \(i\) 重叠的区间，则以 \(x\) 为根的子树中一定有。

往右走时：要么左子树为空，要么 \(x.left.max<i.low\)。后一种情况下左子树中任一区间 \(i'\) 有 \(i'.high\le x.left.max<i.low\)，由三分律不重叠。所以重叠区间（若有）只能在右子树或 \(x\) 本身，而 \(x\) 已检查过不重叠。
往左走时：证明逆否命题——若左子树中没有重叠区间，则整棵树中也没有。因为 \(x.left.max\ge i.low\)，左子树中存在区间 \(i'\) 使 \(i'.high=x.left.max\ge i.low\)；\(i\) 与 \(i'\) 不重叠又不是 \(i'.high<i.low\)，由三分律只能是 \(i.high<i'.low\)。树以低端点为键，右子树中任一区间 \(i''\) 都满足 \(i''.low\ge i'.low>i.high\)，因此也不重叠。

所以无论走哪边，不变式都保持；终止时子树为空，树中自然没有重叠区间。\(\square\)

直观地说：在每个结点上，搜索总是朝"安全"的方向走，因此只需检查一条从根出发的路径。

推导拆解：往右走的理由很直接，难点是往左走。往左走意味着放弃了右子树，凭什么右边一定没有？逻辑链如下。 (1) 已知 \(x.left.max\ge i.low\)，所以左子树里有某个区间 \(i'\)，它的结束时刻 \(\ge\) 查询的开始时刻——\(i'\) 没有"整个在查询左边"。 (2) 假设左子树里没有任何区间与查询重叠，那么 \(i'\) 也不重叠；它不在查询左边，由三分律只能在查询右边：\(i'.low>i.high\)，即 \(i'\) 开始得比查询结束还晚。 (3) 树按开始时刻排序，右子树里每个区间开始得都不比 \(i'\) 早，所以也都晚于查询结束，全部不重叠。结论："左边没有 ⟹ 右边也没有"，这就是逆否命题"右边有 ⟹ 左边有"。所以往左走不会错过答案。注意它只保证找到一个重叠区间，不保证找到全部。

扩展：习题 14.3-4 要求列出全部 \(k\) 个重叠区间，简单方法是反复查询并删除已找到的区间，时间 \(O(\min(n,k\lg n))\)；也可以不修改树，在遍历时用 \(max\) 剪枝（下文代码）。原书章末注记提到，对静态区间集合有能在 \(O(k+\lg n)\) 时间内枚举全部 \(k\) 个重叠区间的结构。

14.3.4 两道思考题

思考题 14-1 最大重叠点：一组区间中被最多区间覆盖的点。先证明总有一个最大重叠点是某个区间的端点；再设计动态结构：用红黑树存所有端点，左端点记 \(+1\)、右端点记 \(-1\)，每个结点扩张"子树值之和"与"子树内的最大前缀和（及其位置）"，即可在插入删除区间时维护最大重叠点。最大前缀和 \(= \max(\text{左.最大前缀},\ \text{左.和}+\text{自身},\ \text{左.和}+\text{自身}+\text{右.最大前缀})\)，只依赖孩子，满足定理 14.1。
思考题 14-2 Josephus 排列：\(n\) 人围圈、每数到第 \(m\) 人移出，例如 \((7,3)\)-Josephus 排列是 \(\langle3,6,2,7,5,1,4\rangle\)。\(m\) 为常数时用循环链表 \(O(n)\)；\(m\) 不是常数时用顺序统计树，每次删除秩为 \((r+m-1)\bmod(\text{剩余人数})\) 的元素，\(O(n\lg n)\)。

14.4 量化实战

14.4.1 订单簿深度、滚动排名与 Kendall τ

下面用一个扩张过的 treap 作基础结构（思考题 13-4；它与红黑树一样用旋转维持平衡，定理 14.1 的论证同样适用，而代码短得多）。每个结点存三个扩张字段：子树结点数 size、子树数量和 sum、子树金额和 pv（价格 × 数量）。它们都只依赖结点自身和两个孩子，旋转后只需重算两个结点。

三个用途：

订单簿深度查询。卖方以价格为键、挂单量为权重。"吃掉 \(Q\) 股穿透到哪一档"就是按 sum 做的 OS-SELECT：在每个结点比较"左子树累计量"与剩余需求，决定往左、停下还是往右；沿途累加 pv，就同时得到成交均价和相对最优价的滑点。每次查询 \(O(\lg n)\)，而排序加前缀和要 \(O(n)\)。
滚动百分位排名。窗口长度 \(w\) 内维护有序集合，每来一个新值插入、移出最旧值、查新值的秩，每步 \(O(\lg w)\)，比每步重新排序的 \(O(w\lg w)\) 快得多。用 (值, 时间) 作键，自然处理重复值。滚动中位数、滚动分位数（历史模拟 VaR）也都是 OS-SELECT。

推导拆解：用一个三档的小订单簿看 sweep 怎么走。卖一 10.01 挂 300 股，卖二 10.02 挂 500 股，卖三 10.03 挂 400 股；树的根是 10.02，左孩子 10.01，右孩子 10.03。根的扩张字段：sum = 1200，pv = \(10.01\times300+10.02\times500+10.03\times400=12025\)。市价买 \(Q=700\) 股：在根 10.02 处，左子树累计 300 < 700，说明不止吃左边；左边加上本档 \(300+500=800\ge700\)，说明停在本档。成交金额 = 左子树的 pv（3003）+ 本档吃掉的 \((700-300)\times10.02=4008\)，合计 7011，均价 \(7011/700=10.0157\)。全程只看了根和根的左孩子汇总值，没有逐档累加。这正是 OS-SELECT 的推广：OS-SELECT 按"个数"找第 \(i\) 个，sweep 按"股数"找第 \(Q\) 股所在的价位。

逆序对与 Kendall τ（习题 14.1-7）。按因子值排序后，看收益序列里有多少逆序对；每个元素的"前面比它大的个数"= 前面元素数 − 它在已插入集合中的秩。总时间 \(O(n\lg n)\)，无并列时 \(\tau=1-2\cdot\text{逆序对数}/\binom n2\)。Kendall \(\tau\) 是衡量因子排序能力（秩 IC）的稳健指标。

import numpy as np, pandas as pd, random
from scipy.stats import kendalltau

class N:
    __slots__ = ("key", "w", "pri", "l", "r", "size", "sum", "pv", "px")
    def __init__(self, key, w, px):
        self.key, self.w, self.pri = key, w, random.random()
        self.l = self.r = None
        self.px = px                          # 价格（订单簿用；其他用途取 0）
        self.size, self.sum, self.pv = 1, w, px * w   # 扩张属性：子树结点数、Σ数量、Σ价格×数量

def sz(x): return x.size if x else 0
def sm(x): return x.sum if x else 0
def pv(x): return x.pv if x else 0.0
def pull(x):                                  # 只依赖 x 与两个孩子 → 定理 14.1 适用
    x.size = sz(x.l) + sz(x.r) + 1
    x.sum = sm(x.l) + sm(x.r) + x.w
    x.pv = pv(x.l) + pv(x.r) + x.px * x.w
def rot_right(x):                             # 旋转后只有 x、y 两个结点需要重算
    y = x.l; x.l = y.r; y.r = x; pull(x); pull(y); return y
def rot_left(x):
    y = x.r; x.r = y.l; y.l = x; pull(x); pull(y); return y

class OSTree:
    """顺序统计树（以 treap 为基础结构，思考题 13-4），扩张 size、sum、pv。"""
    def __init__(self): self.root = None
    def insert(self, key, w=1.0, px=0.0):
        def ins(x):
            if x is None: return N(key, w, px)
            if key < x.key:
                x.l = ins(x.l)
                if x.l.pri < x.pri: x = rot_right(x)   # 恢复最小堆序
            else:
                x.r = ins(x.r)
                if x.r.pri < x.pri: x = rot_left(x)
            pull(x); return x
        self.root = ins(self.root)
    def delete(self, key):
        def de(x):
            if key < x.key: x.l = de(x.l)
            elif key > x.key: x.r = de(x.r)
            else:                                    # 找到：旋转到叶再摘除
                if x.l is None: return x.r
                if x.r is None: return x.l
                if x.l.pri < x.r.pri: x = rot_right(x); x.r = de(x.r)
                else: x = rot_left(x); x.l = de(x.l)
            pull(x); return x
        self.root = de(self.root)
    def select(self, i):                             # OS-SELECT：第 i 小（1 起）
        x = self.root
        while True:
            r = sz(x.l) + 1
            if i == r: return x.key
            if i < r: x = x.l
            else: i -= r; x = x.r
    def rank_lt(self, key):                          # 严格小于 key 的元素个数
        x, r = self.root, 0
        while x:
            if key <= x.key: x = x.l
            else: r += sz(x.l) + 1; x = x.r
        return r
    def sweep(self, q):                              # 累计权重首次 >= q 的结点（按 sum 下降，类比 OS-SELECT）
        x, acc, notional = self.root, 0.0, 0.0       # acc/notional：已确定在目标左侧的数量与金额
        while x:
            if acc + sm(x.l) >= q: x = x.l
            elif acc + sm(x.l) + x.w >= q:
                acc += sm(x.l); notional += pv(x.l)
                return x.key, (notional + (q - acc) * x.px) / q    # 穿透价位、成交均价
            else: acc += sm(x.l) + x.w; notional += pv(x.l) + x.px * x.w; x = x.r
        return None, None
    def __len__(self): return sz(self.root)

random.seed(0); rng = np.random.default_rng(0)

# ---------- 1. 卖方订单簿：吃掉 Q 股要穿透到哪个价位？ ----------
asks = OSTree()
book = {round(10.00 + 0.01 * i, 2): int(rng.integers(1, 50)) * 100 for i in range(1, 400)}
for px, qty in book.items(): asks.insert(px, qty, px)
best = asks.select(1)
for Q in [5_000, 50_000, 200_000]:
    px, vwap = asks.sweep(Q)
    lv = asks.rank_lt(px) + 1
    print(f"市价买 {Q:>7,} 股: 穿透到第 {lv:3d} 档 {px:.2f}，成交均价 {vwap:.4f}，"
          f"相对最优卖价滑点 {1e4 * (vwap / best - 1):5.1f} bp")
ks = sorted(book); cum = np.cumsum([book[k] for k in ks])   # 暴力对照：排序 + 前缀和
j = int(np.searchsorted(cum, 200_000)); print("暴力法第 200,000 股所在价位:", ks[j])
asks.delete(10.01); asks.delete(10.02)                 # 前两档被吃光
print("前两档删除后 最优卖价:", asks.select(1), " 第 5 档:", asks.select(5), " 档位数:", len(asks))

# ---------- 2. 滚动百分位排名：每步 O(lg w) ----------
x = rng.standard_t(4, size=3000); w = 250
t, pct = OSTree(), np.full(len(x), np.nan)
for i, v in enumerate(x):
    t.insert((v, i))
    if i >= w: t.delete((x[i - w], i - w))           # 用 (值, 时间) 作键，处理重复值
    if i >= w - 1:
        pct[i] = (t.rank_lt((v, i)) + 1) / w            # 当前值在窗口内的秩 / w
ref = pd.Series(x).rolling(w).rank().to_numpy() / w
print("\n滚动百分位排名 与 pandas rolling().rank() 最大差:", np.nanmax(np.abs(pct - ref)))
med = t.select(w // 2)[0]                               # 最后一个窗口的下中位数（w 为偶数）
print("最后窗口下中位数:", round(med, 6), " np.sort 对照:", round(np.sort(x[-w:])[w // 2 - 1], 6))

# ---------- 3. 逆序对计数 → Kendall τ（习题 14.1-7） ----------
n = 4000
f = rng.normal(size=n); y = 0.1 * f + rng.normal(size=n)     # 因子值与下期收益，弱相关
order = np.argsort(f, kind="stable"); ys = y[order]
t, inv = OSTree(), 0
for j, v in enumerate(ys):                         # 统计 j 之前比 v 大的元素个数
    inv += j - t.rank_lt(v)                        # 无重复值时 = 前面元素数 - 比 v 小的个数
    t.insert(v)
pairs = n * (n - 1) // 2
tau = 1 - 2 * inv / pairs                          # 无并列时 τ = (协调对 - 不协调对) / 总对数
print(f"\n逆序对 {inv:,} / 总对数 {pairs:,}  → Kendall τ = {tau:.6f}")
print(f"scipy.stats.kendalltau            = {kendalltau(f, y).statistic:.6f}")

运行输出：

市价买   5,000 股: 穿透到第   2 档 10.02，成交均价 10.0116，相对最优卖价滑点   1.6 bp
市价买  50,000 股: 穿透到第  20 档 10.20，成交均价 10.1111，相对最优卖价滑点 101.0 bp
市价买 200,000 股: 穿透到第  78 档 10.78，成交均价 10.4069，相对最优卖价滑点 396.5 bp
暴力法第 200,000 股所在价位: 10.78
前两档删除后 最优卖价: 10.03  第 5 档: 10.07  档位数: 397

滚动百分位排名 与 pandas rolling().rank() 最大差: 0.0
最后窗口下中位数: -0.023031  np.sort 对照: -0.023031

逆序对 3,688,851 / 总对数 7,998,000  → Kendall τ = 0.077557
scipy.stats.kendalltau            = 0.077557

读结果。 第一部分：模拟的卖方簿每档平均约 2500 股，所以 5 万股要穿透 20 档、成交均价比最优卖价高约 1%，20 万股高约 4%——这条"数量 → 均价"曲线就是订单簿隐含的冲击成本曲线，执行算法据此决定是否拆单（拆单的最优调度是下一章动态规划的主题）。树上的查询与"排序 + 前缀和 + 二分"的暴力结果一致。第二部分：增量算出的滚动百分位排名与 pandas 完全相同。第三部分：用逆序对算出的 Kendall \(\tau\) 与 scipy 一致到小数点后六位；这里因子与收益的真实相关很弱（约 0.1 的载荷），\(\tau\approx0.078\)，正是常见的"IC 不高但稳定"的量级。

实践提示。 在 Python 研究环境里，滚动排名直接用 pandas.Series.rolling().rank()、Kendall \(\tau\) 直接用 scipy.stats.kendalltau（内部也是 \(O(n\lg n)\) 的归并/树状结构）即可。手写扩张树的价值在实时系统：行情一笔一笔来时，订单簿深度、窗口分位数都要增量维护，不能每次全量重算。C++ 中 __gnu_pbds::tree 直接提供了顺序统计树。

14.4.2 在册订单的时间区间查询

第二个例子把一天的限价单看作区间 [提交时刻, 撤单或成交时刻]，用区间树回答"某个时间窗内哪些订单在册"。代码同时演示了 INTERVAL-SEARCH（找任一个）和用 max 剪枝的全量枚举，并用端点排序加前缀和求"同时在册订单数峰值"（思考题 14-1 的离线版本）。

import numpy as np, random
random.seed(1); rng = np.random.default_rng(1)

class INode:
    __slots__ = ("lo", "hi", "oid", "pri", "l", "r", "max")
    def __init__(self, lo, hi, oid):
        self.lo, self.hi, self.oid, self.pri = lo, hi, oid, random.random()
        self.l = self.r = None; self.max = hi
def mx(x): return x.max if x else -np.inf
def pull(x): x.max = max(x.hi, mx(x.l), mx(x.r))      # x.max = max(int.high, left.max, right.max)
def rot_r(x): y = x.l; x.l = y.r; y.r = x; pull(x); pull(y); return y
def rot_l(x): y = x.r; x.r = y.l; y.l = x; pull(x); pull(y); return y

class IntervalTree:
    """区间树：以低端点为键的 treap，扩张子树最大高端点 max。"""
    def __init__(self): self.root = None
    def insert(self, lo, hi, oid):
        def ins(x):
            if x is None: return INode(lo, hi, oid)
            if (lo, oid) < (x.lo, x.oid):
                x.l = ins(x.l)
                if x.l.pri < x.pri: x = rot_r(x)
            else:
                x.r = ins(x.r)
                if x.r.pri < x.pri: x = rot_l(x)
            pull(x); return x
        self.root = ins(self.root)
    def search(self, a, b):                       # INTERVAL-SEARCH：返回任一与 [a,b] 重叠的区间
        x = self.root
        while x and not (x.lo <= b and a <= x.hi):
            x = x.l if (x.l and x.l.max >= a) else x.r
        return x
    def all_overlaps(self, a, b):                 # 枚举全部重叠区间：剪掉不可能有解的子树
        out = []
        def go(x):
            if x is None or x.max < a: return     # 子树内所有高端点 < a → 无重叠
            go(x.l)
            if x.lo <= b:
                if a <= x.hi: out.append(x.oid)
                go(x.r)                            # 若 x.lo > b，右子树低端点更大，全部剪掉
        go(self.root); return out

# 模拟一天的限价单：提交时刻 lo，撤单或成交时刻 hi（秒），存续时间服从对数正态
n = 20000
lo = np.sort(rng.uniform(0, 14400, n))
hi = lo + rng.lognormal(mean=3.0, sigma=1.5, size=n)
T = IntervalTree()
for i in range(n): T.insert(lo[i], hi[i], i)

a, b = 7200.0, 7205.0                              # 查询：13:00:00–13:00:05 期间在册的订单
x = T.search(a, b)
print("任一重叠订单:", None if x is None else (x.oid, round(float(x.lo), 1), round(float(x.hi), 1)))
got = sorted(T.all_overlaps(a, b))
brute = sorted(np.where((lo <= b) & (a <= hi))[0].tolist())
print(f"[{a},{b}] 内在册订单数: {len(got)}  与暴力扫描一致: {got == brute}")

# 思考题 14-1 的离线版本：最大重叠点 = 同时在册订单数峰值（端点排序 + 前缀和）
ev = np.concatenate([np.c_[lo, np.ones(n)], np.c_[hi, -np.ones(n)]])
ev = ev[np.lexsort((-ev[:, 1], ev[:, 0]))]        # 同一时刻先 +1 后 −1（闭区间）
live = np.cumsum(ev[:, 1]); k = int(np.argmax(live))
print(f"同时在册订单峰值 {int(live[k])}，出现在 t={ev[k, 0]:.1f}s（是某个订单的左端点: {ev[k, 1] == 1}）")

运行输出：

任一重叠订单: (4992, 3557.4, 8014.6)
[7200.0,7205.0] 内在册订单数: 91  与暴力扫描一致: True
同时在册订单峰值 117，出现在 t=7991.8s（是某个订单的左端点: True）

INTERVAL-SEARCH 找到的第一个重叠订单是一笔挂了一个多小时的"老单"——它的低端点很早，但高端点很晚，这正是 max 字段让搜索能在左子树里找到它的原因。全量枚举的结果与暴力扫描一致。峰值出现在某个订单的左端点上，印证了思考题 14-1(a) 的结论。

这类查询在风控和回测审计中很常见：某一时刻的在册订单数与在途名义金额（风控限额要看峰值而非日终值）；某次异常行情期间有哪些自己的订单在册（事后分析成交质量）；事件窗口重叠检测（两个事件研究窗口是否相互污染）。若需要的是"峰值随订单增删动态更新"，就用思考题 14-1 的动态版本：在端点树上扩张"子树和"与"子树最大前缀和"。

本章小结

扩张数据结构的核心是选一个只依赖子树的附加属性，使它能在插入、删除和旋转中以 \(O(1)\) 或 \(O(\lg n)\) 代价维护（定理 14.1）。顺序统计树附加子树规模 size，OS-SELECT 自顶向下按左子树规模决定方向，OS-RANK 自底向上累加左侧结点数，都是 \(O(\lg n)\)。区间树以低端点为键、附加子树最大高端点 max，INTERVAL-SEARCH 依靠区间三分律只走一条路径。把 size 换成挂单量、金额，就能对订单簿做深度和冲击成本查询；把它用在滑动窗口上，就是增量的滚动排名与分位数。

结构	附加信息	维护公式	新操作（\(O(\lg n)\)）
顺序统计树	\(x.size\)	\(x.left.size+x.right.size+1\)	OS-SELECT、OS-RANK
订单簿深度树	子树挂单量、子树金额	左 + 右 + 自身	按累计量定位穿透价位、成交均价
区间树	\(x.max\)	\(\max(x.int.high,x.left.max,x.right.max)\)	INTERVAL-SEARCH
最大重叠点（思考题 14-1）	子树和、子树最大前缀和	只依赖孩子	FIND-POM

结论	内容
定理 14.1	只依赖 \(x\)、\(x.left\)、\(x.right\) 的属性可在插入删除中维护，保持 \(O(\lg n)\)
区间重叠条件	\(i.low\le i'.high\) 且 \(i'.low\le i.high\)
定理 14.2	INTERVAL-SEARCH 返回重叠区间，或正确地报告不存在
区间枚举	全部 \(k\) 个重叠区间 \(O(\min(n,k\lg n))\)

练习

基础

在原书图 14.1 上模拟 OS-SELECT(T.root, 10) 和对键 35 的 OS-RANK。（原书 14.1-1、14.1-2。）
写出非递归的 OS-SELECT，以及给定关键字（互异）求秩的递归过程 OS-KEY-RANK(T, k)。（原书 14.1-3、14.1-4。）
说明如何在 \(O(\lg n)\) 时间内求结点 \(x\) 的第 \(i\) 个后继。（原书 14.1-5。提示：先求秩 \(r\)，再 OS-SELECT(\(r+i\))。）
写出在区间树上旋转后 \(O(1)\) 更新 max 的 LEFT-ROTATE。（原书 14.3-1。）
黑高能否作为扩张属性在红黑树中维护？深度呢？为什么？（原书 14.2-2。）

进阶

用顺序统计树在 \(O(n\lg n)\) 内统计数组的逆序对数，并说明有并列值时 Kendall \(\tau_b\) 需要怎样修正。（原书 14.1-7 的延伸。）
设计一个结构维护数集 \(Q\)，支持插入、删除和 MIN-GAP（两个最近的数之差），所有操作 \(O(\lg n)\)。例：\(Q=\{1,5,9,15,18,22\}\) 时 MIN-GAP 为 3。（原书 14.3-6。提示：扩张子树的 min、max、min-gap。）在量化里它能回答什么问题？（例如：订单簿中两个相邻价位的最小价差。）
修改订单簿深度树，使它还能在 \(O(\lg n)\) 内回答"在价格 \(p\) 以内（含）一共有多少挂单量"。这个查询和 sweep 是什么关系？
思考题 14-1：实现动态的最大重叠点结构（端点树 + 子树和 + 子树最大前缀和），并用上面的模拟订单数据验证峰值 117。
思考题 14-2：用顺序统计树在 \(O(n\lg n)\) 内输出 \((n,m)\)-Josephus 排列，验证 \((7,3)\) 的结果为 \(\langle3,6,2,7,5,1,4\rangle\)。

原书推荐习题：14.1-5、14.1-7、14.2-3、14.3-4、14.3-6，思考题 14-1、14-2。

原书对照

本章小节	原书章节	PDF 页码
14.1 动态顺序统计	14.1 Dynamic order statistics	p.360–366
14.2 如何扩张数据结构	14.2 How to augment a data structure	p.366–369
14.3 区间树	14.3 Interval trees	p.369–376
14.3.4 思考题	Problems 14-1、14-2	p.374–376

第 14 章 数据结构的扩张

学习目标

读前导读

14.1 动态顺序统计

14.1.1 顺序统计树

14.1.2 查找给定秩的元素：OS-SELECT

14.1.3 求元素的秩：OS-RANK

14.1.4 维护 size

14.2 如何扩张一个数据结构

14.3 区间树

14.3.1 区间与区间三分律

14.3.2 按四步法设计区间树

14.3.3 正确性

14.3.4 两道思考题

14.4 量化实战

14.4.1 订单簿深度、滚动排名与 Kendall τ

14.4.2 在册订单的时间区间查询

本章小结

练习

原书对照

第 14 章数据结构的扩张