1. 四边形不等式

某个二分检索树的状态转移方程为：

可以使用四边形不等式来优化它

下面介绍四边形不等式和决策单调性，把时间复杂度降到 。如果一个函数 w 满足：

则说 w 满足凸四边形不等式（简称 w 为凸），如果函数 w 满足：

则说 w 关于区间包含关系单调。基于这两个定义，可以证明：

定理1 如果 w 同时满足四边形不等式和区间单调关系，则 d 也满足四边形不等式。
定理2 定理 1 条件满足时让 d[i,j] 取最小值的 k 为 K[i,j] ，则 。
定理3 w为凸当且仅当 。

可以利用上面的结论，在递推 i-j 递增的时候，保存 K 值。