ContextQMD
Back to Oi Wiki

Decompose

docs/ds/decompose.md

latest5.5 KB
Original Source

author: Ir1d, HeRaNO, Xeonacid

简介

其实，分块是一种思想，而不是一种数据结构．

从 NOIP 到 NOI 到 IOI，各种难度的分块思想都有出现．

分块的基本思想是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度．

分块的时间复杂度主要取决于分块的块长，一般可以通过均值不等式求出某个问题下的最优块长，以及相应的时间复杂度．

分块是一种很灵活的思想，相较于树状数组和线段树，分块的优点是通用性更好，可以维护很多树状数组和线段树无法维护的信息．

当然，分块的缺点是渐近意义的复杂度，相较于线段树和树状数组不够好．

不过在大多数问题上，分块仍然是解决这些问题的一个不错选择．

下面是几个例子．

区间和

??? note "例题 LibreOJ 6280 数列分块入门 4" 给定一个长度为 $n$ 的序列 ${a_i}$，需要执行 $n$ 次操作．操作分为两种：

1.  给 $a_l \sim a_r$ 之间的所有数加上 $x$；
2.  求 $\sum_{i=l}^r a_i$．

    $1 \leq n \leq 5 \times 10^4$

我们将序列按每 $s$ 个元素一块进行分块，并记录每块的区间和 $b_i$．

$$ \underbrace{a_1, a_2, \ldots, a_s}{b_1}, \underbrace{a{s+1}, \ldots, a_{2s}}{b_2}, \dots, \underbrace{a{(s-1) \times s+1}, \dots, a_n}{b{\frac{n}{s}}} $$

最后一个块可能是不完整的（因为 $n$ 很可能不是 $s$ 的倍数），但是这对于我们的讨论来说并没有太大影响．

首先看查询操作：

  • 若 $l$ 和 $r$ 在同一个块内，直接暴力求和即可，因为块长为 $s$，因此最坏复杂度为 $O(s)$．
  • 若 $l$ 和 $r$ 不在同一个块内，则答案由三部分组成：以 $l$ 开头的不完整块，中间几个完整块，以 $r$ 结尾的不完整块．对于不完整的块，仍然采用上面暴力计算的方法，对于完整块，则直接利用已经求出的 $b_i$ 求和即可．这种情况下，最坏复杂度为 $O(\dfrac{n}{s}+s)$．

接下来是修改操作：

  • 若 $l$ 和 $r$ 在同一个块内，直接暴力修改即可，因为块长为 $s$，因此最坏复杂度为 $O(s)$．
  • 若 $l$ 和 $r$ 不在同一个块内，则需要修改三部分：以 $l$ 开头的不完整块，中间几个完整块，以 $r$ 结尾的不完整块．对于不完整的块，仍然是暴力修改每个元素的值（别忘了更新区间和 $b_i$），对于完整块，则直接修改 $b_i$ 即可．这种情况下，最坏复杂度和仍然为 $O(\dfrac{n}{s}+s)$．

利用均值不等式可知，当 $\dfrac{n}{s}=s$，即 $s=\sqrt n$ 时，单次操作的时间复杂度最优，为 $O(\sqrt n)$．

??? note "参考代码" cpp --8<-- "docs/ds/code/decompose/decompose_1.cpp"

区间和 2

上一个做法的复杂度是 $\Omega(1) , O(\sqrt{n})$．

我们在这里介绍一种 $O(\sqrt{n}) - O(1)$ 的算法．

为了 $O(1)$ 询问，我们可以维护各种前缀和．

然而在有修改的情况下，不方便维护，只能维护单个块内的前缀和．

以及整块作为一个单位的前缀和．

每次修改 $O(T+\frac{n}{T})$．

询问：涉及三部分，每部分都可以直接通过前缀和得到，时间复杂度 $O(1)$．

对询问分块

同样的问题，现在序列长度为 $n$，有 $m$ 个操作．

如果操作数量比较少，我们可以把操作记下来，在询问的时候加上这些操作的影响．

假设最多记录 $T$ 个操作，则修改 $O(1)$，询问 $O(T)$．

$T$ 个操作之后，重新计算前缀和，$O(n)$．

总复杂度：$O(mT+n\frac{m}{T})$．

$T=\sqrt{n}$ 时，总复杂度 $O(m \sqrt{n})$．

其他问题

分块思想也可以应用于其他整数相关问题：寻找零元素的数量、寻找第一个非零元素、计算满足某个性质的元素个数等等．

还有一些问题可以通过分块来解决，例如维护一组允许添加或删除数字的集合，检查一个数是否属于这个集合，以及查找第 $k$ 大的数．要解决这个问题，必须将数字按递增顺序存储，并分割成多个块，每个块中包含 $\sqrt{n}$ 个数字．每次添加或删除一个数字时，必须通过在相邻块的边界移动数字来重新分块．

一种很有名的离线算法 莫队算法，也是基于分块思想实现的．

练习题