四边形不等式复习笔记

本文介绍四边形不等式的来历以及应用。

说明：$\arg\min_i f(i)$表示最小化$f(i)$的$i$，如果有多个则取最大的那个$i$。

四边形不等式

四边形不等式（Quadrangle Inequality）是 Yao 在 1980 年于他的 论文 中定义的。

对于二元函数$f(i,j)$（$1\le i\le j\le n$），称其满足四边形不等式，当且仅当

$$\forall i\le i'\le j\le j', f(i,j)+f(i',j')\le f(i,j')+f(i',j)$$

简记为：交叉小于包含。

四边形不等式的命名

四边形不等式的命名，大概是因为 Yao 在其论文中的证明。在 Yao 论文的条件中，$f(i,i)=0$。则当$i'=j$时，上述等式退化为了

$$f(i,j) + f(j,j')\le f(i,j')$$

如果将$f(i,j)$理解为$i$到$j$的距离，那么上述等式就是反过来的三角不等关系（原本的三角不等关系是$a+b>c$）。

类似地，构造一个凸四边形，其顶点顺次标为$i,i',j,j'$。那么四边形不等式描述的就是：对角线长度和小于等于对边长度和，相当于把原本的几何关系反过来。

历史问题

四边形不等式最早似乎是在研究最优二叉搜索树问题过程中得到的。

最优二叉搜索树问题

最优二叉搜索树问题（Optimal binary search tree），也称带权平衡二叉树问题，指的是对于一些按特定分布的搜索操作，构造最小化（期望）搜索时间的二叉搜索树。

问题的形式化定义为：

给出一个升序数列$a_1,a_2,\ldots,a_n$，以及$2n+1$个概率，分别用$A_1,A_2,\ldots,A_n$以及$B_0,B_1,\cdots,B_n$表示，其中$\sum A_i + \sum B_i = 1$。

$A_i$表示，执行一个指向$a_i$的搜索的概率。$B_i$表示执行一个指向$a_i$和$a_{i+1}$之间的数的搜索的概率。特别地，$B_0$表示指向小于$a_1$的数，$B_n$表示指向大于$a_n$的数。

你需要构造一棵二叉树，使得期望搜索代价最小。

狭义地说，我们定义$\text{Search}(x)$表示一个搜索操作，其返回一个布尔值，判断$x$是否出现在序列$a$中。那么

• $A_i$就表示我们执行$\text{Search}(a_i)$的概率。
• $B_i$表示我们执行$\text{Search}(x)$，其中$a_i < x < a_{i+1}$的概率。

以上狭义的部分希望能帮助大家理解。

另外，我们可以将二叉树的一条边的遍历理解为单位 1 的代价。

就本问题而言，有两种分支

• 静态：指构建了二叉树后形态不能变化。
• 动态：形态可以发生变化。

就动态的问题而言，已经有太多的解决方案，且与四边形不等式不太相关。因此我们讨论的是静态问题的解决方案。

Knuth’s DP Algorithm

Knuth 主要发现了 SOBST 问题的最优子问题的性质，从而得到了一个$O(n^2)$的 DP 算法。

朴素算法

要最小化期望搜索代价，等价于最小化所有情况的搜索代价之和。而搜索的代价与二叉树的遍历路径长度有关。可以理解为，执行$\text{Search}(x)$的搜索代价是 BST 上它到根的路径长度乘上搜索它的概率。你可以理解为，$a_i$和$a_{i+1}$之间有一个元素$b_i$，代表所有$a_i$和$a_{i+1}$之间的数的集合。

设$f(i,j)$表示对$a_{i-1}$和$a_{j+1}$之间（不含端点）的数建立二叉搜索树的最小代价和。

另外，设$p(i,j)$表示，搜索操作指向$a_{i-1}$到$a_{j+1}$之间（不含端点）的概率。

首先，$f(i,i-1) = p(i,i-1) = B_{i-1}$。

对于$p(i,j)$（$1\le i\le j\le n$）而言：

$$p(i,j) = p(i,j-1)+ A_j + B_{j-1}$$

对于$f(i,j)$（$1\le i\le j\le n$）而言，转移时枚举分割点$k$，把两边的分为左右两棵子树：

$$f(i,j) = \min_{i\le k < j}\{ f(i,k)+f(k+1,j) \} + p(i,j)$$

