分块是一种思维简单，代码简洁易懂的算法，虽然时间复杂度 $O(q \times \sqrt[2]{n})$ 相对于线段树的 $O(q \times \log{n})$ 要慢很多，但是它的算法兼容性和思维、代码难度确实远优于线段树。
算法过程
分块和线段树一样一般用于解决区间查询和修改操作的问题。
我们考虑将整个序列分为 $\sqrt{n}$ 个块（有可能数量上有点出入，但是不重要），除了最后一个块，其它块的大小都是 $\sqrt{n}$。
对于每一个块，储存这个块内所有元素的信息，这样如果操作的区间覆盖整个块，可以直接调用这个块的信息而非每个元素的信息，因为总的块的个数在 $\sqrt{n}$ 左右，所以每次操作时间复杂度是 $\sqrt{n}$ 的。
以经典的区间加减，区间求和为例。
变量定义
我们需要定义 $l,r$ 表示这个块包含了原序列的哪段区间，用 $sum$ 表示它们的和，然后再像线段树一样定义一个 $tag$ 进行懒惰标记。
大概这样就行了：
class block {
public:
int l, r, sum, tag;
};
然后需要再定义一个 $blg$ 数组储存每一个元素属于哪一个块。
初始化
首先，我们在读取原数组 $a$ 的同时计算每个元素所属的块以及那个块的总和，$sqr$ 表示块的大小，这里我们用 $blk$ 数组储存每个块的信息。
// 从 1 开始为块编号，a[1] 到 a[sqr] 属于第一个块，a[sqr + 1] 到 a[2 * sqr] 属于第二个块，以此类推。
for (int i = 1; i <= n; ++i) {
cin >> a[i], blg[i] = (i - 1) / sqr + 1;
blk[blg[i]].sum += a[i];
}
然后对每个块的左右端点（也就是包含原数组的哪一块区间）进行初始化。
for (int i = 1; i <= blg[n]; ++i) {
blk[i].l = blk[i - 1].r + 1;
blk[i].r = min(i * sqr, n);
}
然后就没有了。
区间加法
对于一个操作的区间 $[l,r]$，其中的部分元素所在的块不一定都在 $[l,r]$ 之间，比如说操作区间是 $[2,5]$，但是 $2$ 所在的块包含的区间是 $[1,3]$，但是元素 $1$ 不在 $[l,r]$ 之间，这时怎么办呢？
因为每个块的大小最多为 $\sqrt{n}$，这一部分直接暴力修改就行啦。
然后对于包含在区间内的整块，肯定是不可能一个一个修改它所包含的元素的，那就要考虑使用 懒惰标记 了。
分块懒惰标记的意思是暂时先不对块包含的元素进行修改，只在需要调用这些元素时统一进行修改。
那就很好写了，单独处理区间边缘那些残缺的块，中间的整块进行懒惰标记。
推荐在处理修改操作时第一时间修改块的信息，即使要进行懒惰标记，也要同时修改这个块的 $sum$ 值。（但是这并非必须，只是推荐）
那么我们在修改时考虑将整个区间分为三部分：
- 第一部分：
l到blk[blg[l]].r - 第二部分：
blk[blg[l] + 1].l到blk[blg[r] - 1].r - 第三部分：
blk[blg[r]].l到r
第一部分和第三部分单独修改，中间部分进行懒惰标记。
特别的，如果 $l$ 和 $r$ 属于同一个块，上述方法不生效，所以直接枚举区间元素进行修改即可。
void add(int l, int r, int x) {
// l,r 属于同一个区间需要特判
if (blg[l] == blg[r]) {
for (int i = l; i <= r; ++i)
// 不要忘记修改所在区间的值
a[i] += x, blk[blg[i]].sum += x;
} else {
// 第一部分
for (int i = l; i <= blk[blg[l]].r; ++i)
a[i] += x, blk[blg[i]].sum += x;
// 第二部分
for (int i = blg[l] + 1; i < blg[r]; ++i) {
blk[i].sum += x * (blk[i].r - blk[i].l + 1);
// tag 就是懒惰标记，表示这个块内的每一个元素需要增加的量
blk[i].tag += x;
}
// 第三部分
for (int i = blk[blg[r]].l; i <= r; ++i)
a[i] += x, blk[blg[i]].sum += x;
}
}
区间求和
和区间修改一样，求和也要将区间分为三个部分，也要特判 blg[l] == blg[r] 的情况。
直接加即可，但是此时，因为可能需要调用原数组的值，所以这里就需要进行 pushdown 操作，也就是对懒惰标记进行下放操作。
所以考虑在 block 类中添加 pushdown 函数：
class block {
public:
int l, r, sum, tag;
void pushdown() {
// 如果不需要进行加减操作，跳过
if (!tag) return;
// 枚举块的每一个元素
for (int i = l; i <= r; ++i)
a[i] += tag;
// 将 tag 设置为完成
tag = 0;
}
};
因为只有 blg[l] 和 blg[r] 两个块需要调取原数组，所以也只需要对这两个块进行 pushdown 操作。
然后加法操作就没什么好将的了。
int sum(int l, int r) {
int ans = 0;
// 下放懒惰标记
blk[blg[l]].pushdown(), blk[blg[r]].pushdown();
if (blg[l] == blg[r]) {
for (int i = l; i <= r; ++i)
ans += a[i];
} else {
for (int i = l; i <= blk[blg[l]].r; ++i)
ans += a[i];
for (int i = blg[l] + 1; i < blg[r]; ++i)
ans += blk[i].sum;
for (int i = blk[blg[r]].l; i <= r; ++i)
ans += a[i];
}
return ans;
}
完整代码
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1e5 + 5;
int n, m, sqr, a[MAXN], blg[MAXN];
class block {
public:
int l, r, sum, tag;
void pushdown() {
if (!tag) return;
for (int i = l; i <= r; ++i)
a[i] += tag;
tag = 0;
}
} blk[1000];
void add(int l, int r, int x) {
if (blg[l] == blg[r]) {
for (int i = l; i <= r; ++i)
a[i] += x, blk[blg[i]].sum += x;
} else {
for (int i = l; i <= blk[blg[l]].r; ++i)
a[i] += x, blk[blg[i]].sum += x;
for (int i = blg[l] + 1; i < blg[r]; ++i) {
blk[i].sum += x * (blk[i].r - blk[i].l + 1);
blk[i].tag += x;
}
for (int i = blk[blg[r]].l; i <= r; ++i)
a[i] += x, blk[blg[i]].sum += x;
}
}
int sum(int l, int r) {
int ans = 0;
blk[blg[l]].pushdown(), blk[blg[r]].pushdown();
if (blg[l] == blg[r]) {
for (int i = l; i <= r; ++i)
ans += a[i];
} else {
for (int i = l; i <= blk[blg[l]].r; ++i)
ans += a[i];
for (int i = blg[l] + 1; i < blg[r]; ++i)
ans += blk[i].sum;
for (int i = blk[blg[r]].l; i <= r; ++i)
ans += a[i];
}
return ans;
}
int main() {
cin >> n >> m, sqr = sqrt(n);
for (int i = 1; i <= n; ++i) {
cin >> a[i], blg[i] = (i - 1) / sqr + 1;
blk[blg[i]].sum += a[i];
}
for (int i = 1; i <= blg[n]; ++i) {
blk[i].l = blk[i - 1].r + 1;
blk[i].r = min(i * sqr, n);
}
while (m--) {
int op, l, r, x;
cin >> op >> l >> r;
if (op == 1)
cin >> x, add(l, r, x);
else
cout << sum(l, r) << '\n';
}
return 0;
}
此时你兴致冲冲提交了 【模板】线段树 1，然后发现得分 15pts。
原来是没开 long long。
说些什么吧！