企业官网建设流程全解析

最早接触前缀和，是在一道很朴素的题里栽了跟头：一个数组，m 次区间求和，每次循环累加，数据量一大直接超时。那时候才反应过来，这类题考的不是你敢不敢写循环，而是你懂不懂把计算结果提前存好。另一边的差分数组恰好是相反的思路——当一个区间需要被反复修改时，与其老老实实地更新每个元素，不如只修改边界上的两个端点，最后一次性把结果算出来。这两个技巧在竞赛和面试笔试里出现频率极高，而且经常成对出现：前缀和负责快速求和，差分负责快速更新。这篇文章把一维、二维的公式和推导完整过一遍，也会把我实际踩过的坑一并写出来。

1. 一维前缀和：把区间求和从 O(n) 降到 O(1)

1.1 先看暴力写法为什么扛不住

假设有一个长度为 n 的数组a[1..n]，然后有 m 个查询，每次给你l, r，问a[l] + a[l+1] + ... + a[r]是多少。最直观的写法就是一个循环累加：

for (int query = 0; query < m; query++) { long long sum = 0; for (int i = l; i <= r; i++) sum += a[i]; cout << sum << "\n"; }

如果n = 100000，m = 100000，最坏情况下每次查询都遍历整个数组，总共就是10^10次加法，任何合理的时间限制都过不去。这里的问题在于：我反复处理的是同一批数据，但每次查询都重新把区间从头到尾扫一遍，之前的计算结果完全没有被复用。

前缀和的思路很简单：既然要多次求区间和，那就先把“从第 1 个元素到第 i 个元素的总和”全部预处理好，之后每次查询直接拿预处理的数值做一次减法。

1.2 前缀和数组的构造与区间和公式

设pre[i]表示原数组前 i 个元素的和，即：

pre[i] = a[1] + a[2] + ... + a[i]

构造方式非常直接，从 1 一直递推到 n：

vector<long long> pre(n + 1, 0); for (int i = 1; i <= n; i++) { pre[i] = pre[i - 1] + a[i]; }

这里我特意把pre[0]设为 0，这是一个很重要的约定，后面会说明为什么。构造完成后，查询区间[l, r]的和只需要：

sum(l, r) = pre[r] - pre[l - 1]

为什么是pre[r] - pre[l - 1]，而不是pre[r] - pre[l]？因为pre[r]包含的是前 r 个元素，减去前 l-1 个元素后，剩下的刚好是第 l 个到第 r 个。比如查询[2, 4]，pre[4]包含了 a[1]、a[2]、a[3]、a[4]，pre[1]只包含 a[1]，两者相减就得到 a[2] + a[3] + a[4]。边界情况上，如果l = 1，公式变成pre[r] - pre[0]，因此pre[0] = 0让公式对所有合法区间统一成立，不用单独写 if 特判。

1.3 用一组具体数字把公式验证一遍

用一个实际数组走一遍。假设：

a = [1, 3, 5, 7, 9]

下标从 1 开始，那么：

查询[2, 4]的和：直接算应该是3 + 5 + 7 = 15。用公式pre[4] - pre[1] = 16 - 1 = 15，完全一致。再看查询[3, 5]：手动加是5 + 7 + 9 = 21，公式pre[5] - pre[2] = 25 - 4 = 21。

到这里可以发现，前缀和把“每次查询 O(n)”的问题变成了“预处理 O(n) + 每次查询 O(1)”，整体复杂度从O(n*m)降到O(n+m)。这不是简单的时间常数优化，而是复杂度量级上的变化。在题目要求n,m都在10^5甚至10^6级别时，这是唯一可行的做法之一。

2. 一维差分：区间更新的反向思维

2.1 差分数组是怎么定义出来的

前缀和处理的是“静态查询”，但很多问题并不只是查区间，而是先给你一堆“区间更新”操作。比如 m 次操作，每次把[l, r]内的所有元素都加上 v，最后要输出整个数组。暴力做法每次更新都要遍历区间内元素，m 次操作复杂度是O(n*m)，和前面前缀和的暴力查询一样扛不住。

差分数组的核心思想是：我不去维护原数组本身，而是维护原数组“相邻元素之间的差值”。

定义差分数组diff[i]：

