前缀转移
我们宣称形如 \(\displaystyle f_i=\min_{j=1}^{i-1}g_j+w(j,i)\) 的转移式是前缀转移。
若 \(\forall i_1<i_2\)，对于 \(i_1\) 的所有转移点 \(j_1\) 均存在一个 \(j_2\) 使得 \(j_2\) 是 \(i_2\) 的转移点且 \(j_2>j_1\)，那我们称这个 dp 式满足决策单调性。
分治法优化
若 \(g=f\)，我们称该种转移为自转移，否则为他转移。分治法优化只能在他转移是使用。
对于一个区间 \([l,r]\)，我们找到中点 \(mid\)，只需暴力计算所有 \([L,\min(mid-1,R)]\) 的贡献即可算出 \(f_{mid}\)，同时确定 \([l,mid-1],[mid+1,r]\) 的决策点选择区间。
注意到每层暴力扫描部分的总和为 \(n\)，而分治只有 \(\log n\) 轮，故复杂度为 \(O(n\log n)\)。