分块

什么是分块？

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

在信息学中，我们通常将分块定义为把一个长度为 $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)$，这与实际的操作方式、每个块维护的东西与块的划分有关。