diff[1] = a[1] - 0 diff[i] = a[i] - a[i-1] (i >= 2)

也就是说，diff[i]记录的是 a[i] 比 a[i-1] 多出来的部分。这个定义和前缀和正好是相反的操作：对diff做前缀和，就能恢复出a：

a[i] = diff[1] + diff[2] + ... + diff[i]

这一点非常关键。前缀和是把原数组累加成和，差分是把原数组拆成相邻差；两者互为逆运算。可以用一个类比来理解：原数组是一段路程上每个公里标的位置，前缀和相当于从起点到每个点走过的总距离，差分则相当于每一小段路的长度。

2.2 区间加法的两个标记点为什么成立

如果我要把[l, r]内所有元素都加 v，在差分数组上只需要做两个操作：

diff[l] += v diff[r+1] -= v

然后对diff做一遍前缀和，得到的数组就是更新后的原数组。为什么这样是对的？

想象一下原数组的“增量”部分：更新前所有位置增量为 0。更新后，l 到 r 之间的每个位置增量都应该是 v，而其他位置增量为 0。那么看相邻差值：在 l 这个位置，前一项（l-1）增量是 0，当前项（l）增量变成 v，所以增量部分的差分在 l 处突然增加 v；从 l+1 到 r，每一项增量都是 v，相邻之间差分是 0，不需要改动；到 r+1 这个位置，前一项（r）增量是 v，当前项（r+1）增量又变回 0，所以差分在这里突然减少 v。

用具体值验证。原数组：

a = [1, 3, 5, 7, 9]

先构造差分数组，为了保险，我按定义从 i=1 到 5：

diff[1] = 1 diff[2] = 3 - 1 = 2 diff[3] = 5 - 3 = 2 diff[4] = 7 - 5 = 2 diff[5] = 9 - 7 = 2

现在执行操作：把[2, 4]内所有元素加 2。按规则：

diff[2] += 2 => diff[2] = 4 diff[5] -= 2 => diff[5] = 0

然后对 diff 做前缀和：

i=1: 1 i=2: 1 + 4 = 5 i=3: 1 + 4 + 2 = 7 i=4: 1 + 4 + 2 + 2 = 9 i=5: 1 + 4 + 2 + 2 + 0 = 9

得到[1, 5, 7, 9, 9]。原数组[2, 4]位置的元素 3、5、7 加 2 后是 5、7、9，位置 1 和 5 不变，结果完全正确。

2.3 一个完整例子：多次区间加后求最终数组

实际题目一般不会只做一次区间加，而是做很多次。比如有一次我帮一个学弟调一个“涂色板”问题：有一面墙，长度 n，m 次操作，每次把区间[l, r]刷成某种颜色，问最终墙上有多少段被覆盖过。这类题本质上是统计每个位置被区间覆盖的次数。

做法是维护一个全 0 的差分数组，每次操作：

diff[l] += 1 diff[r+1] -= 1

所有操作结束后，对 diff 做一遍前缀和，得到的就是每个位置被覆盖的次数。覆盖次数大于 0 的位置就是被刷过的。这样整个算法复杂度只有O(n+m)，而暴力模拟每次都要更新[l, r]里的每个位置。

另一个经典变体是“区间翻转”：一个只包含 0 和 1 的数组，每次把[l, r]区间内所有数字翻转（0 变 1，1 变 0），最后输出结果。同样可以用差分，只是把每次操作变成：

diff[l] += 1 diff[r+1] -= 1

最后还原时，对每个位置累加 diff，如果累计值是奇数，说明该位置被翻转了奇数次，最终值就是1 - 原值；如果是偶数则不变。这个技巧在不少题目里比线段树简单得多。

3. 二维前缀和：从一维推广到矩阵的关键是容斥

3.1 二维前缀和的递推公式怎么理解

一维前缀和解决的是“数组区间求和”，二维前缀和解决的是“矩阵子区域求和”。假设有一个n行m列的矩阵a，我定义s[i][j]表示从(1,1)到(i,j)这个矩形区域内所有元素的和，即：

s[i][j] = sum(a[x][y]) (1 <= x <= i, 1 <= y <= j)

构造公式是：

s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]

