缺一分治
stripe_python · · 算法·理论
设代数结构
如果信息容易合并,则直接使用前后缀并即可。
:::::info[前后缀并]
预处理求前后缀信息并
那么
:::::
缺一分治主要用于加元素容易,但合并状态困难的情形。
:::::success[例子]{open}
- 最优化 01 背包加物品
O(V) ,合并是(\min,+) 卷积O(V^2) 。- 注:计数 01 背包可以
O(V) 退背包。
- 注:计数 01 背包可以
- 全源最短路加点
O(n^2) ,合并是(\min,+) 矩乘O(n^3) 。
:::::
对序列分治,设缺失区间
考虑下述算法流程:
- 加入
[l,m] 的元素,得到P'=a_1 \circ \cdots \circ a_m \circ a_{r+1} \circ \cdots \circ a_n ,递归(m,r] 。 - 撤销
[l,m] 元素的贡献得到P'=P 。 - 加入
(m,r] 的元素,得到P'=a_1 \circ \cdots \circ a_{l-1} \circ a_{m+1} \circ \cdots \circ a_n ,递归[l,m] 。
递归到分治树叶子