根窗口 · O(n²)

Knuth 单调性：最优 BST 的根不回头

稀疏性：只算 match point 省的是格子：表里多数格子与答案无关，跳过不算。本页的载体换成最优二叉搜索树 (optimal BST)，格子一个也省不掉，能省的在每个格子内部：算一个区间的最优代价要在区间里挑根，朴素做法逐一试遍全部候选，而 Knuth 在 1971 年证明最优根的位置单调，每格的枚举窗口被两个已经算好的邻格夹住，全表试根总数从 $\Theta(n^3)$ 摊到 $O(n^2)$ 。

1 · 问题与朴素填表

给定按键序排好的 $n$ 个键与访问频率 $F[1..n]$ ，最优二叉搜索树是让总搜索代价 $\sum_k F[k]\cdot\operatorname{depth}(k)$ 最小的那棵二叉搜索树（根记深度 1）。二叉搜索树只有一条硬性约束：中序遍历等于键序。于是「谁当根」决定一切：选键 $r$ 作根，键 $i \dots r-1$ 只能进左子树、 $r+1 \dots j$ 只能进右子树，两侧各自又是同型的子问题。区间 DP 随之而来：

OptCost[i][j] = \min_{i \le r \le j}\bigl(OptCost[i][r-1] + OptCost[r+1][j]\bigr) + \sum_{k=i}^{j} F[k]

频率和一项与 $r$ 无关：无论谁当根，区间里每个键都因头上多出这个根而加深一层，整段频率整体加一次； $i > j$ 的空区间代价为 0。表有 $O(n^2)$ 个格子，每格枚举 $O(n)$ 个根，合计 $O(n^3)$ 。这个问题在次优查找树 · 静态带权查找的工程折中已经出现过一次，那里用 $O(n \log n)$ 的贪心绕开它、拿这套 DP 当最优对照；本页不绕，直接压 DP 本身的复杂度。

2 · 最优根的单调性

记 $OptRoot[i][j]$ 为子问题 $F[i..j]$ 的最优根，并列时取最左。Knuth 证明的性质是 [1]：把子数组的一端挪动一格，最优根只会朝同一方向移动，或原地不动。写成不等式：

OptRoot[i][j-1] \;\le\; OptRoot[i][j] \;\le\; OptRoot[i+1][j]

直觉顺着频率的重心走：右端多接一个键 $j$ ，新增的频率全部压在右侧，根被往右拉；左端割掉键 $i$ ，剩余部分的重心同样右移。等价的说法是 $OptRoot$ 上三角矩阵的每行、每列都非降。这条观察看着平平无奇，证明却不在直觉的深度上，Erickson 在书里特意标注 nontrivial；本页不复述证明，只交代脉络：Yao 在 1980 年把这类论证抽象成四边形不等式 (quadrangle inequality)，划出一整类可以照此加速的 DP [2]。

单调性在引擎里是被机器核对过的事实：checkRootMonotone 逐行逐列扫根表，预设与另外四组手工频率全部通过；另有 20 组随机频率核对朴素与窗口化的代价一致（见 core/engines.test.ts）。

3 · 窗口化枚举与望远镜求和

单调性直接改写算法。按区间长度 $d$ 从小到大填表，轮到 $OptCost[i][j]$ 时， $OptRoot[i][j-1]$ 与 $OptRoot[i+1][j]$ 都已在更短的区间里算好，根只需在窗口 $[OptRoot[i][j-1],\, OptRoot[i+1][j]]$ 里枚举，书中的 ComputeCostAndRoot 写的就是这个循环。

省多少要靠摊还看。固定 $d$ ，沿对角线让 $i$ 从 1 走到 $n-d$ ：第 $i$ 格窗口的上端是 $OptRoot[i+1][i+d]$ ，而第 $i+1$ 格（它的 $j-1$ 恰是 $i+d$ ）窗口的下端也是 $OptRoot[i+1][i+d]$ ——相邻窗口首尾相接，共享一个端点。整条对角线的窗口宽度之和于是望远镜式 (telescoping) 地消去中间项，只剩两端之差加格数，不超过 $n + (n-d)$ ；用 Erickson 的话说，最外层的每一轮里 $r$ 单调地从 1 走到 $n$ 。每条对角线 $O(n)$ ， $n$ 条合计 $O(n^2)$ 。

