前缀和与差分 知识点讲解

概念

前缀和与差分是解决数组区间问题的两大神器。想象一下，你有一排排好队的士兵（数组），指挥官经常问：“从第 3 个到第 7 个士兵，一共站了多少人？”如果每次都要数一遍，当队伍有 10 万人，指挥官问了 10 万次，那得数 100 亿次，电脑会累死的。

前缀和就是为了解决“反复问区间和”这个问题。它的核心思想是：把“前 k 个人的总和”提前算好存起来。以后指挥官再问“第 l 到 r 个人”，你只需要用“前 r 个人的总和”减去“前 l-1 个人的总和”，O(1) 秒出答案。

差分是前缀和的逆运算。它解决的是“反复改区间”的问题。比如指挥官命令：“把第 3 到第 7 个士兵都加发一条毛巾”。如果每次都真的去改那 5 个人的数据，改 10 万次就是 50 万次操作。差分的方法是：只在第 3 个人和第 8 个人（r+1）身上做记号，最后统一结算。这样改区间只需 O(1)，最后还原一次数组 O(n)。

触发清单（看到这些信号第一时间想到本知识点）

定义

一维前缀和

设原数组为 a[1..n]。定义前缀和数组 pre，其中 pre[i] 表示从第 1 个到第 i 个数的总和。

pre[0] = 0; //  必须留 pre[0]，方便处理 l=1 的情况
for (int i = 1; i <= n; i++) pre[i] = pre[i-1] + a[i];

为什么必须留 pre[0] = 0：

前缀和公式 pre[i] = a[1] + a[2] + … + a[i]。当我们要算区间 [l, r] 的和时，利用“两段重叠部分相减归零”的原理：

pre[r] = a1 + a2 + … + a(l-1) + al + … + ar
pre[l-1] = a1 + a2 + … + a(l-1)
pre[r] - pre[l-1] = (al + … + ar) ← 前面那串 a1..a(l-1) 出现两次，相减正好抵消

所以 [l, r] 的和 = pre[r] - pre[l-1]。

注意：当 l = 1 时，pre[l-1] 就是 pre[0]。如果数组下标从 1 开始且没留 pre[0]，这一步会越界或算错。留 pre[0] = 0 后，[1, r] 和 [l, r] 用同一个公式，不用特判。

一维差分（a 是原数组）

定义差分数组 d，其中 d[i] = a[i] - a[i-1]（相邻两项之差）。

d[i] = a[i] - a[i-1]; // 构造差分数组

对原数组做「区间 [l, r] 全部加上 v」，等价于只改差分数组的两个位置：

d[l] += v;
d[r+1] -= v; // 最后对 d 求前缀和，就还原出新的 a

为什么只改两个点：

设原数组 a，差分数组 d[i] = a[i] - a[i-1]。对原数组做「[l, r] 全部 +v」：

• 位置 l 之前的相邻差 a[i]-a[i-1] 没变（两边同加 v）；
• 位置 l 处：a[l] - a[l-1] 因为 a[l] 加了 v 而 变大 v → 只动 d[l]；
• 位置 r+1 处：a[r+1] - a[r] 因为 a[r] 加了 v 而 变小 v → 只动 d[r+1]；
• 区间内部相邻差完全不变。

所以只要 d[l] += v; d[r+1] -= v 两个点。最后对 d 求一次前缀和（pre 是 d 的前缀和 = 原数组）就还原出新 a。“只改边界”是因为区间加只在两个边界改变了相邻差。

两者的关系（一句话记住）：

差分数组求前缀和 = 原数组；原数组求差分 = 差分数组。它们互为逆运算——这也是为什么「区间加完再求前缀和」能还原。

二维前缀和（容斥原理）：

对于矩阵 a[1..n][1..m]，定义 pre[i][j] 为左上角 (1,1) 到 (i,j) 的矩形和。

pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]; // 多减了一块，加回来

子矩阵 (x1, y1) 到 (x2, y2) 的和，利用容斥：

pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]

（加两遍、减一遍、再加回一小块）

技巧速查表（背下来）

原讲义配图

例题

例 1：区间和查询

题目描述：

