线段树优化 DP
可分离转移的决策窗口任意时,用线段树维护 y(j,f(j)) 的区间最小值;若候选值随 i 区间加,则配合懒标记维护区间最值。时间 O(n log n),空间 O(n) · 标签 动态规划 / 线段树 / 区间最值 / DP 优化
问题形式
考虑 1D/1D 动态规划中,当 时,方程退化为
其中 没有单调性要求,只要求 。
此时 需要查询一个任意区间内的最小值。把每个已经算出的 的值 放在位置 ,用线段树维护区间最小值,就能在 内回答一次转移。
线段树维护转移
线段树的叶子 存 。还未计算或不应参与转移的位置初始化为 。
按 递增计算:
- 查询区间 的最小值。
- 令 查询结果。
- 把位置 的值更新为 ,供后面的状态使用。
线段树覆盖所有可能的位置;未插入的位置是 ,因此查询范围包含它们也不会改变最小值。
每个状态做一次区间查询和一次单点更新,总时间为 ,空间为 。
正确性
不变式为:计算 前,线段树中位置 的值恰好是 ,其中 且已计算;其余位置为 。
由于 ,查询区间只包含已经计算的状态。区间最小值就是 ,再加上 即得 。随后更新位置 ,不变式对下一个状态成立。
区间加变体
有些 DP 的候选值会随着 增加而整体变化。例如固定右端点扫描时,一个新加入的区间会对所有满足某个条件的左端点统一加上权值。此时线段树的叶子表示的是当前 下的候选值,需要支持区间加和区间最值查询。
这类做法仍然是“线段树维护转移”,只是把单点更新换成了带懒标记的区间修改。扫描线的部分见 扫描模型。
易错点
- 未计算的位置必须是 (取最大值时是 ),否则空位置会污染查询。
- 必须先算 再把位置 插入;若 依赖 ,提前插入会使用错误的值。
- 时转移可能引用当前状态或未来状态,已经不再是本页的无后效模型。
- 区间加变体要在查询和继续修改前下传懒标记,否则叶子值不是当前候选值。
- 区间加变体中,未激活的叶子若使用有限哨兵,加上权值后可能变成合法候选;需要单独标记未激活,或避免修改它们。
- 若 含有 这样的乘积项,单靠线段树存标量值不够,需要维护凸壳或改用斜率优化。