何为分块#

分块，正如其名，将一个整区间分为若干小区间进行操作。分块拥有比线段树更强的泛用性，但是时间复杂度略输一筹；分块代码更加直观、减少理解难度，但是时间复杂度稍逊风骚；分块的代码比线段树更短，但是时间复杂度惜败后者……线段树所上下传递的操作计算必须满足结合律，区间平均数、方差还行，像计算区间众数、中位数这样的问题，线段树就只能被薄纱了……

考虑到树状数组理解难度较大、较难调试，一般都选用泛用性强、码量折中、效率及格、调试简便的分块算法求解。

如何分块#

不同于线段树的二分存储，分块所使用的块状数组本质上只是一个带有块起始下标和块末尾下标的普通数组，就像在一列数中间插上分割线分出区块。对于区间修改操作，只需要进行以下几步就可以：

1. 判断左端点l和右端点r所在的区块
2. 若两个端点在同一个区块内：暴力循环更新值
3. 若两个端点不在同一个区块内：在l所在区块内，从l开始循环至该区块结束，暴力更新值，相应的从r开始，往回循环至该区块起始处，暴力更新值，最后将二者中间整块的区块打上更新标记

我们会发现，分块其实就是将完全暴力的操作拆分成部分暴力的操作和部分取巧的操作。尽管看起来还是在使用暴力算法，但实际上优化了不少东西，而优化的效率还得取决于每个区块的长度。那么我们如何选择区块的长度呢？

最坏情况下，指定的左右端点就是整个数组的左右端点。假设总长度为$n$，一般采取的区块长度是$\sqrt n$。这样一来，就有$\sqrt n-2$个整区块会被打上标记，而两头的区块（长度都为$\sqrt n$）暴力修改的复杂度是$\mathcal O(2\sqrt n)=\mathcal O(\sqrt n)$。这也就意味着分块是一种根号算法（时间复杂度是根号级别的算法），尽管它在时间复杂度上比不过线段树的$\log n$。但是只要满足$n\leq10^{18}$或者$m\sqrt n\leq10^9$（$m$为询问个数），基本上就不会TLE（1s）。

既然已经知道了$\sqrt n$的来历，我们对数组进行分块时就简单了。首先循环$\sqrt n$次用以记录区块的起点和终点，但是注意如果数组长度不为完全平方数就需要将最后一个区块（编号为$\sqrt n$的区块）的终点下标设为$n$以免访问越界。开两个长度略大于$\sqrt n$的数组st和ed分别记录每个区块的起点下标和终点下标；加上一个查询数组bel，用于查找第$i$个数所属的区块编号；同时为了避免后期访问到最后一个区块时出现下标越界RE的情况，再开一个长度$\sqrt n$的数组记录每个区块长度（也可以只开一个变量存，特判是否是最后一个区块即可）。接下来就可以循环遍历整个数组了：

这是求解区间和的一段代码，init()函数中，我们把每个区块的和存在sum对应下标处

1
#include <bits/stdc++.h>
2
#define N 1000010
3
#define SQN 1010
4
typedef long long ll;
5

6
int st[SQN], ed[SQN], size[SQN], bel[SQN];
7
ll a[N], tag[N], sum[N];
8

9
void init() {
10
    int sq = (int) sqrt(n);
11
    for (int i = 1; i <= sq; i++) {
12
        st[i] = sq * (i - 1) + 1;
13
        ed[i] = sq * i;
14
        size[i] = ed[i] - st[i] + 1;
15
    }
16
    ed[sq] = n;
17
    size[sq] = ed[sq] - st[sq] + 1;
18
    for (int i = 1; i <= sq; i++) {
19
        for (int j = st[i]; j <= ed[i]; j++) {
20
            bel[j] = i;
21
            sum[i] += a[j];
22
        }
23
    }
24
}

按照如上所述的修改原理：

1
void update(int l, int r, int x) {
2
    if (bel[l] == bel[r]) {
3
        for (int i = l; i <= r; i++) a[i] += x, sum[bel[i]] += x;
4
    } else {
5
        for (int i = l; i <= ed[bel[l]]; i++) a[i] += x, sum[bel[l]] += x;
6
        for (int i = st[bel[r]]; i <= r; i++) a[i] += x, sum[bel[r]] += x;
7
        for (int i = bel[l] + 1; i < bel[r]; i++) tag[i] += x;
8
    }
9
}

询问区间和的原理比较相似，同样是分l和r所在区块进行讨论。只是当进行整体区块操作时，用与线段树相似的方法——将标记乘到总和中并累加即可。

1
ll askSum(int l, int r) {
2
    ll res = 0;
3
    if (bel[l] == bel[r]) {
4
        for (int i = l; i <= r; i++) res += (a[i] + tag[bel[l]]);
5
    } else {
6
        for (int i = l; i <= ed[bel[l]]; i++) res += (a[i] + tag[bel[l]]);
7
        for (int i = st[bel[r]]; i <= r; i++) res += (a[i] + tag[bel[r]]);
8
        for (int i = bel[l] + 1; i < bel[r]; i++) res += (size[i] * tag[i] + sum[i]);
9
    }
10
    return res;
11
}

以上求区间和的代码可以提交到洛谷 P3372 线段树模板 一里。与线段树相比，分块的速度慢了大约40ms，在300ms左右，还是可以接受的。