给定一个长度为 $n$ 的整数数组 $a$（下标从 1 开始），接下来有 $m$ 次询问。每次询问给出两个整数 $l$ 和 $r$，要求输出区间 $[l, r]$ 内所有数的和。

数据范围：$n, m \le 10^5$，$a_i \le 10^9$。

审题分析：

1. 读题抓条件：有 $n$ 个数，要回答 $m$ 次区间和查询。

2. 定需求：直接暴力每次循环加一遍，复杂度 $O(n \times m)$。当 $n=m=10^5$ 时，总操作数 $10^{10}$，必然超时。

3. 为什么能用本知识点：题目是典型的“多次问区间和”，且没有修改操作。这正是前缀和最擅长的场景。

4. 如果不用会怎样：如果不预处理，每次都要 $O(n)$ 计算，无法在规定时间内完成。

解题思路：

1. 定义前缀和数组 pre，pre[i] 表示 $a[1 \dots i]$ 的和。

2. 预处理：pre[0] = 0，然后 pre[i] = pre[i-1] + a[i]。

3. 对于每次询问 $[l, r]$，答案直接是 pre[r] - pre[l-1]。

4. 注意数据范围：$a_i$ 最大 $10^9$，$n$ 最大 $10^5$，总和可能达到 $10^{14}$，必须使用 long long 防止溢出。

C++ 完整参考代码：

#include <iostream>
#include <vector>
using namespace std;

int main() {
 // 优化输入输出效率
 ios::sync_with_stdio(false);
 cin.tie(nullptr);

 int n, m;
 if (!(cin >> n >> m)) return 0;

 // 使用 long long 防止前缀和溢出 (n=1e5, a[i]=1e9 -> sum=1e14)
 vector<long long> pre(n + 1, 0); 

 // 读入数组并构建前缀和
 // pre[0] 必须初始化为 0，方便处理 l=1 的情况
 for (int i = 1; i <= n; i++) {
 long long a;
 cin >> a;
 pre[i] = pre[i - 1] + a;
 }

 // 处理 m 次询问
 for (int i = 0; i < m; i++) {
 int l, r;
 cin >> l >> r;
 // 区间 [l, r] 的和 = pre[r] - pre[l-1]
 // 因为 pre[l-1] 已经存好了前 l-1 个数的和，相减即可
 long long ans = pre[r] - pre[l - 1];
 cout << ans << "\n";
 }

 return 0;
}

代码解读：

• pre 数组大小为 n+1，下标从 1 到 n 对应题目中的位置，0 号位置留空为 0。
• 循环中 pre[i] = pre[i-1] + a 实现了前缀和的递推。
• 查询部分 pre[r] - pre[l-1] 是核心公式，时间复杂度 O(1)。
• 运行结果（假设输入）：

5 3
3 1 4 1 5
1 5
1 3
2 4

输出：

14
9
6

验证：[1,5] 和为 $3+1+4+1+5=14$；[1,3] 和为 $3+1+4=8$（等等，代码输出是 9？让我重新算一下：3+1+4=8。啊，题目给的序列是 3,1,4,1,5。pre[1]=3, pre[2]=4, pre[3]=8, pre[4]=9, pre[5]=14。查询 [1,3] 应该是 pre[3]-pre[0] = 8-0 = 8。但我上面的模拟输出写错了，应该是 8。再检查一遍：3+1+4=8。好的，修正输出为 8。查询 [2,4] 是 pre[4]-pre[1] = 9-3 = 6。正确。

修正后的运行结果：

14
8
6

例 2：差分还原

题目描述：

有一个长度为 $n$ 的数组 $a$，初始时所有元素都为 0。接下来有 $m$ 次操作，每次操作给出 $l, r, v$，表示将区间 $[l, r]$ 内的所有数都加上 $v$。所有操作完成后，输出最终的数组。

数据范围：$n, m \le 10^5$，$v \le 10^9$。

审题分析：

1. 读题抓条件：初始全 0，多次区间加，最后输出结果。

2. 定需求：如果每次操作都真的去遍历区间加，复杂度 $O(n \times m)$，同样会超时。

3. 为什么能用本知识点：题目是“多次区间加，改完才问”，这是差分的典型应用场景。

4. 如果不用会怎样：暴力模拟会超时；如果边改边问，差分就不够用了，需要树状数组或线段树。

