缺一分治

· · 算法·理论

设代数结构 (S,\circ) 是交换半群。给定 a_1,a_2,\cdots,a_n \in S,对每个 i 求出

b_i=a_1 \circ \cdots \circ a_{i-1} \circ a_{i+1} \circ \cdots \circ a_n

如果信息容易合并,则直接使用前后缀并即可。

:::::info[前后缀并]

预处理求前后缀信息并

\begin{aligned} \text{pre}_i&=a_1 \circ a_2 \circ \cdots a_i\\ \text{suf}_i&=a_i \circ a_{i+1} \circ \cdots a_n \end{aligned}

那么 b_i=\text{pre}_{i-1} \circ \text{suf}_{i+1}。

:::::

缺一分治主要用于加元素容易,但合并状态困难的情形。

:::::success[例子]{open}

:::::

对序列分治,设缺失区间 [l,r] 中点 m。维护外部信息并

\begin{aligned} P&=a_1\circ \cdots \circ a_{l-1} \circ a_{r+1} \circ \cdots \circ a_n \end{aligned}

考虑下述算法流程:

递归到分治树叶子 l=r 时,恰有 b_i=P。复杂度 O(nk \log n),其中 k 是半群加点 & 撤销的复杂度。