不知道你有没有过这种经历：拿到一道题，明明暴力解法想得很顺，代码也就二十来行，交上去却总是超时。你反复优化循环、改输入输出，折腾半天还是卡在性能上。后来看了别人题解，发现他只是在开头多写了一小段预处理，把一堆“每次都要重新算”的东西提前存好，查询就变成了 O(1)。这个预处理技巧，八成就是前缀和；和它经常一起出现的，还有能高效处理“区间加值”的差分。这两个东西在信奥和算法题里几乎属于“保命技能”，c++ 选手绕不开的那种。
这篇文章就专门讲前缀和与差分。我会从一维到二维，从静态数组到树状数组，把公式怎么推、代码怎么写、边界怎么防坑都拆开讲。适合刚接触算法的初学者，也适合刷题刷到瓶颈、想系统梳理一下的读者。顺便先提醒一句：你要是去搜索引擎里搜“差分”，大概率先看到一堆“差分放大器”“差分信号线”之类电子学内容，跟算法里的差分完全是两码事——别搞混了。
1. 前缀和：从“暴力求和”到“O(1)查询”的思维跃迁
1.1 一维前缀和的定义与构造
先看最简单的情况。假设你有一个长度为 n 的数组 a，下标从 1 开始。前缀和数组 S 的定义是：
S[i] = a[1] + a[2] + ... + a[i]
也就是“数组前 i 个元素的和”。这个定义本身就是递推的：要求 S[i]，你不需要重新加一遍前面所有数，只需要用 S[i-1] 加上 a[i] 就行。
S[i] = S[i-1] + a[i]
预处理阶段从头到尾扫一遍数组，O(n) 就能把 S 算出来。之后你想知道任意一个区间 [l, r] 的和，不需要再遍历，直接用下面的公式：
sum(a[l..r]) = S[r] - S[l-1]
很多人第一次看到这个公式会愣一下：为什么减的是 S[l-1] 而不是 S[l]？因为 S[r] 包含的是前 r 个元素之和，里面已经把前 l-1 个元素算进去了，要单独留下 [l, r] 这一段，自然要把前面的部分减掉。如果你下标从 1 开始，那 S[0] 定义为 0，这样当 l=1 时，S[l-1] 就是 S[0]=0，公式依然成立。这是从 1 开始编号最大的好处：不用为区间左端点是 1 的情况单独写 if。
在 c++ 里实现起来非常简单：
#include <bits/stdc++.h> using namespace std; int main() { int n, q; cin >> n >> q; vector<long long> a(n + 1), s(n + 1, 0); for (int i = 1; i <= n; i++) { cin >> a[i]; s[i] = s[i-1] + a[i]; } while (q--) { int l, r; cin >> l >> r; cout << s[r] - s[l-1] << '\n'; } return 0; }这个代码里有个细节：s 和 a 都用 long long。原因很简单，n 个 int 相加很可能超过 int 范围。别问，问就是吃过亏。前缀和的本质是用“额外空间换时间”：你多开一个数组，预处理 O(n)，之后每次查询 O(1)。如果题目里查询次数 q 很大，比如 10^5 甚至 10^6，暴力做法每次 O(n) 就会变成 O(nq)，直接爆炸；而前缀和总复杂度只有 O(n + q)。
1.2 二维前缀和：矩形区域求和的利器
一维前缀和解决的是“区间和”，二维前缀和解决的是“子矩阵和”。假设有一个 n 行 m 列的矩阵 a，定义二维前缀和数组 P[i][j] 表示从 (1,1) 到 (i,j) 这个子矩阵的所有元素之和。
构造递推公式是这个：
P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + a[i][j]
这个公式的图形理解是：P[i-1][j] 是上边一块，P[i][j-1] 是左边一块，两个加起来，左上角那块 P[i-1][j-1] 被加了两次，所以要减掉一次，最后再加上 a[i][j] 自己。这就是容斥原理的基本应用。
查询时，要计算左上角 (x1, y1)、右下角 (x2, y2) 的子矩阵和：
ans = P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] + P[x1-1][y1-1]
同样是容斥：先取整个大矩形，减掉上边多出来的，减掉左边多出来的，然后左上角重叠被减了两次的部分要加回来。
信奥题里二维前缀和的典型场景是：给一张地图，多次询问某个矩形区域内数字的总和。你不用每次重新遍历这个矩形，提前 O(nm) 预处理，每次查询 O(1)。比如后面的“救生员”“地毯”这类经典题，实际上都是二维前缀和或者二维差分的变形。
二维前缀和构造和查询的 c++ 代码逻辑如下：
vector<vector<long long>> p(n + 1, vector<long long>(m + 1, 0)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + a[i][j]; } } // 查询 (x1, y1) 到 (x2, y2) long long ans = p[x2][y2] - p[x1-1][y2] - p[x2][y1-1] + p[x1-1][y1-1];注意 p 数组的维度：要开 (n+1) 行 (m+1) 列，并且第 0 行、第 0 列全部为 0。这样当 x1=1 或 y1=1 时，下标 0 能兜住边界，不用特判。
1.3 为什么前缀和这么“香”
一个很容易被忽略的点是：前缀和不只是用来做区间求和。它更重要的价值在于“把区间信息压缩成两个前缀信息的差”。很多题目里，只要遇到了“连续一段”“某个范围内的总量”这类表述，你都应该下意识想想能不能用前缀和。举例来说：统计一个数组中正数个数，你可以用布尔标记加前缀和；统计某段区间内某个值出现的次数，也可以用前缀和。前缀和本质上是一种“可减性”的利用：只要信息满足类似“整体 - 前面 = 后面”的运算规则，就能前缀化。这和后面的差分形成了完美的镜像关系：前缀和把区间和变成两次查询的差，差分把区间修改变成两次单点修改。
2. 差分：区间修改的反向操作
2.1 一维差分：把“区间修改”化为“两次单点修改”
如果说前缀和是“提前算好总和”，那差分就是它的逆运算。给定数组 a，构造差分数组 b：
b[i] = a[i] - a[i-1]
注意，这里也是从下标 1 开始，并且定义 a[0] = 0，所以 b[1] = a[1]。差分数组有一个关键性质：对差分数组 b 做前缀和，还原出来就是原数组 a。换句话说，a 是 b 的前缀和，b 是 a 的差分，两者互为逆运算。
这个性质有什么用？最经典的场景是：对原数组 a 的某个区间 [l, r] 统一加上一个值 v。如果直接操作 a，最坏要 O(n)；但如果操作差分数组 b，只需要做两处修改：
b[l] += v b[r+1] -= v
为什么这样可行？因为 a 是 b 的前缀和。b[l] 加 v，会让 a[l]、a[l+1]、... 一直到 a[n] 都加上 v。为了让 a[r+1] 及之后恢复原状，再在 b[r+1] 减去 v，这样从 a[r+1] 开始前缀和抵消，就不再变化。整体效果就是只有 [l, r] 这段被加了 v。
给你一个具体例子。a 初始全 0，长度 n=8。我想让 [2, 5] 都加 3，[4, 7] 都加 1。用差分数组操作：
操作1：b[2] += 3，b[6] -= 3。 操作2：b[4] += 1，b[8] -= 1。
然后对 b 做一遍前缀和得到最终 a：
a[1] = 0 a[2] = 3 a[3] = 3 a[4] = 3 + 1 = 4 a[5] = 4 a[6] = 4 - 3 = 1 a[7] = 1 a[8] = 1 - 1 = 0
手推一遍你就会发现，整个过程不只是“公式背下来”，而是真正理解了前缀和的逆运算。这也是我强烈建议初学者自己拿笔推一次的原因。
m 次区间修改，每次都 O(1) 改两个位置，全部操作结束后，只用 O(n) 做一次前缀和把 a 还原出来。总复杂度 O(n + m)，暴力修改则是 O(nm)。当 n 和 m 都到 10^5 以上时，这是本质区别。
区间加操作的实现模板：
vector<long long> diff(n + 2, 0); auto add = [&](int l, int r, long long v) { diff[l] += v; diff[r + 1] -= v; // 注意 r+1 可能等于 n+1，所以数组开 n+2 }; // 所有操作结束后还原 for (int i = 1; i <= n; i++) { diff[i] += diff[i-1]; a[i] = diff[i]; // 此时 diff 已经变成原数组 }我这里的 diff 数组开的是 n+2，因为 r 最大是 n，r+1 就是 n+1，如果数组只开到 n+1，会越界。这个问题在二维差分里更明显，后面会专门讲。
2.2 二维差分：矩阵区域加值
二维差分配合二维前缀和，能解决“给某个子矩阵统一加一个值，最后求整个矩阵变化后的值”这类问题。二维差分的构造思路与一维类似：构建一个差分矩阵 D，使得对 D 做二维前缀和后得到原矩阵 a。
对于一次“左上角 (x1, y1)、右下角 (x2, y2) 加 v”的矩形修改，只需要在差分矩阵里操作四个位置：
D[x1][y1] += v D[x2+1][y1] -= v D[x1][y2+1] -= v D[x2+1][y2+1] += v
然后对 D 做一遍二维前缀和，就得到操作后的原矩阵。这个四角操作的图形意义是：在 (x1, y1) 加 v，让从这个点开始的右下区域都加 v；在右上角和左下角分别减 v，把超出矩形范围的区域消掉；但右上、左下两个区域会被减去两次，所以右下角要加回来一次。这跟前缀和查询时的容斥是完全对称的。
二维差分代码范式：
vector<vector<long long>> d(n + 2, vector<long long>(m + 2, 0)); auto add = [&](int x1, int y1, int x2, int y2, long long v) { d[x1][y1] += v; d[x2+1][y1] -= v; d[x1][y2+1] -= v; d[x2+1][y2+1] += v; }; // 多次调用 add 修改 // 最后二维前缀和还原 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1]; a[i][j] = d[i][j]; } }很多人在写二维差分时会犯一个经典错误：忘记数组要开 n+2 和 m+2，导致处理 x2+1 或 y2+1 时下标越界。为什么是 +2 而不是 +1？因为修改时可能用到 x2+1，而且做前缀和还原的时候，i-1 位置也要能从 0 开始。实际上把第 0 行、第 0 列全留空，再把第 n+1 行、第 m+1 列用来承接边界派生出的“抵消”，是最稳妥的做法。宁可多开一点，也不要越界，这是基本功。
二维差分还有一个常见的坑：把修改和还原混在一起。很多人做一次修改就对整个矩阵做一次前缀和，那复杂度又变回 O(nm) 了。正确的做法是先攒下所有修改，用 O(1) 的四角法更新差分矩阵，最后一次性做前缀和还原。差分的意义就在于“区间修改可以延迟到最后统一结算”，这是它和直接修改最大的区别。
3. 前缀和与差分的组合应用与信奥实战
3.1 树状数组：让前缀和与差分支持动态更新
前面讨论的前缀和与差分，都局限于“数组是静态的”：预处理完后修改很少。但实际题目中经常出现“既有点修改，又有区间查询”的动态场景，比如洛谷模板题里的树状数组 1、树状数组 2。树状数组（Fenwick Tree）就是在这个需求下出现的：它能维护一个数组，支持单点修改和前缀和查询，两者都能做到 O(log n)。
拿一个非常经典的问题来理解树状数组：维护一个长度为 n = 16 的序列，支持查询前缀和 sum(11)，以及单点修改 add(3, x)。如果用普通数组，查询前缀和要 O(n)，修改只要 O(1)。用它反复来回操作，整体还是 O(nq)。树状数组的做法是，用一个树状结构把前缀和“分段存储”，每个位置存的是某个 lowbit 区间上的和。lowbit(x) 定义是 x 的二进制表示里最低位的 1 所对应的数值，比如 lowbit(6) = 2，因为 6 的二进制是 110，最低位 1 对应的值是 2。
query(11) 的流程是反复累加 tree[11]、tree[10]、tree[8]，直到下标变成 0。11 的二进制是 1011，lowbit(11) = 1，所以 11 -> 10（1010），lowbit(10) = 2，所以 10 -> 8（1000），lowbit(8) = 8，所以 8 -> 0。查询是 O(log n)。单点修改 add(3, x) 则是从下标 3 开始，不断向上更新父节点：3 -> 4 -> 8 -> 16，每次 tree[下标] += x，直到超过 n。这也正好 O(log n)。如果想查区间和，就用前缀和相减：sum(r) - sum(l-1)。
树状数组最巧妙的点在于，它和差分可以嵌套使用：如果想支持“区间修改 + 区间查询”，只靠一棵树状数组不够，因为区间修改如果用差分来转，差分数组的每次单点修改对应原数组的区间影响，而原来的前缀和查询会收到两棵树的共同影响。具体做法是维护两棵 BIT：一棵维护差分数组 d[i]，另一棵维护 i*d[i]。区间 [l,r] 加 v 时，在两棵 BIT 上各做两次单点修改；查询前缀和时，用 (sum1 * x - sum2) 这种形式计算。这就是经典的“区间修改 + 区间查询”的双树状数组写法。
struct Fenwick { int n; vector<long long> c; Fenwick(int size) : n(size), c(size + 1, 0) {} void add(int pos, long long val) { for (; pos <= n; pos += pos & -pos) c[pos] += val; } long long sum(int pos) { long long res = 0; for (; pos > 0; pos -= pos & -pos) res += c[pos]; return res; } };我特意把 lowbit 写成pos & -pos，这是位运算写法，也是最常见的写法。手动模拟一次sum(11)，你会发现它比直接遍历 11 个数要快得多，而且不受数组长度影响，只和长度相关的二进制位数有关。信奥里面，树状数组的常数比线段树小很多，代码也短，能处理绝大多数需要动态区间求和的问题。唯一的痛点是它天生只能处理前缀信息，遇见区间最大值之类就不方便了，那就要请出线段树。但至少在“前缀和与差分动态化”这个场景，树状数组几乎是标准答案。
3.2 经典题型拆解：从“借教室”到“差分+前缀和还原”
差分最常见的出题套路是：给你一堆区间，每个区间都让某个统计量 +1，最后问每个点的实际情况。经典题有“种树”“铺地毯”“挤牛奶”等。我的建议是，遇到这种题，不要犹豫，直接往差分上想。
举个例子，一个有 n 个房间的公寓，m 个租房请求，每个请求从第 l 天到第 r 天租住，每天需要一个房间，问有没有哪天房间不够用。这类题盯着“区间加 1”这个操作，差分数组维护每个时间点的增量，所有请求处理完后做前缀和，就能得到每一天的占用房间数，和房间总数比较即可。复杂度 O(n + m)，如果用暴力去每一天查占用，就变成 O(nm)，显然不现实。
还有一类题是“差分 + 二分答案”，比如经典的“借教室”题。它的操作是依次处理若干个区间减 1 的订单，一旦某天教室数量变成负数就停。最容易想到的办法是每次都去区间暴力减，那肯定超时。更稳的思路是二分答案：判断前 k 个订单能否执行。check(k) 时，只对前 k 个订单做差分区间减，然后一次前缀和还原看看哪天会变负。每个 check 是 O(n + k)，二分要 O(log m) 次，总复杂度 O((n + m) log m)，完全能过。这算把差分从一个“小技巧”升级成了“算法框架中的核心组件”。
3.3 复杂度与空间取舍：什么时候能用，什么时候不能用
选了前缀和或差分，代价是什么？空间。
一维前缀和需要额外 O(n)，二维需要 O(nm)。如果 n 和 m 本身都到 10^6，那你必须考虑内存够不够。有时候题目卡内存，你就要想能不能用滚动数组、原地修改或者离散化缩小范围。举个例子，差分数组完全可以在原数组上做，先把原数组当成全 0，区间修改都打在差分上，最后原数组本身变成“还原后的结果”。这样只用一份内存，不需要额外开一个“最终结果数组”。
但还有一个更隐蔽的限制：前缀和依赖的信息必须满足“可减性”。像是求和、求异或和、求布尔值和这种可以整体与部分互相抵消的运算，都能前缀化。但“最大值”“最小值”这种没法通过“减掉前面一部分”得到后面一部分的信息，就不能直接用普通前缀和。这类问题要么用线段树，要么用稀疏表等其他数据结构。我见过不少初学者，学会了前缀和，就什么题都想硬套，结果误判了题意。你要记住：前缀和是个“减法型”工具，不是“全局型”工具。
差分的限制则正好相反：它要求你的操作是“区间整体加减同一个常数”，而且这种加减在预处理期间不会产生“交叉影响”需要即时反馈。如果修改是“区间赋值成某值”而不是“加某值”，差分就帮不上忙了，因为赋值破坏可逆性。好在大部分竞赛题里，加减操作是主流，差分用得飞起。
4. 实操中的常见问题与避坑经验
4.1 下标从 0 还是从 1：一个能省半天调试时间的选择
这是一个看起来小、影响却极大的决策。我的建议很直接：算法题里涉及前缀和、差分的场景，一律从 1 开始存储数组，把 0 位置空出来当哨兵。为什么？因为 S[0] = 0 可以让 [1, r] 的查询公式 S[r] - S[0] 不用特判，差分的 b[1] = a[1] 也不用特殊处理。二维里，第 0 行、第 0 列全 0 的价值更明显：每一条递推公式都能无脑套。
如果你非要从 0 开始，前缀和公式会变成 S[r+1] - S[l]，差分的话要处理 b[0] = a[0] 这个“无中生有”的边界，还要时刻注意 r+1 是否会越界。我不是说从 0 开始写不了，而是说从 1 开始能少想很多边界条件。在你还没有形成“下标偏移”的肌肉记忆之前，从 1 开始是最不容易出错的选择。刷题群里你去看老选手的代码，绝大多数前缀和题都是这么写的。
4.2 溢出、负数与取模：细节决定的 0 分与 100 分
前缀和和差分最大的数值风险是“中间结果溢出”。差分数组在多次区间加之后，某个位置的值可能是很大的数，再做前缀和还原时更可能溢出。我的建议是无脑用 long long，除非你明确知道数据范围非常小。有些题还会要求取模，这个时候更要注意负数问题：差分中做减法（比如 b[r+1] -= v）之后，前缀和还原过程中可能出现负数。标准写法是在每次运算后加 mod 再取模，避免出负数。
举例：diff[r+1] -= v 之后，如果后面要直接做前缀和并用模运算，最好写成：
(d[i] += mod - v) %= mod;虽然这不影响差分本身的正负，但是如果你最后要对原数组取模，那么差分累积过程中的负值会通过加法传递，必须时刻保证每一步都在 [0, mod) 范围内。不少选手在这个环节吃过亏：明明样例能过，大数据一提交就 WA，检查半天发现是负数取模的问题。
4.3 二维操作最易错的四个点
二维前缀和和二维差分的坑比一维多得多。我总结了四个最容易踩的：
第一，数组开小了。前面反复强调，二维差分需要 n+2 行 m+2 列，因为修改操作会用到 x2+1、y2+1，从 1 开始编号时这俩值最大值就是 n+1、m+1，数组少一位就越界。第二，还原差分时把公式抄错。还原的二维前缀和公式是d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1]，有人会漏掉中间的减号。第三，查询矩形范围搞反。对 (x1,y1) 到 (x2,y2)，正确的容斥下标是 x1-1、y1-1、x2、y2，写成别的就会得到完全错误的结果。第四，把修改和还原混在一起。有些人每做一次区间修改就暴力跑一边前缀和，复杂度全毁。真正写法是攒修改、最后还原，前面多次提到，实际操作时特别容易犯。
我建议初学二维部分时，拿一个 3x3 的小矩阵手算一遍，把数组下标和公式每一项对应关系写出来。写一次比看十遍都管用。等你完全理解了那个容斥逻辑，再去写代码就不会只是“背模板”了。
4.4 树状数组与差分结合的边界细节
树状数组和差分结合时，有个容易忽略的问题：两棵树状数组的大小定义。如果原数组长度是 n，区间修改时你要在差分数组的 r+1 位置减 v，此时 r+1 可能等于 n+1。树状数组内部 add 操作的循环条件是pos <= n，如果 pos 超过 n 就更新不了，这个“减 v”就丢失了。但这个时候其实无所谓：因为前缀和查询只查到 n，永远不会去查 n+1 以后的位置，在 r+1 减 v 的操作本来就是多余的。所以你可以选择不处理它，或者专门处理成if (r+1 <= n) add(r+1, -v)。两种逻辑都该在心里有个数，不然你在调试时会很困惑：为什么 add 传了一个 n+1 进去，树状数组却没反应？
还有一个细节：两棵 BIT 维护 i*d[i] 时，i 是原数组下标，d[i] 是差分值。区间修改对第二棵树的影响是add(l, v*l)、add(r+1, -v*(r+1))。这里 v 和下标相乘，也要尽量用 long long，不然又是一个隐蔽的溢出点。
4.5 从“会模板”到“会思路”：我的个人刷题心得
前缀和与差分看起来是小知识点，但它们其实是“逆运算思维”的启蒙：你看到一个数组，不仅可以直接操作它，还可以换一个视角，通过操作它的差分来间接完成目标。这种思维迁移到很多领域都有用。比如在图像处理里，“积分图”就是二维前缀和的应用，让任意矩形区域的像素和能被 O(1) 查询；在统计区间覆盖次数时，差分的思路也比直接遍历高效得多。我甚至觉得，如果你能彻底理解“差分是前缀和的逆运算”这一句话，很多算法题就不再需要死记硬背模板了。
就我个人经验来说，遇到一个新题型，我会先问自己三个问题：能不能转化成区间加减？能不能转换成前缀和查询？能不能用差分延迟计算？这三个问题任何一个是“能”，题目基本就破解一半了。反之，如果你对一个题目完全没有思路，先往这三个方向想，往往也能打开局面。这个习惯是我刷了上百道题之后才慢慢养成的，如果你刚接触，可以直接把这三个问题当“ checklist”用。
到了这里，前缀和与差分的核心内容就全讲完了。代码不多，但每一个模板背后都有值得琢磨的推导过程。希望你不要只背代码，而是真的拿笔在草稿纸上推一遍：把差分数组前缀化还原成原数组，感受一下“逆运算”的美妙。下次再遇到区间修改和区间查询，你就知道，用不上那些花里胡哨的数据结构，前缀和与差分就够你走得非常远了。