解题思路：

1. 定义差分数组 d，大小为 n+2（因为 r+1 可能等于 n+1）。

2. 每次操作 [l, r] += v，只执行 d[l] += v 和 d[r+1] -= v。

3. 所有操作结束后，对 d 求前缀和，得到的就是最终的数组 $a$。

4. 注意 $v$ 很大，中间计算和最终结果都可能超过 int 范围，必须用 long long。

C++ 完整参考代码：

#include <iostream>
#include <vector>
using namespace std;

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

 int n, m;
 if (!(cin >> n >> m)) return 0;

 // 差分数组开 n+2，防止 r+1 越界
 vector<long long> d(n + 2, 0);

 // 第 1 步：处理所有区间加操作（只改两个点）
 for (int i = 0; i < m; i++) {
 int l, r;
 long long v;
 cin >> l >> r >> v;
 d[l] += v;
 d[r + 1] -= v; // ️ r+1 最大是 n+1，数组多开一位
 }

 // 第 2 步：求前缀和还原出最终数组
 long long cur = 0;
 for (int i = 1; i <= n; i++) {
 cur += d[i];
 cout << cur << (i == n ? "" : " ");
 }
 cout << "\n";

 return 0;
}

代码解读：

• d 数组初始化为 0，对应题目初始全 0 的条件，省去了构造差分数组的步骤。
• 循环中 d[l] += v; d[r+1] -= v; 是差分的核心操作。
• 最后 cur += d[i] 是对 d 求前缀和，还原出真实的数组值。
• 运行结果（假设输入）：

5 2
1 3 2
2 5 1

输出：

2 3 3 1 0

验证：

• 初始 [0,0,0,0,0]
• [1,3] +2 → [2,2,2,0,0]
• [2,5] +1 → [2,3,3,1,1]
• 等等，最后一个是 1？让我重新算：位置 5 只被第二个操作覆盖，加 1，所以是 1。但我上面的代码输出是 0？啊，我模拟错了。d[5] 是 d[5] += 1（来自第二个操作），d[6] -= 1。d 数组：d[1]=2, d[2]=2, d[3]=2, d[4]=-2, d[5]=1, d[6]=-1。前缀和：cur[1]=2, cur[2]=4, cur[3]=6, cur[4]=4, cur[5]=5。这也不对。让我重新手动推演差分过程：

- 操作 1: l=1, r=3, v=2 → d[1]+=2, d[4]-=2 → d=[?, 2, 0, 0, -2, 0, 0]

- 操作 2: l=2, r=5, v=1 → d[2]+=1, d[6]-=1 → d=[?, 2, 1, 0, -2, 0, -1]

- 前缀和还原：

- i=1: cur=2 → a[1]=2

- i=2: cur=2+1=3 → a[2]=3

- i=3: cur=3+0=3 → a[3]=3

- i=4: cur=3-2=1 → a[4]=1

- i=5: cur=1+0=1 → a[5]=1

- 结果应该是 2 3 3 1 1。

- 我之前的代码输出写错了，修正为 2 3 3 1 1。

例题复盘总结

共性特征：

• 所有题目都涉及区间上的批量操作（求和、加法、乘法等）。
• 数据规模通常较大（$n, m \ge 10^5$），暴力模拟必然超时。
• 操作之间相互独立，没有依赖关系（如“修改后立刻查询”这种需要动态维护的场景除外）。

各自技巧：

• 前缀和：核心是“预处理 + O(1) 查询”。关键在于必须留 pre[0]=0，以及下标从 1 开始，这样公式统一，不用特判。
• 差分：核心是“只改两个端点 + 最后还原”。关键在于数组开 n+2，防止 r+1 越界；以及最后一定要求前缀和，否则得到的只是“记账”数据，不是真实数组。
• 前缀配对：核心是“哈希表记录前缀出现次数”。关键在于cnt[0]=1（空前缀），以及用 long long 存前缀和。

审题模板（固定思考流程）：

1. 数一遍“操作次数” —— 只问一次？那直接循环加就行，不用前缀和。问很多次才值得预处理。

2. 区分“查询多”还是“修改多” —— 查询多 → 前缀和；修改多（改完才问）→ 差分；边改边问 → 树状数组/线段树（不是本知识点）。

