前缀和与差分算法详解：一维二维公式、模板与常见错误

一提起前缀和与差分，很多刚接触算法题的朋友都觉得太简单了：一个维护累计和，一个维护变化量，公式背下来不就行了？可实际刷题时，二维公式写反、下标越界、差分数组开小一格的报错比比皆是。也许你搜“差分”时看到的更多是差分放大电路、差分隐私、PCB差分走线这些词，这些都不是我们今天的主角。我们要聊的是信息学奥赛、蓝桥杯、考研机试和互联网笔试里最常用的那对技巧：前缀和与差分。

这篇文章不做高深推导，就把一维、二维的前缀和和差分讲透，包括公式为什么长这样、代码模板怎么写、常见的坑在哪。读完你至少能直接上手做区间求和、区间加、二维矩阵和这类题。

1. 先从一道最经典的题说起

1.1 暴力做法的复杂度瓶颈

先看一个几乎每个刷题人都遇到过的场景：给定一个长度为 n 的整数数组 a，有 m 次询问，每次给两个下标 l 和 r，要求输出 a[l] 到 a[r] 的和。n 和 m 都能到 1e5 甚至 1e6。

最朴素的做法是每次询问都写一个循环，从 l 遍历到 r 做累加。代码非常简单，可一旦 n 和 m 都很大，比如各 1e5，最坏情况下每次询问都遍历近乎整个数组，总计算量就是 1e10 次加法。一台普通评测机每秒大概能跑 1e8 次运算，1e10 意味着几十秒甚至更久，妥妥的超时。

很多人第一反应是“优化循环，比如少算一点”，但这方向不对。暴力做法的问题不是循环本身笨，而是同一个元素被反复加了太多次。举个例子，a[2] 这个数，可能第一个询问加一次，第二个询问又加一次，第十个询问再加一次，做过 1e5 次重复劳动。更好的思路是预处理一份“账本”，把常用结果提前算好存下来，让每次询问都只做一次常数运算。

1.2 用一个账本搞定所有区间和

这个预处理的账本就是前缀和数组。定义 s[i] 表示数组前 i 个元素的和，也就是：

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

可以把它理解成一个累计账本：第一天收入 a[1]，第二天累计到 s[2]，第 i 天累计到 s[i]。如果想知道从第 l 天到第 r 天一共收入多少，只需要用 s[r] 减去 s[l - 1]。

为什么是 s[l - 1] 而不是 s[l]？因为 s[l] 里已经包含了第 l 天的钱，减掉它就会把第 l 天也减没，答案会比正确值少一个 a[l]。这个细节是新手最常踩的第一个坑，后面我会专门说边界问题。

有了前缀和数组，每次区间和查询就是：

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

构造前缀和数组需要 O(n) 时间，之后每次查询都是 O(1)。这就是典型的空间换时间：用 O(n) 的额外空间，把单次查询从 O(n) 降到 O(1)。当 n 和 m 都在 1e5 量级时，这个优化是从超时到秒过的最根本差距。

2. 一维前缀和：公式、边界与代码模板

2.1 从1开始的构造方式与区间求和公式

竞赛题里的数组下标，强烈建议从 1 开始存数据。原因很简单：s[0] 天然等于 0，查询 l = 1 的时候，s[l - 1] 就是 s[0]，不需要特判。

构造方式是这样：

cpp复制int n;
cin >> n;
vector<long long> s(n + 1, 0);
for (int i = 1; i <= n; i++) {
    long long x;
    cin >> x;
    s[i] = s[i - 1] + x;
}

这里有一个常被忽略的点：其实不需要用数组把原来的 a 存下来。输入一个数，就立刻累加到前缀和数组里，后面查询时直接查 s 就行。只有在某些题目还需要回看原始数组时，才有必要另开数组保存。

如果输入之后还要用原数组做别的操作，那就先存 a，再构造 s：

cpp复制for (int i = 1; i <= n; i++) {
    s[i] = s[i - 1] + a[i];
}

区间求和查询：

cpp复制while (m--) {
    int l, r;
    cin >> l >> r;
    cout << s[r] - s[l - 1] << '\n';
}

2.2 前缀和为什么能O(1)回答

这个问题拆开看就是小学算术：

s[r] = a[1] + a[2] + ... + a[r]
s[l - 1] = a[1] + a[2] + ... + a[l - 1]

上下相减，左边连续相同的前 l - 1 项全部抵消，剩下的正好是：

a[l] + a[l + 1] + ... + a[r]

这个过程没有循环、没有累加，只是两次数组取值、一次减法。所谓“O(1) 回答”就是指这样：不管区间有多长，也不管数组多大，只要前缀和已经构造好，每次查询付出的时间都是一样的。

