姬轩亦想当年我第一次在算法题里遇到“区间加、区间求和”这种东西，脑子是懵的。当时一个朋友在准备信奥，拿了一道二维矩阵的题来问我，我硬是用暴力写了个O(n^3)的版本，跑了半天没跑出来。后来他给我讲了“前缀和”和“差分”这两个东西，我才发现，原来很多看起来绕来绕去的区间操作，本质上就一句话：把重复计算提前做完，把区间修改变成点修改。这篇文章我想把这些东西彻底掰开揉碎讲清楚，不搞玄乎的公式堆砌，就用最直白的方式告诉你前缀和是干嘛的、差分是干嘛的、它们为什么是一对互逆操作、以及在真实题目里到底怎么用。这篇内容适合什么人群？说实话，从刚接触算法的学生，到准备信奥、蓝桥杯、力扣周赛的朋友，甚至是搞数据分析想快速算累计值的，都能从里面拿到一点东西。
1. 先从最朴素的需求开始：为什么需要前缀和
讲任何算法之前，都得先回答一个问题：没有它，我们会卡在哪里？前缀和的出现，核心是解决一类“高频区间求和”的问题。
假设你有一个长度为 n 的数组，比如 [3, 1, 4, 1, 5, 9, 2, 6]，现在有 m 次询问，每次给你一个区间 [l, r]，让你算出从第 l 个数加到第 r 个数的和。最朴素的做法是什么？每次询问都用一个 for 循环，从 l 加到 r。单次询问的复杂度是 O(n)，如果 m 次询问，那就是 O(n×m)。
当 n 和 m 都跑到 10^5、10^6 这个量级的时候，O(n×m) 直接爆炸。10^5 乘以 10^5 就是 10^10 次运算，在一秒钟的时限里基本不可能跑完。而前缀和这种预处理思路，能把这个复杂度从 O(n×m) 一口气降到 O(n+m)。
它的思想其实特别朴素，甚至你在生活中早就用过。比如你想知道这个月到目前为止一共花了多少钱，你不会每天去翻之前的每一笔账单重算一遍，而是每天记一个“累计到今天的总花费”，想知道某天到某天之间的花费，拿两个累计值相减就行了。
前缀和就是在做这件事。我们首先预处理出一个数组 pre[i]，表示原数组中前 i 个元素的和。一旦有了这个数组，求任意区间 [l, r] 的和，就只需要一个公式：
sum(l, r) = pre[r] - pre[l-1]
为什么是这个公式？因为 pre[r] 是前 r 个元素的总和，pre[l-1] 是前 l-1 个元素的总和，两者相减，正好剩下的就是区间 [l, r] 这一段的元素和。这个过程是 O(1) 的。
记住一个关键点：前缀和适合处理“数组是静态的、查询是凌乱的”这种场景。如果数组本身动不动就被修改了，前缀和就需要重新维护，那是另一套复杂的玩法，暂时先不提，后面我讲到树状数组的时候再说。这里，你先把一个场景焊死在脑子里：多次查询区间和，数组不变，直接前缀和。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 一维前缀和：从预处理到O(1)查询的核心推导
2.1 预处理阶段到底在做什么
很多初学者会问：前缀和的预处理，不就又是一个 O(n) 的循环吗，凭什么比我暴力每次 O(n) 快？这里的关键是摊还的思想。预处理确实要花 O(n)，但只花这一次，之后每一次查询都只需要做一次减法。
咱们来一步步拆解预处理的过程。假设原数组用 a[1] 到 a[n] 存储（这里我特意用从 1 开始的下标，后面你会明白为什么这样写东西特别爽）。我们初始化 pre[0] = 0，然后从 1 到 n 逐个计算：
pre[i] = pre[i-1] + a[i]
这一段代码写出来就是：
cpp复制for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + a[i];
}
这就是把上一轮的累计结果加上当前元素。你去看 pre 数组，它的每一项都是“原数组从开头到这里的和”。比如 pre[3] 一定是 a[1] + a[2] + a[3]。
这里为什么从 1 开始而不是从 0 开始？这是前缀和里一个非常经典的细节。如果你从 0 开始，那你求 [l, r] 区间和的时候，就会经常面临边界判断的麻烦——l = 0 时怎么办？而如果我们让下标从 1 开始，并且规定 pre[0] = 0，那么查询区间 [l, r] 的和就永远是：
pre[r] - pre[l-1]
当 l = 1 时，pre[0] 正好等于 0，公式依然成立，不用特判。
2.2 把查询过程彻底跑通一遍
用一个具体例子来说，数组 [3, 1, 4, 1, 5]，预处理的前缀和是：
| i | a[i] | pre[i] |
|---|---|---|
| 1 | 3 | 3 |
| 2 | 1 | 4 |
| 3 | 4 | 8 |
| 4 | 1 | 9 |
| 5 | 5 | 14 |
现在我要查询区间 [2, 4] 的和。按照公式，pre[4] - pre[1] = 9 - 3 = 6。看看原始数组：a[2] + a[3] + a[4] = 1 + 4 + 1 = 6，完全一致。
再查 [3, 5]：pre[5] - pre[2] = 14 - 4 = 10。原始数组：4 + 1 + 5 = 10，也对。
这个算法没有一丁点复杂的逻辑，但它的价值是几何级的。你可以自己造一组数据感受一下：n = 100000，m = 100000，暴力要跑 10^10 次加法，而前缀和只需要 10^5 次预处理加 10^5 次减法。这就是算法的魅力——降低复杂度不是靠硬件速度，而是靠逻辑优化。
2.3 前缀和不止能求“和”
很多人把前缀和这个名字理解窄了，以为它只能求区间和。其实它的思想可以推广到任何具有“可减性”的运算上。什么意思？如果一个运算是满足 op(a, b, c) 反过来能求出中间段 的性质，那就可以用前缀和的思想。
最常见的一个推广是前缀异或和。异或运算有个性质：x ^ x = 0，所以你维护一个 xorPre[i] 表示前 i 个元素的异或结果，那么区间 [l, r] 的异或值就是：
xorPre[r] ^ xorPre[l-1]
这个在某些涉及位运算的题目里会非常有用，我见过不少题目表面上是求区间某种奇偶判断，最后就落脚在异或前缀和上。
还有一个推广是前缀积，但注意，实数域的前缀积在很多时候会因为数值过大而溢出，或者因为精度问题失真。所以在竞赛圈里，前缀和本身最常见，其次是前缀异或。总之，你只要记住：如果一个运算能通过“相减”或“相逆”的操作还原出中间段，那么它就能配合前缀和。
3. 二维前缀和：从平面面积到矩阵区间求和
3.1 二维场景里的核心痛点
一维搞明白了，接下来就是头疼的二维。在一个 n×m 的矩阵里，让你反复求某个子矩阵的和。比如给定一个 5×5 的矩阵，每次问 (x1, y1) 到 (x2, y2) 这个矩形区域内的所有数字之和是多少。
暴力做法就是每次都四重循环，把这片区域里的元素一个个加起来。复杂度每次是 O(n×m)。如果查询特别多，又是爆炸。二维前缀和就是解决这个问题的。
你可以在脑子里把“区间和”类比成“面积”。一维前缀和，pre[i] 是从起点到 i 这条线段的面积（其实就是长度加权后的和）。二维前缀和，pre[i][j] 就是从矩阵左上角 (1,1) 到 (i,j) 这个矩形区域的面积和。
计算 pre[i][j] 的公式是：
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]
这个公式很多初学者第一次看会懵，其实用面积图解释非常清楚。pre[i-1][j] 是上面一块的面积，pre[i][j-1] 是左边一块的面积，两个加起来，中间有一块 pre[i-1][j-1] 被加了两次，所以要减掉一次。最后再把当前位置的元素 a[i][j] 加上。
3.2 从公式到代码的细节
二维前缀和的预处理代码长这样：
cpp复制for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j];
}
}
这里的边界条件是什么？pre[0][j] 和 pre[i][0] 全部初始化为 0 就行。你会发现下标从 1 开始又一次救了命，因为当 i=1 或者 j=1 的时候，公式里的 pre[0][j]、pre[i][0]、pre[0][0] 都是 0，不需要特殊处理。
查询子矩阵 (x1, y1) 到 (x2, y2) 的和，公式是：
sum = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]
为什么是这个？还是拿面积说事。pre[x2][y2] 是大矩形总面积，减去上面多出来的 pre[x1-1][y2]，减去左边多出来的 pre[x2][y1-1]，因为左上角那块 pre[x1-1][y1-1] 被减了两次，所以要加回来。这个过程只用 O(1) 时间。
3.3 一个具体的例子让你彻底走一遍
假设矩阵是：
code复制1 2 3
4 5 6
7 8 9
预处理出来的二维前缀和应该是：
code复制 1 3 6
5 12 21
12 27 45
我验证一下：pre[2][2] 应该是 1+2+4+5 = 12，表格里正是 12。pre[3][3] 是全部元素之和 45，也对。
现在我要查询 (2,2) 到 (3,3) 这个子矩阵，也就是右下角 2×2 的区域，元素是 5 6 8 9，和应该是 28。
套公式：pre[3][3] - pre[1][3] - pre[3][1] + pre[1][1] = 45 - 6 - 12 + 1 = 28，完全正确。
二维前缀和在实际题目里出现频率极高，特别是在图像处理、棋盘问题、矩阵区域统计这类题目里。你掌握了它，就相当于掌握了一种把二维区域查询变成 O(1) 的武器。
4. 差分：区间修改的终极偷懒思路
4.1 从朴素操作到差分的诞生
前缀和解决的是“多次查询静态数组”的问题。现在换个需求：有一个数组，我不仅想查区间和，还想频繁修改——每次把 [l, r] 这个区间里的所有元素都加上一个常数 c，然后再查询。如果你老老实实每次遍历区间去做修改，那修改一次的复杂度就是 O(n)，频繁修改依旧爆炸。
差分就是解决这个问题的。差分的核心思想是：我不去改变原数组本身，而是维护一个差分数组，让区间修改变成两次单点修改。
先定义一个差分数组 d，其中 d[i] = a[i] - a[i-1]（同样，下标从 1 开始，且 a[0] = 0）。这个差分数组的性质非常巧妙：原数组 a[i] 就等于差分数组的前缀和，也就是 a[i] = d[1] + d[2] + ... + d[i]。
怎么理解这个性质？你自己验证一下：a[3] 等于 d[1] + d[2] + d[3]，展开就是 (a[1]-0) + (a[2]-a[1]) + (a[3]-a[2])，中间项全部抵消，正好等于 a[3]。这就是为什么差分和前缀和是一对逆运算。
4.2 区间修改如何在O(1)内完成
现在假设我们要把区间 [l, r] 的每一个元素都加上 c。在差分数组上，我们只需要做两次操作：
code复制d[l] += c
d[r+1] -= c
然后就结束了。为什么这样就能让 a[l] 到 a[r] 全部加 c？因为原数组 a[i] 是差分数组的前缀和。当你在 d[l] 上加 c，那么从 a[l] 开始，所有位置的前缀和都会多出 c。当你在 d[r+1] 上减 c，从 a[r+1] 开始，多的这个 c 又被抵消掉了。最终效果就是只有区间 [l, r] 受到了影响。
用一个例子彻底说明白。原数组 a = [1, 2, 3, 4, 5]，差分数组 d = [1, 1, 1, 1, 1]。现在我要把 [2, 4] 区间每个数加 10。
在差分数组上进行 d[2] += 10, d[5] -= 10，得到：
d = [1, 11, 1, 1, -9]
现在把差分数组做前缀和还原成原数组：
a[1] = 1
a[2] = 1 + 11 = 12
a[3] = 1 + 11 + 1 = 13
a[4] = 1 + 11 + 1 + 1 = 14
a[5] = 1 + 11 + 1 + 1 - 9 = 5
结果就是 [1, 12, 13, 14, 5]。看看，从 2 到 4 的元素确实都加上了 10，而第 1 个和第 5 个元素没有变。
单次区间修改的复杂度从 O(n) 降到了 O(1)，这就是差分的价值。如果你做了 k 次区间修改后想查看最终数组，只需要做一次 O(n) 的前缀和还原。于是整体的复杂度被压缩成了 O(n+k)。
4.3 差分的典型应用场景
差分最经典的应用是区间整体加减，或者“多次区间染色”问题。比如有一个长度为 n 的数组，初始全是 0，现在有 m 个操作，每次把 [l, r] 这个区间内的所有数都加上 1，问最终数组是什么样。这种题直接用差分做，复杂度 O(n+m)。
还有一类题目是“列车停靠站”问题，或者“区间覆盖次数”问题。比如一条公路上有很多区间段要覆盖，问每个点被覆盖了几次。本质上就是在一个全零数组上做多次区间加 1，也直接差分。
甚至有一些题不是明摆着让你用差分的，但你在分析过程中会发现需要“快速给一个区间加上一个等差数列”或者“区间加某个多项式”，那就需要差分的高阶版本了。不过那个先不谈，先把基础差分的思路吃透。
5. 二维差分：让你的区间修改从面到体
5.1 二维差分的构造逻辑
一维差分處理的是“区间”的修改，二维差分處理的就是“子矩阵”的修改。需求是：有一个二维矩阵，每次把某个矩形区域内的所有元素都加上一个常数 c，问最终矩阵是什么。
二维差分数组的构造思想跟一维完全一致，只不过每个维度都要做一次“相邻相减”。具体来说，定义差分数组 d，使得原数组 a[i][j] 等于 d 的二维前缀和。构造公式是：
d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]
这个公式看着眼熟不？没错，和二维前缀和的容斥公式正好是反过来的。前缀和是加法容斥，差分就是减法容斥。
5.2 子矩阵加法的四角操作
现在我要把以 (x1, y1) 为左上角、(x2, y2) 为右下角的子矩阵内的所有元素都加上 c。在二维差分数组上，只需要做四次单点修改：
code复制d[x1][y1] += c
d[x2+1][y1] -= c
d[x1][y2+1] -= c
d[x2+1][y2+1] += c
这四个点的操作方向很有意思：左上角加，右上角和左下角减，右下角加。为什么右下角反而要加？因为 - 会被重复减两次，需要加回来一次。这个逻辑跟二维前缀和查询公式里的 + pre[x1-1][y1-1] 如出一辙。
经过这四次修改后，你对差分数组做一遍二维前缀和还原，就能得到修改后的原数组。还原公式就是：
cpp复制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];
}
}
之后 d[i][j] 里存的就是最终原数组 a[i][j] 的值了。
5.3 手动验证二维差分的每一步
用一个 3×3 的矩阵来验证。假设原矩阵是：
code复制0 0 0
0 0 0
0 0 0
全 0 矩阵的差分矩阵当然也是全 0。现在我要把左上角 (1,1) 到右下角 (2,2) 这个 2×2 的子矩阵全部加 5。
按四角操作：
code复制d[1][1] += 5
d[3][1] -= 5
d[1][3] -= 5
d[3][3] += 5
得到的差分矩阵是：
code复制 5 0 -5
0 0 0
-5 0 5
然后做二维前缀和还原。从第一行开始：
d[1][1] = 5
d[1][2] = 0 + 5 = 5
d[1][3] = -5 + 5 = 0
第二行：
d[2][1] = 0 + 5 = 5
d[2][2] = 0 + 5 + 5 - 5 = 5
d[2][3] = 0 + 0 + 0 - 5 + 5 = 0
我偷个懒，直接用直觉说：还原后会是
code复制5 5 0
5 5 0
0 0 0
完全符合预期。第一个 2×2 子矩阵全是 5，其他位置都是 0。这个验证过程你可能觉得繁琐，但真的建议你手动跑两遍，跑顺了，二维差分就再也不会忘了。
6. 前缀和与差分的联动：从区间加区间和到整体解题思路
6.1 这对互逆操作如何配合使用
前缀和和差分是一对互逆的操作。前缀和把一个数组加工成累计数组，差分把一个数组还原成相邻差数组。这两者往往不是孤立使用的，而是组合在一起解决复杂的区间问题。
有一个很典型的题型是：先进行多次区间修改，然后进行多次区间求和。比如你有 n 个数，先做 m1 次“区间加”操作，再做 m2 次“区间求和”查询。直接的做法是用线段树，但用差分加前缀和也能低成本解决。
做法分三步：
- 第一，用差分数组处理所有修改。每次把
[l, r]区间加 c，就在差分数组上执行d[l] += c, d[r+1] -= c。这一步每次操作 O(1)。 - 第二，对差分数组做一次前缀和，还原出最终的数组
a。 - 第三，对最终数组再做一次前缀和，得到
pre。然后所有查询就用pre[r] - pre[l-1]回答。
整个过程把区间修改和区间求和都变成了 O(1) 或 O(n) 级别。你想想，如果直接用暴力，修改 O(n)、查询 O(n)，遇到大数据直接歇菜；而差分加前缀和的组合拳，总复杂度只有 O(n + m1 + m2)。
6.2 什么时候选差分，什么时候选前缀和
很多人分不清这两个东西的使用场景，我总结一个最简单好记的法则：
- 如果题目是“静态数组 + 多次区间查询”，选前缀和。
- 如果题目是“多次区间修改 + 最后看一下结果”，选差分。
- 如果题目是“多次区间修改 + 多次区间查询”，先差分后前缀和。
这三种情况覆盖了绝大多数区间操作的入门题目。本质上，前缀和的优势在查询端，差分的优势在修改端，两者互补。你只需要先判断这个题目里的操作重心放在哪里，就知道该用什么了。
6.3 信奥题目里的经典套路
在信奥题里，前缀和和差分经常是作为某一题的“第一步优化”出现的。比如有一类题是：给你 n 个点，每个点初始有一个权重，然后有 k 个操作，每个操作把某一段区间内的点权重全部加某个值，问最后权重最大的点在哪。看起来好像要用什么高级数据结构，但其实直接差分就能搞定。
差分解决这类问题的优雅之处在于：它把“影响一整段”的问题转换成了“只影响两个点”。你再做一次前缀和，就把影响铺开。可以理解为，差分是一种“种因”的操作，前缀和是一种“结果显现”的操作。
我强烈建议你遇到区间类的题，先想暴力，再想能不能用这两种工具优化。如果优化成功，那大概率就不需要上树状数组和线段树了。只有当你需要同时维护修改和查询，而且操作顺序是交错的、不能先处理所有修改再做所有查询的时候，才需要考虑更高级的数据结构。
7. 常见问题与避坑技巧实录
7.1 下标从1开始到底有多重要
我平时看很多初学者写的代码，前缀和下标从 0 开始，然后查询的时候疯狂特判 if (l == 0)。说实话，这就是给自己找罪受。下标从 1 开始，pre[0] = 0，所有边界情况全部消失。这个习惯我希望你从第一次学就养成。
在二维里也一样。所有 pre[0][j]、pre[i][0]、pre[0][0] 全部分配为 0，查询公式不需要任何特判。这是无数人踩坑踩出来的经验，你直接接收这个经验就好。
7.2 二维操作方向搞混的救星：记住“加减对称”
二维前缀和和二维差分，公式看起来都是四个项，容易记混。这里我分享一个老选手的独家记忆方法。
对于二维前缀和的构建公式：pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]，记住“上 + 左 - 左上 + 自己”。
对于二维前缀和的查询公式：pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]，记住“大 - 上 - 左 + 左上”。
对于二维差分的更新操作，跟查询公式一模一样，左上加，右上减，左下减，右下加。
你只要把这一类操作都总结成“四角操作”，每次写之前心里默念一遍，就不容易搞反了。
7.3 数据范围与溢出问题
前缀和这种东西，一算就是累计值，一不小心就可能超出 int 的范围。如果你在做题，n 是 10^5，a[i] 最大是 10^9，那前缀和的最大值就是 10^14，int 直接炸。这种时候必须用 long long，不用犹豫。
另外，差分数组里可能会有负数，因为 a[i] - a[i-1] 可能是负的。这不影响正确性，但有些代码习惯用 unsigned 类型的同学会在这里踩坑，注意别用无符号类型存差分数组。
7.4 差分还原时的一个直觉陷阱
如果你自己手写差分还原，有时候会发现还原出来的结果和自己预期不一致。这里最常见的问题是：你做了区间修改操作之后，是否记住了要在最后做一次前缀和还原？很多新手在差分数组上做了修改，然后直接输出差分数组，发现和原数组对不上，就以为算法错了。
差分数组就是用来做修改的草稿纸，它不是最终答案。最终答案必须通过对差分数组求前缀和来得到。这就好比你在记账本上记的是流水，但你想知道这个月花了多少钱，得把流水汇总一遍，而不是直接把最后一笔流水当总额。
7.5 练习建议：从力扣到信奥的刷题节奏
如果你想彻底掌握前缀和和差分，光看文章是不够的，建议按下面这个顺序找题练手：
- 力扣 303（区域和检索 - 数组不可变）：最简单的一维前缀和。
- 力扣 304（二维区域和检索 - 矩阵不可变）：二维前缀和入门。
- 力扣 1109（航班预订统计）：差分的经典应用题。
- 力扣 798（得分最高的最小轮调）：稍微绕一点，但用的也是差分思想。
- 信奥题里关于“区间加”“海面覆盖”的题，网上搜“差分 区间 覆盖”能找到一堆。
每道题不要只看题解，先自己尝试从暴力优化到前缀和或差分，再对比题解。这个过程你走一两遍，基本就内化这两个工具了。
8. 从区间工具到思维模型的扩展
写到最后了，我想多说一句题外话。前缀和和差分表面上只是一对算法技巧，但它们的核心思想——“预处理”和“反推”——在很多地方都能用到。你处理任何一批数据，如果能提前算出一些累计值，就能在后续大量复用；如果能把“影响一段区域”的操作变成只记录起止影响，就能极大减少重复劳动。
这种思想不仅适用于算法题，也适用于实际工程场景。比如数据分析中计算滑动窗口统计量、概率论里累计分布函数的计算，甚至 MySQL 里的预聚合报表，本质上都带着前缀和和差分的影子。
把这个基础打扎实了，后面你再学树状数组、线段树那些更高级的数据结构，会觉得顺滑很多。因为你会发现，那些复杂结构的核心，还是在帮你处理区间修改和区间查询，只不过它们能应对更加动态、更加复杂的变化而已。前缀和与差分，就是打开区间问题大门的第一把钥匙。