3. 看到“有多少个子数组”就想到“前缀配对” —— 写成 pre[r] - pre[l-1] = k，再变成 cnt[pre - k]。

4. 差分题先问“最后要不要还原” —— 差分只是记账，必须求一次前缀和才是真数组。

5. 估算数值上界 —— n = 1e5、a[i] 到 1e9 时 pre[n] 到 1e14，一律用 long long。

6. 下标统一从 1 开始 —— 留出 pre[0] 和 d[n+1]，能省掉一堆特判。

错误清单（只列上文没讲过的特有错误）：

• 二维前缀和容斥符号写错：pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]。容易漏掉最后那个 +，导致结果偏小。
• 区间积前缀忘记处理 0：如果数组里有 0，pre[l-1] 可能是 0，求逆元会出错。需要记录 0 的位置分段处理，或者用“前缀 + 后缀”分别预处理。
• 差分题忘记清空 d 数组：在多组测试数据或多次二分检查时，d 数组里的旧数据会干扰新结果，必须 memset 或重新初始化。

写法总表

分工说明：

• 触发清单 告诉你“看到什么信号该想到本知识点”，帮你从题目描述里识别需求。
• 技巧速查表 告诉你“具体怎么写代码”，提供可直接套用的模板。
• 写法总表 把技法按粒度从细到粗分层，让你知道每个技法对应解决哪类问题，以及典型的代码结构是什么。三者配合，形成从“识别”到“实现”的完整闭环。

常见错误

1. 忘了 pre[0] = 0 / 数组下标从 0 开始。 用 pre[l-1] 时 l = 1 会访问 pre[0]，没有留这一位就崩了。统一从 1 开始编号最省心。

2. 差分数组开小了。 d[r+1] 当 r == n 时会用到 d[n+1]，数组要开 n + 2。

3. 差分忘记“还原”。 差分只是“记账”，必须最后求一次前缀和才是真正的数组 —— 忘记这一步是差分题最常见的失分点。

4. 边修改边查询却用差分。 差分不支持“随时问”，需要树状数组/线段树。

5. 前缀和溢出。 n = 1e5 且 a[i] 到 1e9 时，pre[n] 会到 1e14 —— 必须用 long long。这个坑静默出错，极难发现。

6. 二维前缀和的容斥写错符号。 记住形状：加两遍、减一遍、再加回一小块；查询时也是“加两遍减一遍再加回”。

自测

1. 写出前缀和的预处理和取区间和的公式，说明为什么必须留 pre[0]。

2. 对数组做「[l, r] 全部加 v」，差分数组要改哪两个位置？为什么只改两个？

3. 差分数组改完之后，还差哪一步才能得到最终的数组？

举一反三 · 审题流水线

拿到一道区间题，别急着写代码，先让这条流水线跑一遍：

1. 数操作次数：只问一次？直接暴力。问很多次？继续。

2. 看有没有修改：边改边问？换树状数组/线段树。改完才问？继续。

3. 看统计量：和？异或？积？最大值？能“相减”的（和、异或、积）→ 前缀；不能的（最大值）→ 换数据结构。

4. 看计数：有多少个子数组？→ 前缀配对。

5. 估算上界：n=1e5, a[i]=1e9 → long long。

6. 统一下标：pre[0] 和 d[n+1] 预留好，能省特判。

练手题

题 A：区间乘积（取模）

给定 $n$ 个正整数 $a_1, a_2, \dots, a_n$，以及 $m$ 次询问，每次给出 $l, r, MOD$，求区间 $[l, r]$ 所有数的乘积对 $MOD$ 取模的结果。

数据范围：$n, m \le 10^5$，$a_i \le 10^9$，$MOD \le 10^9+7$。

提示：注意 $MOD$ 不是质数时，逆元不一定存在；如果区间里有 0，乘积直接为 0。

题 B：区间异或和

给定 $n$ 个非负整数 $a_1, a_2, \dots, a_n$，以及 $m$ 次询问，每次给出 $l, r$，求区间 $[l, r]$ 所有数的异或和。

数据范围：$n, m \le 10^5$，$a_i \le 10^9$。

提示：异或的逆运算就是它自己，所以区间异或和 = pre[r] ^ pre[l-1]。