从更抽象的角度看，前缀和的核心是预处理 + 容斥。一维是简单的减法，二维前缀和就变成减法加回，再往后扫线、树状数组、线段树里也到处都有这种“先预处理、后差分/容斥”的影子。

2.3 一个容易忽略的边界：s[0] 必须保留

很多人觉得 s[0] 没意义，就不初始化。但当下标从 1 开始时，s[0] 是查询区间 [1, r] 时不可或缺的减数。s[0] 应当被设置为 0，表示前 0 个元素的和。

如果反过来用 0 下标存储数组，查询 [0, r] 时就会遇到 s[-1] 越界的问题。要么特判，要么把数组整体下标偏移。很多新手两种写法混着用，同一个程序里一会从 0 开始一会又从 1 开始，最后 debug 到怀疑人生。所以我的建议是：在竞赛和平时的练习里，固定使用从 1 开始的写法，把下标选择变成肌肉记忆。

3. 差分：区间修改的“逆运算”武器

3.1 差分的定义：原数组本来就是前缀和

差分和前缀和是倒数关系：对一个数组做一次差分，得到差分数组；对差分数组做一次前缀和，又得到原数组。

设原数组为 a，定义差分数组 d：

d[i] = a[i] - a[i - 1]

其中 a[0] = 0。那么对 d 求前缀和：

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

举个例子：a = [1, 2, 3, 4, 5]，它的差分就是 [1, 1, 1, 1, 1]。因为每个数都比前一个数大 1。如果对差分数组做前缀和，1, 1+1=2, 1+1+1=3，又能回到 1, 2, 3, 4, 5。这就像温度计记录每天温度的变化量，把所有变化量累加，就能还原出每天的温度。

那这个东西有什么用？它最大的价值是：区间统一“加同一个数”这个操作，可以只改两个地方，最后再做一次前缀和还原。

3.2 区间加一个数，为什么只改两个位置

现在有这样一个需求：执行若干次区间加操作，每次把数组 [l, r] 范围内的每个数加上 v，所有操作结束后求最终的数组。

如果直接模拟，每次 O(n)，总复杂度 O(nm)，不可行。但用差分数组，每次操作只需要两句话：

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

然后操作结束后，对 d 做一次前缀和，就能得到最终数组。

为什么这两句话就能表示整个区间都加 v？因为对差分数组求前缀和时，d[l] 从 l 位置开始会影响后面所有位置；而 d[r + 1] 从 r + 1 位置开始会抵消前面的 v。两者叠加，真正被影响的范围恰好是 [l, r]。

我用一个具体例子验证。原数组 a = [1, 2, 3, 4, 5]，构造差分 d = [1, 1, 1, 1, 1]。现在想要 [2, 4] 区间内每个数加 2，于是：

d[2] += 2，得到 [1, 3, 1, 1, 1]
d[5] -= 2，得到 [1, 3, 1, 1, -1]

再对这个差分数组做前缀和：

i=1：1
i=2：1 + 3 = 4
i=3：1 + 3 + 1 = 5
i=4：1 + 3 + 1 + 1 = 6
i=5：1 + 3 + 1 + 1 - 1 = 5

得到 [1, 4, 5, 6, 5]，正好是原数组 [1, 2, 3, 4, 5] 在区间 [2, 4] 每个数加 2 的结果：第2个 2+2=4，第3个 3+2=5，第4个 4+2=6。完美对上了。

这里要特别注意：减的位置一定是 r + 1，不是 r。如果在 r 位置减，那么第 r 个元素也会被减掉，最终只有 [l, r-1] 加了 v。很多人第一次写差分，都会栽在这个加一上。

3.3 一维差分完整模板

最标准的模板长这样：

cpp复制#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<ll> a(n + 1), diff(n + 2, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 构造差分数组
    for (int i = 1; i <= n; i++) {
        diff[i] = a[i] - a[i - 1];
    }

    // m 次区间加
    while (m--) {
        int l, r;
        ll v;
        cin >> l >> r >> v;
        diff[l] += v;
        diff[r + 1] -= v;
    }

    // 对差分数组做前缀和，还原最终数组
    for (int i = 1; i <= n; i++) {
        a[i] = a[i - 1] + diff[i];
        cout << a[i] << (i == n ? '\n' : ' ');
    }
    return 0;
}

注意 diff 数组的长度开到了 n + 2，因为当 r = n 时，diff[r + 1] 会访问到 diff[n + 1]，如果数组只开 n+1，这里就越界了。多开一位不是浪费，是必要的安全垫。

