分块

· · 算法·理论

什么是分块？

分块，顾名思义，就是把数组分成很多块，对于每次寻问，对每块单独进行求解，再求出散块，最终的答案就是每块的答案的并。

在信息学中，我们通常将分块定义为把一个长度为 n 的序列分成若干块，然后对于每次在序列上的操作 ( 一般是区间的修改和查询)，我们们分别在操作设计的那些块上进行即可。 简单的来说，分块其实就是一种暴力的优化。

分块优势

分块思想在一些情况中有着较好的应用。当出现下列情况时，将一个问题分解为若干个规模较小的子问题，也就是进行分块，会是较优的策略：

  1. 如果子问题的规模很小，可以设计关于子问题规模的复杂度较高的算法；
  2. 如果子问题的数目很少，可以对每类子问题使用复杂度与整个问题规模有关的算法；
  3. 如果每个子问题内部的元素具有共同的性质，可以使用针对性的算法。

如何分块？

我们可以把整个数列数列分为每块长度为 S 的若干块，以便于之后的使用。从第一个元素开始，每连续的 S 个元素组成一个块。若剩余的元素不足 S 个，令它们组成一个块。

例子：序列元素数目 N=7，块的大小 S=3。显然，此时的分块情况是 3、3、1，虽然最后一个块中数字个数不足 S，但是当 S=3 时，这就是我们分块的方式。

分割时，如果分的块数过多，虽然散块会较短，但会导致合并答案的时候速度太慢，如果分的快过少，虽然分得块数较少，但是每块过长，同时头尾的散块也会过长，降低效率，所以说，如何分块，每块长度 S 为多少，是一个需要考究的问题。

设 N 为序列的元素数目，S 为块的大小，那么可以保证：

  1. 块的数目不超过 N/S+1。
  2. 对于任意区间 [L,R], 可以分解成若干个完整的块以及剩余的不超过 2S 个元素。

修改与查询

分好块之后，如果我们能在块的层次上概括块内元素的信息，并且可以快速将不同部分的信息合并，就能够快速地得到任意区间的信息，也就是询问了。

对于每次询问 [L,R]，由于我们无法保证端点与分出的块的端点重合，所以要分为整块和散块分别处理。

在上图中，对于 [L,R] 这个询问，我们不难发现其中有两个整块，两端还有两个散块，那么，对于整个区间 [L,R] 的询问，我们可以将取用两个块内现成的结果与两个散块算出的答案的并。

对于修改操作，我们也可以使用上述方法，散块单独修改，整块进行统一修改即可。

时间复杂度分析

将序列分块，令每块的大小为 \sqrt n。考虑一个例题，在块的层次上维护每个块的所有元素的和。

首先，预处理的复杂度为 O(n) 。
对于询问操作，只需计算出询问区间对应的完整的块与多余的元素的和，时间复杂度为 O(\sqrt n)。
对于修改操作，也是 O(\sqrt n)。
对于 q 次修改和查询，总的时间复杂度为 O(q\times\sqrt n)。

但是，不是所有的分块时间复杂度都是 O(\sqrt n)，这与实际的操作方式、每个块维护的东西与块的划分有关。