第一次看这个公式时，很多人觉得奇怪：为什么要多减去一个s[i-1][j-1]？用一个直观的例子说明。把s[i-1][j]看成上方所有行的和，s[i][j-1]看成左方所有列的和，两者相加时，左上角区域(1,1)到(i-1,j-1)被加了两次，但这一块只需要计算一次，所以必须减掉一次。最后再加上右下角当前格子的值a[i][j]，得到完整的矩形和。

代码实现：

vector<vector<long long>> s(n + 1, vector<long long>(m + 1, 0)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]; } }

注意s[0][j]和s[i][0]都保持为 0，这样公式在 i=1 或 j=1 的边界上也能统一成立。

3.2 子矩阵和查询公式与边界处理

有了二维前缀和数组s，查询任意子矩阵(x1, y1)到(x2, y2)的和可以用类似容斥的思路：

res = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]

这四个部分分别代表什么？s[x2][y2]是整个大矩形；减去s[x1-1][y2]去掉上面多余的部分；减去s[x2][y1-1]去掉左边多余的部分。但是左上角那一块被减了两次，所以要加回来一个s[x1-1][y1-1]。这个模式和构造递推公式完全一致，都是二维容斥。

查询代码：

long long query(int x1, int y1, int x2, int y2) { return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]; }

边界上如果x1 = 1或y1 = 1，x1-1 = 0或y1-1 = 0，读到的s[0][...]或s[...][0]都是 0，不会出错。这也是为什么多开一行一列并初始化为 0 至关重要。

3.3 三阶矩阵手算验证

用一个实际的 3×3 矩阵来验证，避免公式停留在纸面上。假设矩阵：

1 2 3 4 5 6 7 8 9

逐格计算二维前缀和：

其中s[2][2] = 1+2+4+5 = 12，s[3][3] = 45。现在查询子矩阵(2,1)到(3,3)，也就是第二、三行的所有列，直接手算是4+5+6+7+8+9 = 39。用公式：

s[3][3] - s[1][3] - s[3][0] + s[1][0] = 45 - 6 - 0 + 0 = 39

结果正确。再查一个更小的区域(2,2)到(3,3)，手算是5+6+8+9 = 28。公式：

s[3][3] - s[1][3] - s[3][1] + s[1][1] = 45 - 6 - 12 + 1 = 28

二维前缀和在图像处理里也非常常用，比如做局部均值滤波、统计某个区域内像素值的总和。工作里我做过一个简单的热力图统计功能，地图被切成很多小格子，用户想快速知道某个矩形范围内有多少活跃用户，就是先预处理整张矩阵的二维前缀和，之后每个查询都是 O(1)。

4. 二维差分：四个标记点解决矩形区域更新

4.1 二维差分数组与“桶标记法”

如果说一维差分的核心是两个标记点，那二维差分的核心就是四个标记点。它的适用场景是：有一个矩阵，进行 m 次操作，每次把某个子矩阵内所有元素全部加上 v，最后输出矩阵。如果直接暴力更新，每次操作的最坏复杂度是O(n*m)，总复杂度可能达到O(n*m*q)，数据规模稍大就彻底没戏。

二维差分的定义方式其实可以从一维推广过来，但实际使用中我们通常不直接构造一个现成的差分矩阵，而是把它当作一个“标记桶”：先初始化一个全 0 的二维数组diff，所有矩形加法都通过修改diff上的四个点来记录，最后对diff做二维前缀和恢复原矩阵。

一个常用技巧是：如果已经存在初始矩阵a，我可以把每个位置(i,j)的初始值看成一次单点矩形加法，执行add(i, j, i, j, a[i][j])，这样diff就包含了初始值的信息，最后统一还原。这样代码逻辑统一，不容易漏掉初始值。

4.2 矩形区域加法的四个角：原理拆解

假设要把(x1, y1)到(x2, y2)这个矩形区域内的所有元素加 v，二维差分的操作是：

diff[x1][y1] += v diff[x2+1][y1] -= v diff[x1][y2+1] -= v diff[x2+1][y2+1] += v

四个点怎么记？很多初学者靠死记硬背，我一般这样理解：二维前缀和的性质是，如果在某个点(x, y)放一个值 v，做二维前缀和后，v 会从该点向右下方向传播，影响所有(x' >= x, y' >= y)的位置。

所以要在某个矩形区域加 v，其实就是四个“传播源”的叠加：

