单调直线下包络优化

形式陈述

许多转移虽然要在所有旧状态中取最小，却能写成

D[j]=g(j)+\min_{k<j}\{m_kx_j+b_k\}.

每个候选 $k$ 对应一条直线 $L_k(x)=m_kx+b_k$ ，系数与查询坐标都取自实数。问题变成动态插入直线，并查询指定横坐标处的最低值。这里的函数是仿射函数；算法习惯把它的图像简称为线。

Convex hull trick 是利用这些直线下包络加速求最小值的方法。本页讲双单调版本：直线按斜率非增顺序插入，查询横坐标按非降顺序到来。每条线的编号按插入次序增加，平局取最早插入者。

用一个双端队列保存仍可能成为最优候选的线。插入时从队尾删除无用线；查询时从队首删除以后不会再赢的线。相同斜率只保留截距较小者，截距也相同则保留较早编号。查询非空队列时返回最小值及其编号；空结构返回无候选，费用约定为 $+\infty$ 。

对三条严格递减斜率 $m_1>m_2>m_3$ ，中间线冗余的判定是

\frac{b_2-b_1}{m_1-m_2}\ge \frac{b_3-b_2}{m_2-m_3}.

分母为正，因此可以交叉相乘而不改变不等号方向。若斜率和截距为整数，下面就是整数精确判定；一般实数输入则仍需能精确比较相应乘积的表示：

(b_2-b_1)(m_2-m_3)\ge (b_3-b_2)(m_1-m_2).

直觉

斜率较大的线在左边更有优势，斜率较小的线在右边更有优势。两条不同斜率的线最多交一次，所以下包络的获胜线随 $x$ 增大按斜率递减的顺序交接。

中间线要真正赢得一个区间，必须先击败第一条线，过一段以后才被第三条线击败。如果它击败第一条的交点已经不早于被第三条击败的交点，就没有独占最优的区间。两个交点重合时，它至多在那个点打平，而第一条线编号更早，仍不需要保留中间线。这解释了冗余判定中的等号及其依赖的平局约定。

队尾反复删掉冗余中间线，直到交点严格递增，再加入新线。查询时比较队首两条线在当前 $x$ 的值：只有第二条严格更优时，才弹出第一条；以后查询更靠右，较低斜率的第二条优势不会逆转，弹出是永久安全的。若值相等，第一条编号更早，必须暂时保留。

三条线中 2x+5 没有最优区间被队尾删除，保留 4x 与 6；查询横坐标越过 1.5 后，队首从 4x 移到 6 — 删去无用线，再移动查询队首

例子与边界

一条从未获胜的线

依次插入 $L_0(x)=4x$ 、 $L_1(x)=2x+5$ 、 $L_2(x)=6$ 。前两条的交点是 $2.5$ ，后两条的交点是 $0.5$ 。中间线还没追上第一条，就已输给第三条，因此从队尾删除 $L_1$ 。剩下两条在 $x=1.5$ 交接。

按 $x=-2,0,2,4$ 查询，最小值依次为 $-8,0,6,6$ ，获胜编号为 $0,0,2,2$ 。前两个查询都保留队首 $L_0$ ；到 $x=2$ ， $L_2(2)=6<8=L_0(2)$ ，弹出 $L_0$ 。这次弹出依靠后续横坐标不会倒退。如果下一问突然回到 $x=0$ ，已经删掉的 $L_0$ 才是真正胜者，队列无法回答。

因此只有斜率单调、查询乱序时，应保留完整包络并对交接位置二分查询，而不是弹队首；斜率也乱序时，则可改用Li Chao 树等结构。两种单调性负责两个不同的删线动作。

从平方费用得到直线

对非负工作量的连续分段动态规划，展开

D_t[j]=\min_{k<j}\{D_{t-1}[k]+(S_j-S_k)^2\}

得到

D_t[j]=S_j^2+\min_{k<j}\{ (-2S_k)S_j+D_{t-1}[k]+S_k^2\}.

所以候选线的斜率 $m_k=-2S_k$ ，截距 $b_k=D_{t-1}[k]+S_k^2$ ，查询点 $x_j=S_j$ 。非负工作量让 $S_k$ 非降，恰好使插入斜率非增、查询点非降。计算每个 $j$ 前，先插入新合法候选 $k=j-1$ ，跳过上一层不可达的状态，再查询；不能提前插入所有 $k$ ，否则会允许未来切点影响当前状态。

示例第二层查询 $j=4$ 时， $S_4=6$ 。切点 $1,2$ 的前缀和同为 $2$ ，给出相同直线 $-4x+8$ ，保留编号 $1$ ；切点 $3$ 给出 $-10x+50$ 。在 $x=6$ ，前者为 $-16$ ，后者为 $-10$ ，加回 $S_4^2=36$ 得到费用 $20$ 、切点 $1$ 。相等斜率处理与 DP 最左切点约定完全一致。

交叉相乘也有数值边界

对整数系数，交叉相乘无需先把交点舍入为浮点数，但乘积可能超过输入整数的位宽。实现前应估计斜率差、截距差和乘积的最大位数，使用足够宽的整数或任意精度整数。本页核验脚本使用 Python 整数，不发生固定宽度溢出。若改用浮点容差，接近交点的平局和冗余判定就需要单独的误差分析。

推论与应用

每条线最多入队一次，从队尾或队首删除后不再回来，所以 $L$ 次插入与 $Q$ 次单调查询总共 $O(L+Q)$ 次队列操作和比较。这是摊还分析：某次插入可能删除许多条线，但每条被删线只支付一次。空间为 $O(L)$ ；若保存每一步整个队列用于图示，追踪日志可能额外占二次空间，不能算进同一个界。

在平方分段例中，每层至多插入、查询各 $n$ 次，所以 $K$ 层可做 $O(Kn)$ 次整数算术操作。上一层数值可用两行保存；完整回溯切点仍要另存。这里的线性是算术操作数，任意精度乘法的位成本还随整数大小增长。

几何上， $\min_k L_k(x)$ 是分段线性的凹函数，其获胜斜率非增；“convex hull trick”的名字来自与直线对偶凸壳的联系，并不意味着这条最小包络本身是凸函数。算法真正使用的是一次交叉与交接顺序，而不是一个含糊的“看起来凸”。

参考资料

UNSW COMP4128, Dynamic Programming II, 2021, “CHT Data Structure Construction”, “CHT Query Implementation”, “CHT Insert Implementation” and “Covered Walkway”, slides 16–46：官方讲义。按斜率维护包络、交点判断、单调查询与平方展开。
CP Initiative, USACO Guide, “Convex Hull Trick”：维护者教程。双单调条件和队列实现的教学实例。

形式陈述 ​

一条从未获胜的线 ​

从平方费用得到直线 ​

交叉相乘也有数值边界 ​

反向链接

形式陈述

一条从未获胜的线

从平方费用得到直线

交叉相乘也有数值边界