[特殊字符] C++ 算法8：前缀和与差分

📚 C++ 算法笔记：前缀和与差分

一、前缀和 (Prefix Sum)

1. 概念介绍
前缀和，顾名思义，就是求一个序列前 n 项的和。它是一种预处理思想，通过预先计算并存储好前缀和，可以将多次“区间求和”查询的时间复杂度从 O(n) 降低到 O(1)，极大地提高了效率。

• 定义：对于一个数组 a，其前缀和数组 s 的第 i 项 s[i] 表示 a 数组中前 i 个元素的和。
  • s[i] = a[1] + a[2] + … + a[i]
• 核心公式：求原数组 a 中区间 [l, r] 的和，可以通过前缀和数组 s 快速计算：
  • sum(l, r) = s[r] – s[l-1]

2. 案例引入：从暴力求解到前缀和优化

问题：给定一个长度为 n 的整数序列，进行 m 次查询。每次查询输入一对 l, r，要求输出原序列中从第 l 个数到第 r 个数的和。

• 暴力解法：
  对于每次查询，都使用一个 for 循环从 l 遍历到 r 并累加求和。

  • 时间复杂度：每次查询需要 O(r-l+1) 的时间，最坏情况下为 O(n)。进行 m 次查询，总时间复杂度为 O(n * m)。当 n 和 m 很大时（例如 10^5），这个复杂度很容易导致超时。

• 前缀和优化：
  我们可以先进行一次预处理，计算出整个数组的前缀和 s。之后，每次查询只需要做一次减法运算。

  • 时间复杂度：预处理需要 O(n) 的时间，每次查询仅需 O(1)。总时间复杂度为 O(n + m)。效率提升显著。

3. 知识点详解

步骤一：预处理，构建前缀和数组
我们定义一个数组 s，其中 s[i] 存储 a[1] 到 a[i] 的

// 假设数组 a 和 s 已经定义，且下标从 1 开始
s[0] = 0; // 边界条件，方便计算
for (int i = 1; i <= n; i++) {
s[i] = s[i-1] + a[i]; // 递推公式
}

这个过程的时间复杂度是 O(n)。

步骤二：进行区间查询
当需要查询区间 [l, r] 的和时，直接使用公式 s[r] – s[l-1]。

// 查询区间 [l, r] 的和
int query(int l, int r) {
return s[r] – s[l-1];
}

这个过程的时间复杂度是 O(1)。

原理
为什么 s[r] – s[l-1] 就是区间 [l, r] 的和呢？

• s[r] = a[1] + a[2] + … + a[l-1] + a[l] + … + a[r]
• s[l-1] = a[1] + a[2] + … + a[l-1]
• 两式相减，s[r] – s[l-1]，前面从 a[1] 到 a[l-1] 的部分就被抵消了，
• 剩下的正好是 a[l] + … + a[r]。

4. 例题与代码实现

题目：输入一个长度为 n 的整数序列，进行 m 次区间和查询。

输入样例:

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

输出样例:

C++ 代码实现:

1#include <iostream>
2#include <cstdio>
3using namespace std;
4
5const int N = 100010; // 根据数据范围定义数组大小
6
7int n, m;
8int a[N], s[N]; // a为原数组，s为前缀和数组
9
10int main() {
11 // 1. 输入数据
12 scanf("%d%d", &n, &m);
13 for (int i = 1; i <= n; i++) {
14 scanf("%d", &a[i]);
15 }
16
17 // 2. 预处理：构建前缀和数组
18 for (int i = 1; i <= n; i++) {
19 s[i] = s[i-1] + a[i];
20 }
21
22 // 3. 处理 m 次查询
23 while (m–) {
24 int l, r;
25 scanf("%d%d", &l, &r);
26 // 4. 利用前缀和公式 O(1) 查询
27 printf("%d\\n", s[r] – s[l-1]);
28 }
29
30 return 0;
31}

二、差分 (Difference)

1. 概念介绍
差分可以看作是前缀和的逆运算。如果说前缀和是为了快速求“区间和”，那么差分就是为了快速进行“区间修改”。它通过构造一个差分数组，将对原数组一个区间的批量修改操作，转化为对差分数组上两个点的修改，从而将时间复杂度从 O(n) 降低到 O(1)。

• 定义：对于原数组 a，其差分数组 b 的第 i 项 b[i] 定义为 a[i] 与 a[i-1] 的差。
  • b[i] = a[i] – a[i-1] (其中 b[1] = a[1])
• 关系：原数组 a 是差分数组 b 的前缀和。即 a[i] = b[1] + b[2] + … + b[i]。

2. 案例引入：高效的区间修改

问题：给定一个长度为 n 的数组 a，进行 m 次操作。每次操作给定 l, r, c，要求将数组 a 中区间 [l, r] 内的所有数都加上 c。最后输出修改后的整个数组。