• (x1, y1)放 +v：让整个右下部分都加上 v。
• (x2+1, y1)放 -v：把 x > x2 的行全部抵消掉，让影响范围只到 x2。
• (x1, y2+1)放 -v：把 y > y2 的列全部抵消掉，让影响范围只到 y2。
• (x2+1, y2+1)放 +v：前面两个 -v 在右下重叠区域把值多减了一次，这里补回来。

把这四个传播源叠加后，有效影响范围正好就是(x1,y1)到(x2,y2)的矩形内部。我实际写代码时会用注释把每一行的意图标出来：

void add(int x1, int y1, int x2, int y2, long long v) { diff[x1][y1] += v; diff[x2+1][y1] -= v; diff[x1][y2+1] -= v; diff[x2+1][y2+1] += v; }

4.3 二维差分还原的代码与实验验证

所有矩形加操作完成后，对diff做二维前缀和还原：

for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]; } }

还原之后，diff[i][j]就是最终矩阵每个位置被加的总量。如果初始矩阵全是 0，这一步之后直接输出diff即可；如果初始矩阵非 0，需要在还原之后的数组上再加上初始值，或者在初始化时把初始值通过上述add单点矩形加法写进diff。

用一个 3×3 全 0 矩阵验证。执行操作：把(1,2)到(2,3)的矩形加 5。四个标记点分别是：

diff[1][2] += 5 diff[3][2] -= 5 diff[1][4] -= 5 diff[3][4] += 5

注意这里矩阵只有 3 行 3 列，所以x2+1 = 3、y2+1 = 4都落在了多开出来的位置，安全。对diff做二维前缀和后，最终效果是：

0 5 5 0 5 5 0 0 0

只有第 1、2 行的第 2、3 列被加了 5，完全符合预期。如果觉得不放心，可以再加一次其他矩形操作，比如把(2,2)到(3,3)加 2，看四个标记点叠加后还原结果是否正确，多试几次就会形成肌肉记忆。

5. 实战中反复踩过的几个坑

5.1 下标从 1 开始并不只是习惯

很多学校教材和刷题网站习惯用 0 下标，但做前缀和、差分时我强烈建议从 1 开始。原因很简单：前缀和公式pre[r] - pre[l-1]在l = 1时需要pre[0]，如果数组下标从 0 开始，pre[0]是第一个元素本身还是空和为 0，很容易混；差分公式diff[r+1] -= v在r = n时需要访问diff[n+1]，如果数组长度刚好是 n，这就会越界。

统一约定：原数组下标从 1 到 n，前缀和数组和差分数组都开n+1或n+2的大小，第 0 个位置初始化为 0。这样所有公式都是闭区间形式，不需要在边界上写一堆特判。二维的s和diff统一开(n+1)*(m+1)，如果要做二维差分，进一步开到(n+2)*(m+2)。

5.2 差分数组开 n+2 而不是 n+1 的原因

一维差分中，如果执行add(l, r, v)时r = n，需要访问diff[n+1]；二维差分中，如果子矩阵最右或最下边界取到最大值，同样需要访问diff[x2+1][y2+1]。因此差分数组至少要开n+2（一维）或(n+2)*(m+2)（二维）。直接开到 n+2 还可以避免另一个隐患：本地测试数据小的时候，越界不一定崩溃，它会静默污染相邻内存，结果看起来像“玄学错误”，排查起来特别浪费时间。

多维数组如果需要较大空间，建议用vector动态初始化，或者声明为全局变量。局部大数组很容易爆栈，这个我踩过一次：某次在函数里定义了一个5000*5000的二维数组，程序一跑就段错误，改成全局数组后立刻正常。

5.3 多组测试数据的残留问题与溢出问题

竞赛题里常见“多组测试数据”，每一组都要重新算一遍。最容易犯的错误是：只初始化了原数组，忘了把diff或前缀和数组清空。上一组数据的差分标记还残留在数组里，新一组数据一累加，结果完全错乱。我现在的习惯是直接在循环体内用vector定义并初始化为 0，这样每组数据自动从头开始，不会残留。