如果原数组初始全是 0，那就更简单了，连构造差分数组那步都可以省掉，直接对全 0 的 diff 做区间加，最后前缀和就是答案。

4. 二维前缀和与二维差分

4.1 二维前缀和的容斥原理

一维前缀和好用，二维稍微绕一点，但核心还是那个“预处理 + 容斥”。

二维前缀和 s[i][j] 表示：从矩阵左上角 (1,1) 到 (i,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] 表示左方一整块，两块都包含了左上角的公共部分 s[i - 1][j - 1]。直接加会把公共部分算两遍，所以必须减掉一次。这就像计算图形面积时，两个区域重叠的部分不能重复计入，必须减一次。

用一段二维的 C++ 代码构造：

cpp复制vector<vector<ll>> s(n + 1, vector<ll>(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];
    }
}

4.2 二维区域和查询公式

如果需要查询左上角为 (x1, y1)、右下角为 (x2, y2) 的子矩阵和，公式是：

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

这个公式看起来很怪，其实还是容斥：先取整块大矩阵，然后减掉上方区域 s[x1 - 1][y2]，再减掉左方区域 s[x2][y1 - 1]。但上方和左方的公共部分 s[x1 - 1][y1 - 1] 被减了两次，所以最后要加回来。

记忆技巧是：参与运算的四个点分别是 (x2,y2)、(x1-1,y2)、(x2,y1-1)、(x1-1,y1-1)，符号依次是加、减、减、加。只要记住“右下 +，上边界 -，左边界 -，左上重叠加回”，公式就不容易写错。

我强烈建议你在纸上画一个 3 乘 3 的矩阵，手写一次 s[3][3] 到 s[2][2] 的过程。这一步花不了两分钟，但比死记公式可靠得多。

4.3 二维差分：四个点就能搞定矩形修改

二维差分解决的问题是：多次把一个子矩形内所有元素加上同一个数 v，最后要输出整个矩阵。

直接暴力每次 O(nm) 不可行，但用二维差分可以把一次矩阵修改降为 O(1)。对左上角 (x1, y1)、右下角 (x2, y2) 的矩形加 v，只需要对差分数组 d 做四个操作：

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

最后对 d 做一遍二维前缀和，得到的就是加完所有操作后的最终矩阵。

为什么是这四个点？你可以这样理解：二维前缀和一旦开始累加，就会向右下角方向“传播”。d[x1][y1] 加 v 之后，所有从该点右下方向的格子都会加上 v，但影响范围远大于我们想要的那个矩形。为了“截住”过深的行，在 x2 + 1 这一行的 y1 位置减 v；为了“截住”过宽的列，在 y2 + 1 这一列的 x1 位置减 v。可这两个截断操作在右下角区域发生了重叠，相当于减了两次，所以还要在 (x2+1, y2+1) 位置加 v，把多减的那次补回来。

模板是这样的：

cpp复制int n, m;
cin >> n >> m;
vector<vector<ll>> diff(n + 2, vector<ll>(m + 2, 0));

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

// 若干次 add 操作...

// 二维前缀和还原
vector<vector<ll>> res(n + 2, vector<ll>(m + 2, 0));
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        res[i][j] = res[i - 1][j] + res[i][j - 1] - res[i - 1][j - 1] + diff[i][j];
    }
}

这里 diff 数组必须开 (n + 2) * (m + 2)，因为修改时会用到 x2 + 1 和 y2 + 1，可能等于 n + 1 或 m + 1。开小了会越界，而且这种越界往往是玄学错误，很不方便查。

5. 实战：三类高频题的代码模板

5.1 静态区间和：洛谷 P8218 模板

洛谷的 P8218 是一道非常标准的一维前缀和模板题。题意就是给一个数组，多次询问区间和。

我的 AC 写法：

cpp复制#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> s(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        s[i] = s[i - 1] + x;
    }

    int m;
    cin >> m;
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << '\n';
    }
    return 0;
}

这题的坑主要就是结果可能超过 int 范围。n 到 1e5，每个数可以到 1e9，整个区间的和最高到 1e14，用 int 直接溢出变成负数，然后 WA 得莫名其妙。所以不管题目给的数据看起来多大，一看到需要累加和，我第一反应就是 long long。

5.2 一维区间加+最终数组：经典差分题

洛谷 P2367 语文成绩这类题就是典型的差分模板：初始给一个数组，多次把区间 [l, r] 内的成绩统一加上某个分，最后求最低分。

有了差分，解法就很固定：