• 暴力解法：
  对于每次操作，都使用一个 for 循环从 l 遍历到 r，给每个 a[i] 加上 c。

  • 时间复杂度：每次操作 O(n)，m 次操作总复杂度为 O(n * m)。

• 差分优化：
  我们构造 a 的差分数组 b。要将 a 的 [l, r] 区间都加上 c，只需对 b 进行两步操作：b[l] += c 和 b[r+1] -= c。

  • 时间复杂度：每次操作 O(1)，m 次操作后，再通过一次 O(n) 的前缀和运算还原 a 数组。总复杂度为 O(n + m)。

3. 知识点详解

步骤一：构造差分数组

1// 假设数组 a 和 b 已经定义
2b[1] = a[1];
3for (int i = 2; i <= n; i++) {
4 b[i] = a[i] – a[i-1];
5}

步骤二：进行区间修改
要将 a 数组的 [l, r] 区间所有元素加上 c：

最终效果就是只有 a[l] 到 a[r] 的元素增加了 c。

原理
想象一条数轴，b[l] += c 相当于在 l 位置施加了一个 +c 的力，这个力会一直传递到数组末尾。为了在 r 位置停止这个力的作用，我们在 r+1 位置施加一个 -c 的力来抵消它。

步骤三：还原原数组
所有修改操作完成后，对差分数组 b 求前缀和，即可得到最终的原数组 a。

1for (int i = 1; i <= n; i++) {
2 a[i] = a[i-1] + b[i]; // 此时 a[i] 已被更新为最终值
3}

4. 例题与代码实现

题目：(AcWing 797. 差分) 对数组进行 m 次区间加法操作，输出最终数组。

输入样例:

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例:

3 4 5 3 4 2

C++ 代码实现:

1#include <iostream>
2#include <cstdio>
3using namespace std;
4
5const int N = 100010;
6
7int n, m;
8int a[N], b[N]; // a为原数组，b为差分数组
9
10int main() {
11 scanf("%d%d", &n, &m);
12
13 // 1. 输入原数组并构造差分数组
14 for (int i = 1; i <= n; i++) {
15 scanf("%d", &a[i]);
16 b[i] = a[i] – a[i-1];
17 }
18
19 // 2. 处理 m 次区间修改操作
20 while (m–) {
21 int l, r, c;
22 scanf("%d%d%d", &l, &r, &c);
23 b[l] += c; // 区间起点 +c
24 b[r+1] -= c; // 区间终点后一位 -c
25 }
26
27 // 3. 通过差分数组还原并输出最终的原数组
28 for (int i = 1; i <= n; i++) {
29 a[i] = a[i-1] + b[i]; // a[i] 此时存储了最终结果
30 printf("%d ", a[i]);
31 }
32
33 return 0;
34}

三、差分应用案例：海底高铁

这是一个利用差分思想解决实际问题的经典案例。

问题简述：
有 n 个城市排成一排，有 n-1 段铁路连接相邻城市。你需要按顺序访问 m 个城市。对于每段铁路，你可以选择买纸质车票，也可以办一张IC卡。目标是求出完成所有行程的最小花费。

核心思路：

C++ 代码实现:

1#include <iostream>
2#include <cstdio>
3#include <algorithm> // 用于 min 函数
4using namespace std;
5
6typedef long long ll; // 使用 long long 防止结果溢出
7
8int main() {
9 ll n, m, ans = 0;
10 scanf("%lld%lld", &n, &m);
11
12 ll p[m+1]; // 存储访问城市的顺序
13 ll t[n+1] = {}; // 差分数组，记录每段路的访问次数，初始化为0
14 ll a[n+1], b[n+1], c[n+1]; // a:票价, b:IC卡扣费, c:工本费
15
16 // 输入访问顺序
17 for (ll i = 1; i <= m; i++) {
18 scanf("%lld", &p[i]);
19 }
20 // 输入每段铁路的费用信息
21 for (ll i = 1; i <= n-1; i++) {
22 scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
23 }
24
25 // 1. 使用差分思想标记每段路的访问次数
26 for (ll i = 1; i <= m-1; i++) {
27 ll x = p[i], y = p[i+1];
28 if (x > y) swap(x, y); // 保证 x 是起点，y 是终点
29
30 t[x]++; // 从第 x 段路开始，次数+1
31 t[y]–; // 到第 y 段路结束，次数-1 (差分标记)
32 }
33
34 // 2. 对差分数组求前缀和，得到每段路的实际访问次数
35 for (ll i = 1; i <= n; i++) {
36 t[i] += t[i-1];
37 }
38
39 // 3. 计算总花费
40 for (ll i = 1; i <= n-1; i++) {
41 // 比较两种方案，取最小值
42 ans += min(a[i] * t[i], b[i] * t[i] + c[i]);
43 }
44
45 printf("%lld", ans);
46 return 0;
47}