线段树优化 DP

可分离转移的决策窗口任意时,用线段树维护 y(j,f(j)) 的区间最小值;若候选值随 i 区间加,则配合懒标记维护区间最值。

时间 O(n log n),空间 O(n) · 标签 动态规划 / 线段树 / 区间最值 / DP 优化

问题形式

考虑 1D/1D 动态规划中,当 𝑄𝑖,𝑗(𝑓(𝑗))=𝑥(𝑖)+𝑦(𝑗,𝑓(𝑗)) 时,方程退化为

𝑓(𝑖)=𝑥(𝑖)+min𝐿(𝑖)≤𝑗≤𝑅(𝑖)𝑦(𝑗,𝑓(𝑗)),

其中 𝐿(𝑖),𝑅(𝑖) 没有单调性要求,只要求 𝐿(𝑖)≤𝑅(𝑖)<𝑖。

此时 𝑓(𝑖) 需要查询一个任意区间内的最小值。把每个已经算出的 𝑗 的值 𝑦(𝑗,𝑓(𝑗)) 放在位置 𝑗,用线段树维护区间最小值,就能在 𝑂(log𝑛) 内回答一次转移。

线段树维护转移

线段树的叶子 𝑗 存 𝑦(𝑗,𝑓(𝑗))。还未计算或不应参与转移的位置初始化为 +∞。

按 𝑖 递增计算:

  • 查询区间 [𝐿(𝑖),𝑅(𝑖)] 的最小值。
  • 令 𝑓(𝑖)=𝑥(𝑖)+ 查询结果。
  • 把位置 𝑖 的值更新为 𝑦(𝑖,𝑓(𝑖)),供后面的状态使用。

线段树覆盖所有可能的位置;未插入的位置是 +∞,因此查询范围包含它们也不会改变最小值。

每个状态做一次区间查询和一次单点更新,总时间为 𝑂(𝑛log𝑛),空间为 𝑂(𝑛)。

正确性

不变式为:计算 𝑓(𝑖) 前,线段树中位置 𝑗 的值恰好是 𝑦(𝑗,𝑓(𝑗)),其中 𝑗<𝑖 且已计算;其余位置为 +∞。

由于 𝑅(𝑖)<𝑖,查询区间只包含已经计算的状态。区间最小值就是 min𝐿(𝑖)≤𝑗≤𝑅(𝑖)𝑦(𝑗,𝑓(𝑗)),再加上 𝑥(𝑖) 即得 𝑓(𝑖)。随后更新位置 𝑖,不变式对下一个状态成立。

区间加变体

有些 DP 的候选值会随着 𝑖 增加而整体变化。例如固定右端点扫描时,一个新加入的区间会对所有满足某个条件的左端点统一加上权值。此时线段树的叶子表示的是当前 𝑖 下的候选值,需要支持区间加和区间最值查询。

这类做法仍然是“线段树维护转移”,只是把单点更新换成了带懒标记的区间修改。扫描线的部分见 扫描模型。

易错点

  • 未计算的位置必须是 +∞(取最大值时是 −∞),否则空位置会污染查询。
  • 必须先算 𝑓(𝑖) 再把位置 𝑖 插入;若 𝑄𝑖,𝑗 依赖 𝑓(𝑖),提前插入会使用错误的值。
  • 𝑅(𝑖)≥𝑖 时转移可能引用当前状态或未来状态,已经不再是本页的无后效模型。
  • 区间加变体要在查询和继续修改前下传懒标记,否则叶子值不是当前候选值。
  • 区间加变体中,未激活的叶子若使用有限哨兵,加上权值后可能变成合法候选;需要单独标记未激活,或避免修改它们。
  • 若 𝑄𝑖,𝑗 含有 𝐴(𝑖)𝐵(𝑗) 这样的乘积项,单靠线段树存标量值不够,需要维护凸壳或改用斜率优化。
源码位置