1. 对初始数组构造差分数组。
2. 每次区间加，只改 l 和 r + 1 两个位置。
3. 所有操作结束后，对差分数组做前缀和还原得到最终数组。
4. 遍历最终数组找最小值。

核心片段：

cpp复制vector<ll> a(n + 1), diff(n + 2, 0);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) diff[i] = a[i] - a[i - 1];

while (m--) {
    int l, r;
    ll v;
    cin >> l >> r >> v;
    diff[l] += v;
    diff[r + 1] -= v;
}

ll ans = LLONG_MAX;
ll cur = 0;
for (int i = 1; i <= n; i++) {
    cur += diff[i];
    ans = min(ans, cur);
}
cout << ans << '\n';

这个模板可以应对几乎所有“离线区间加”的题。记住：只要题目的描述是“多次修改，最后一次性查询结果”，就先想差分，不要上来就线段树。

5.3 二维矩阵区域和与矩形加

LeetCode 304 是二维前缀和模板题，输入是一个二维矩阵，多次查询不同子矩阵的和。因为它给的接口是从 0 开始的下标，我习惯在外层包一层偏移，使下标从 1 开始。

初始化：

cpp复制vector<vector<ll>> s(n + 1, vector<ll>(m + 1, 0));
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + matrix[i][j];
    }
}

查询：

cpp复制return s[row2 + 1][col2 + 1] - s[row1][col2 + 1] - s[row2 + 1][col1] + s[row1][col1];

这里把原矩阵的 (row,col) 映射到前缀和数组的 (row+1,col+1)，查询时右下角要 +1，左上角不变，其实就是在用从 1 开始的模板。这个偏移思想在接口固定为 0 下标时非常实用。

二维差分的模板题可以看洛谷 P3397 地毯。题目给一个 n×n 的网格，m 次操作每次给一个矩形覆盖范围，要求最终输出每个格子上覆盖了多少次。做法就是二维差分加二维前缀和还原，直接套上面的 add 函数。

6. 常见错误与排查实录

6.1 下标从0还是从1，这个问题天天有人错

我几乎每次答疑都会遇到下标混用的问题。常见症状是：区间和答案总是差一点，或者某些询问一错全错。

从 1 开始和从 0 开始都是可行的，但必须统一。我的建议很简单：竞赛、练习、自己写工具类，一律从 1 开始，s[0] 初始化为 0。为什么？区间查询可以写成 s[r] - s[l - 1]，不需要任何 if，不需要担心负数下标，修改时也有 r + 1 的位置可以自然多开一位。

个人体会是：自己写题用从 1 开始的模板，调用别人接口时就老老实实包一层偏移，不要在同一个程序里“灵机一动”换下标。

6.2 数组越界与整数溢出

下面这张表是我在实际做题中总结出来的高频问题，基本可以当速查表用：

另外，输入输出加速也不能忘。C++ 里 ios::sync_with_stdio(false); cin.tie(nullptr); 很多人不写，输入量大时直接卡超时。Python 用户则要善用 sys.stdin.buffer.read() 这类快速输入方式。

6.3 到底什么时候用前缀和，什么时候用差分

这个问题适合用一句话判断：前缀和解决“多次询问区间和”的问题，思路是把原始数组转成累计数组；差分解决“多次区间修改，最后求数组”的问题，思路是记录变化量再还原。

更直白的口诀：

• 看到“多次询问某一段的和/某一个矩阵的和”，先想前缀和。
• 看到“多次把某个区间/矩阵统一加一个数，最后输出结果”，先想差分。
• 看到“区间加 + 单点查询”，直接差分后前缀和还原。
• 看到“区间加 + 区间查询”，差分数组只能解决一半，通常要配合树状数组或线段树，但这是后话。

本质上，前缀和和差分是一枚硬币的两面：前缀和把“一段区间的结果”提前存下来，差分把“一段区间的影响”压缩成两个边界事件。这两个思想在之后的树状数组、扫描线、线段树的懒标记中都会反复出现，所以现在花点时间把公式和边界磨透，是非常值得的。

最后说点个人体会。我见过不少零基础的朋友，公式背得滚瓜烂熟，可真到做题还是写错，原因基本都在下标。所以我自己的习惯是：先写 s[0] = 0，输入从 1 开始，任何区间查询都写成 s[r] - s[l - 1]，不做特判。这一个习惯帮我省下大量调 bug 的时间。还有一个小技巧：遇到二维问题时，先用一个 2×3 的矩阵手推一遍公式，再改代码，比硬记四个点可靠得多。如果你想把这些思路扩展出去，接下来可以试试树状数组和线段树，你会发现前缀和的影子无处不在。