另一个容易忽略的点是数据范围。前缀和存储的是累加结果，数值很容超过int范围。假设一个长度为 100000 的数组，每个元素是10^9，前缀和可以到10^14，明显超过 32 位整形的上限。所以涉及前缀和、差分累加的地方，一律用long long或更大类型，不要在输出时才临时转换，中途溢出就晚了。二维场景下这个风险更大，因为矩形区域内元素数量是成百上千的相乘关系。

还有一个使用上的常见混淆：差分数组的“构造”和“还原”都叫前缀和，方向容易记反。构造差分是“相邻相减”，方向是从原数组到 diff；还原是“前缀累加”，方向是从 diff 到原数组。我教过一个同学，他代码里把diff[i] = a[i] - a[i-1]错写成diff[i] = a[i-1] - a[i]，最后整个输出镜像翻转，调试了半天才发现是符号问题。一个简单的记忆方式：差分描述的是“变化量”，区间加 v 时，左端变化量增加 v，右端结束处变化量减少 v。

6. 把这两个技巧组合起来：更多应用场景

6.1 差分 + 前缀和：先区间更新再多次区间查询

有些题目的操作分两个阶段：先进行 m 次区间更新，再进行 k 次区间查询。这种场景单靠前缀和或差分都不够，但把两者串起来就是完整的解法。

第一阶段用差分数组diff记录所有区间加操作，结束后对diff做前缀和，还原出“更新后的完整数组”。第二阶段对还原后的数组再构建一层前缀和数组pre，这样后续每次查询区间和都是 O(1)。整体复杂度是 O(n+m+k)，每一步都在做该做的事，没有任何多余计算。

我经常把这个组合方法当作“轻量级线段树”来用。线段树能同时支持区间更新和区间查询，功能更强，但代码量和思维复杂度高出不少。如果题目只是“多次更新 + 最后几次查询”或者“更新完再查询”，差分+前缀和足够。

6.2 前缀和配合哈希统计子数组

前缀和不只是用来求区间和，它还能配合哈希表解决“统计和为 k 的子数组个数”这样的问题。思路是：任意子数组[l, r]的和等于pre[r] - pre[l-1]。如果这个值等于 k，即pre[r] = pre[l-1] + k。所以遍历前缀和数组时，用一个哈希表记录每个前缀和值出现的次数，每到一个位置 r，看之前有多少个pre[l-1]等于pre[r] - k，它对应的就是多少个和为 k 的合法子数组。

这个题目看起来和差分区无关，但它让我意识到：前缀和数组本身作为“历史记录”，配合其他数据结构可以衍生出大量算法变体。

6.3 什么时候该换树状数组或线段树

差分和前缀和不是万能的。它们的共同弱点是只适合“静态”场景——要么先更新完再查，要么先查完静态数据再更新。如果需要“边更新边查询”，也就是每次区间更新后立刻回答一个区间求和查询，差分+前缀和就无法在每次操作后都保持 O(1) 的查询性能，因为重新构建前缀和是 O(n) 的。

这种场景需要树状数组或线段树。树状数组支持单点更新、区间求和，配合差分技巧也能做区间更新、区间求和；线段树功能更全，但代码量大。我给一个简单的选择建议：如果操作只有区间加、最后输出，用差分；如果先全部加完再多次查询，用差分+前缀和；如果边更新边查询，用线段树或树状数组；如果既有区间更新又有区间查询且是二维，可以考虑二维树状数组，但实现复杂度会陡增，很多时候先看题意是否允许离线处理，离线允许就用差分加前缀和，代码简单得多。

我之前带过一个同学做一道二维区间更新题，第一版他直接上了二维线段树，写了三百多行，改 bug 改到凌晨。后来我提醒他注意题目里“所有更新操作结束之后再统一查询”这个条件，他换成二维差分加二维前缀和，代码五十分钟写完，不仅通过速度更快，而且理解起来也直观得多。做算法题选工具时，复杂度固然重要，但“够用”才是第一原则，能用三个点的差分解决，就不要上三十行的数据结构。

二维差分的四个标记如果配合前缀和一起用，还有个容易记的顺口溜：左上加，右上减，左下减，右下加。写代码之前先把这四个点写在注释里，后面即使操作多，也不会把坐标对应错。实际跑数据的时候，先用小规模矩阵手推验证一遍，确认标记方向没有问题，再放大数据。传统做法里“先画坐标系、再标传播源”的思路，其实可以用在任何需要理解二维扩散的算法里。