C++ 算法讲义：前缀和

第一部分：问题引

1. 场景模拟：高频区间查询

假设这样一个数据处理场景：班级里有 100,000 名学生站成一排，已知每个人的考试分数。

此时，班主任频繁提出查询需求：“第 3 名到第 25 名学生的总分是多少？”

最直观的解法是编写一个 for 循环，将区间内的分数逐一累加。

但这仅仅是单次查询。如果系统在极短时间内（例如 1 秒内）发起了 10 万次不同区间的查询请求（如“第 10 到 80 名”、“第 2 到 99,999 名”），会发生什么？

2. 暴力解法的缺陷分析

如果每次询问都通过 for 循环遍历相加，单次查询的时间复杂度为 $O(N)$。如果有 M 次查询，总时间复杂度将高达 $O(N \cdot M)$。

在 N 和 M 均为 100,000 的量级下，程序需要执行约 100 亿次运算，这在任何算法竞赛都会导致超时（TLE）。

除时间复杂度高之外，暴力解法的核心缺陷在于存在大量的重复计算。

例如，程序刚刚计算完“第 2 名到第 6 名”的总和，紧接着又要计算“第 2 名到第 5 名”的总和。在暴力解法中，程序会无视之前的计算成果，将第 2 到第 5 名的数据重新遍历累加一遍。

思考：

是否存在一种算法结构，能够将计算过的中间结果缓存下来，消除重复遍历？无论查询的区间跨度有多大，都能在常数时间 $O(1)$ 内直接返回答案？

第二部分：类比思考

想象你正驾驶汽车行驶在一条笔直的高速公路上。这条公路被划分为了多个路段。

真实路段（原数组 $a$）：每一段路都有其独立的长度。例如第 1 段路长 10 公里，第 2 段路长 20 公里。
累计里程碑（前缀和数组 $S$）：在每一段路结束的终点处，都设立了一块里程碑，上面记录着“从公路起点行驶至此的总里程”。
- 驶出第 1 段路时，里程碑标记为 10。
- 驶出第 2 段路时，里程碑标记为 30（即 10 + 20）。

第 i 个里程碑的位置，对应第 i 段路的终点。

第三部分：推导公式

现在，我们需要计算**“第 3 段路 + 第 4 段路 + 第 5 段路”**的总长度（即求原数组区间 [3, 5] 的和）。

依据直觉，许多初学者会尝试直接使用两端的里程碑相减：用第 5 个碑的读数减去第 3 个碑的读数。

直觉陷阱剖析：

如果你以“第 3 个碑”作为起点进行计算，请注意你当前所处的位置：你在第 3 段路的终点！

如果你从这里开始计算距离，你所包含的第一段路将是第 4 段路。这样一来，第 3 段路的长度被完全遗漏了。

为了确保计算结果完整包含第 3 段路，我们的计算基准点必须设置在第 3 段路的起点。

而在累计里程碑系统中，第 3 段路的起点，在物理位置上等同于第 2 段路的终点，即第 2 个里程碑所在的位置。

因此，计算第 3 到第 5 段路总距离的正确等式为：

第 5 个里程碑的读数 - 第 2 个里程碑的读数。

抽象为通用算法公式：

若需求取原数组从第 L 个元素到第 R 个元素的总和，设前缀和数组为 $S$：
- 区间的终点标记为：$S[R]$。
- 区间的起点标记（必须是第 L 段开始前的位置）为：$S[L-1]$。
- 区间查询公式：
  Sum(L, R) = S[R] - S[L-1]

第四部分：前缀和数组与如何高效求取？

而我们刚才反复提到的那个用来记录里程碑的数组 𝑆[]，其实就叫做： —— 前缀和数组 (Prefix Sum Array)

简单的来说，前缀和数组就是一个用来存储累加和的辅助数组。

那么如何在程序中高效地生成这个 S 数组（即建立所有的里程碑）呢？

在构建第 i 个里程碑时，我们无需从第 1 段路重新累加。只需查阅紧邻的前一个里程碑的数值，再加上当前这一段路的长度即可。

公式：

当前前缀和 = 前一个前缀和 + 当前元素的值

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

第五部分：C++ 代码

long long a[100005]; // 原数组
long long S[100005]; // 前缀和数组（里程碑）
// 第一步：处理前缀和数组

for (int i = 1; i <= n; i++) {
    cin >> a[i]; 
    // 递推：当前总和 = 前一个总和 + 当前数字
    S[i] = S[i-1] + a[i]; 
}


// 第二步：查询第 L 个元素到第 R 个元素的区间和
for (int i = 0; i < q; i++) {
    int L, R;
    cin >> L >> R; 

    // 终点 - 起点的前一个
    cout << S[R] - S[L-1] << endl; 
}

数组下标从 1 开始！

如果要求区间 [1, 5] 的和，套公式是 $S[5] - S[0]$。我们刚好就默认 $S[0] = 0$，非常完美。
如果你非要从下标 0 开始存数据（求 [0, 4]），公式就会变成 $S[4] - S[-1]$。数组下标变成负数，程序直接越界崩溃！所以，写前缀和，数组从 1 开始！否则你就要特判下标为 -1 的情况了。

前缀和数组务必开 long long！

原数组 a 的数字可能不大，但十万个数加在一起很有可能超过 int 的上限（约 21 亿）。为了不爆数据，前缀和数组请开 long long。

5.3 KiB Raw Permalink Blame History Unescape Escape