警示 · 伪码假设数组两侧无限延伸。书中 ComputeCostAndRoot 的循环是 for r ← OptRoot[i][j−1] to OptRoot[i+1][j]，配套初始化 OptRoot[i][i−1] ← i。照抄实现， $d = 0$ 的一圈就会读到 $OptRoot[i+1][i] = i + 1$ ，让 $r$ 越出合法根区间 $[i, j]$ 一格；数组按合法尺寸开时，cost[r + 1][j] 的行号在 $i = n$ 处达到 $n + 2$ ，引擎首版正是在此读出 undefined。修法是把窗口夹回 $[i, j]$ ，两界与合法区间的交必含最优根，core/obst.ts 里 lo / hi 旁的注释记着这处。

4 · 实测账本

预设频率 $F = [4, 2, 6, 3, 1, 5, 7, 2]$ 、 $n = 8$ 时最优代价 70。朴素枚举在长度 $d$ 的对角线上每格试 $d+1$ 个根，合计 $\sum_{d=0}^{7}(8-d)(d+1) = 120$ 次；窗口化枚举 66 次，两版填出的代价表与根表逐位一致。逐对角线的账本：

试根数	$d=0$	${1}$	${2}$	${3}$	${4}$	${5}$	${6}$	${7}$	合计
朴素 $[i, j]$	8	14	18	20	20	18	14	8	120
Knuth 窗口	8	14	12	9	8	6	5	4	66

头两条对角线分文不省： $d \le 1$ 时窗口与合法区间重合。省额从 $d = 2$ 起步，区间越长省得越多， $d = 7$ 那格（整段问题）只试了 $[3, 6]$ 四个根。总账 66 对 120 只有 1.8 倍，远没有 $n^3$ 对 $n^2$ 听上去悬殊，因为 $n = 8$ 太小；但「每条对角线合计 $O(n)$ 」的形状在这张小表上已经成立——窗口行不随 $d$ 二次增长，朴素行的 $(8-d)(d+1)$ 则在中段隆起。

根表还给出一个与加速无关、只有盯着它才会注意的读数：整段问题的最优根是 6 号键（频率 5），不是频率最高的 7 号键（频率 7）。最优根平衡的是两侧的频率总量：6 号作根把总量 30 切成 16 与 9，7 号作根切成 21 与 2，后者把几乎全部重量压进左子树，换来的深度增量抵掉了根上那点频率优势。

图 4-1 · 最优 BST 填表的根枚举窗口。上三角每格上为

OptCost

、下为该格最优根，红框是正在计算的格，蓝框是给出窗口两端的邻格；键条高亮当前窗口内的候选根，深色为选中的最优根；末尾的最优树由根表回溯而来，横坐标即键序。可拖动各键频率、在朴素与 Knuth 窗口两种枚举间切换，对照读数行里两版的试根总数（填表次序相同，仅窗口不同）。

5 · 行最小值视角

固定 $d$ 的一轮里定义矩阵 $M[i][r] = OptCost[i][r-1] + OptCost[r+1][i+d]$ ， $r$ 不合法处记 $\infty$ ：每次 ComputeCostAndRoot 做的事，就是在 $M$ 的第 $i$ 行里找最小值；Knuth 单调性说的则是行最小值的位置随行号非降。一个关于二叉搜索树的技巧至此变成一个关于矩阵的问题：哪类矩阵能不逐行扫描就找出全部行最小值。行最小值：Monge 与 SMAWK 把「非降」加强为 totally monotone，用 $O(m+n)$ 的功夫找出全部行最小值，落地：SMAWK 加速一维分段 DP 再把这台机器接回一维分段 DP。

6 · 参考文献

Knuth, D. E. (1971). Optimum binary search trees. Acta Informatica, 1(1), 14–25.
Yao, F. F. (1980). Efficient dynamic programming using quadrangle inequalities. Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC '80), 429–435.