该算法直接实现的复杂度是$O(n^3)$。但 Knuth 使用了一些优化来将 DP 的计算复杂度降至$O(n^2)$。

优化

设$\arg(i,j)$表示$\arg \min_k \{f(i,k)+f(k+1,j)\}$，也就是上述方程中的最优转移决策。那么有

$$\arg(i,j-1) \le \arg(i,j)\le \arg(i+1,j)$$

Knuth 在他的 论文 中对此有详细的证明，本文不做解释。从直观的角度，这是很容易理解的。$[i,j-1]$的区间相对于$[i,j]$要偏左一些，因此最优分割点更靠左一些。对$[i+1,j]$是有同样的道理。

有了这个推论，我们可以按照$|j-i|$从小到大的顺序进行 DP 转移，对于$|j-i|$相同的那些 DP 值，可以在$O(n)$的总时间内计算。因此总复杂度$O(n^2)$。

四边形不等式与矩阵

我们注意到四边形不等式是关于二元函数定义的，对此我们可以用矩阵模型描述。

单调矩阵（monotone matrix）：对于$n\times m$的矩阵$A$，若$\forall 1\le i < j\le n$，$\arg\min_k(A_i)\le \arg\min_k(A_j)$，即第$i$行最小值的位置在第$j$行最小值位置的左边，则称该矩阵为单调矩阵。

完全单调矩阵（totally monotone matrix）：若矩阵$A$的所有子矩阵均为单调矩阵，则称之为完全单调矩阵。子矩阵指抽出若干行若干列交叉位置上的元素形成的矩阵。

容易证明若$w$满足四边形不等式，则$w$对应的矩阵$W$以及其转置$W^T$都是完全单调矩阵。

单调矩阵反映了四边形不等式在矩阵上的体现。

四边形不等式优化 DP

在需要用到四边形不等式的性质优化的问题中，四边形不等式往往表现出次模性。这里的次模性指边际效益递减（不一定变小，而是指变劣）。

形式 I

对于满足四边形不等式的代价函数$w$，考虑以下形式的 DP：

$$f(i) = \min_{j < i} \{ f(j) + w_{j, i}\}$$

应用二分栈算法可以在$O(n\log n)$的时间内完成计算。

根据四边形不等式的性质，我们发现：对于两个决策点$j_1, j_2$（$j_1 < j_2$），如果$f(j_1) + w_{j_1, i} > f(j_2) + w_{j_2, i}$，则随$i$增加$j_1$不可能变优。

因此对于$j_1 < j_2$，$j_1$优于$j_2$只占一段时间。

于是我们可以二分出$j_1$劣于$j_2$的最早时刻$i$。

而且这个$i$是单调的。证明：考虑矩阵$A_{j, i} = f(j) + w_{j, i}$。这个矩阵满足四边形不等式。$i$在其中扮演一个分界点的角色。然后你可以反证法证明。它是单调的。

这样我们就只需要支持在序列末位插入/删除元素，在序列上二分。使用栈维护即可。

形式 II

$$f(i, j) = \min_{k < j} \{ f(i - 1, k) + w_{k, j}\}$$

Yao 的论文指出：在 Knuth 算法中，如果$w(i,j)$满足四边形不等式，那么$f(i,j)$也满足四边形不等式。

同时它也指出，如果$f(i,j)$满足四边形不等式，那么

$$\arg(i,j-1) \le \arg(i,j)\le \arg(i+1,j)$$

始终成立。

因此就可以使用决策单调性优化 DP。

应用：背包问题

你有$n$个物品，大小和权值分别为$w_i$和$v_i$。你有一个大小为$m$的背包，求放入背包的物品权值和的最大值。

$n\le 10^6, m\le 50000, w_i\le 300, v_i\le 10^9$。

考虑 DP。由于物品的大小较小，因此考虑分类。设$f(s, i)$表示考虑大小小于等于$s$的所有物品和大小为$i$的背包的最大价值和。设$V_{s, i}$表示选$i$个大小为$s$的物品的权值和的最大值，那么显然

$$f(s, i) = \max_j \{f(s - 1, i - sj) + V_{s, j}\}$$

类似多重背包的套路，我们将转移按模$s$的余数分类，那么可以将方程转化为类似

$$g_i = \max_j \{ h_j + w_{i , j} \}$$

的形式，其中$w_{i,j} = V_{s, j - i}$。

显然这是一个满足四边形不等式的 DP 方程，可以应用二分栈算法解决。