#前缀和

前缀和（Prefix Sum）是一种简单但非常实用的算法技巧，主要用于高效地计算数组中一段连续元素的和。通过预处理数组的前缀和，我们可以在常数时间内查询任意区间的和。

#问题背景

假设我们有这样一个需求，给定一组共 n 个整数，需要查询从第 l 个元素到第 m 个元素范围内所有元素的和。如何去求？

例如，对于下面的输入数据

第一行的 7 3 5 ，7 代表 n，也就是第二行给出 7 个数据，3 5 表示要求出第 3 个元素到第 5 元素之间（包括第 3 和第 5 个元素）所有元素的和。

人工来计算，一眼就可以看出来，这个范围一共三个数，3+4+5=12，也就是输出结果应该是 12。

#朴素解法

用编程来求解， 也很容易想到，这就是一个简单的通过循环去完成的累加求和应用。

代码也很简单：

#include <bits/stdc++.h>
using namespace std;

int n, l, m, sum;
int q[110];

int main() {
  cin >> n >> l >> m;
  
  for (int i = 1; i <= n; i++) cin >> q[i];
  
  // 计算 m 到 k 之间的所有整数之和
  for (int i = l; i <= m; i++) {
    sum += q[i];
  }
  
  cout << sum << endl;
  return 0;
}

#问题拓展

对于上面的问题，用朴素解法求解就可以了，算法复杂度为 $O(n)$。

如果我们把问题变得稍微复杂一点，假设我们有 k 个这样的查询呢？

例如，像下面这样的输入数据：

这里的 7 3，7 仍然是 n，表示后面有 7 个输入的整数，后面的 3 代表 k，表示一共有 k 查询，分别要求三个范围内的元素之和，这三个范围分别是 [2 4]、[1 5]、[3 5]，求出的结果应该分别是：

• 2+3+4=9
• 1+2+3+4+5=15
• 3+4+5=12

因此输出：

#拓展问题朴素解法

用同样的朴素解法，也不复杂，参考代码如下：

#include <bits/stdc++.h>
using namespace std;

int n, k, t, l, m, sum;
int q[110];

int main() {
  cin >> n >> k;
  
  for (int i = 1; i <= n; i++) cin >> q[i];
  
  while (k--) {
    cin >> l >> m;
    sum = 0;
    for (int i = l; i <= m; i++) {
      sum += q[i];
    }
    cout << sum << endl;
  }
  return 0;
}

复杂度变为 $O(n \times k)$ 。

#前缀和求解

前缀和就是解决上述拓展问题的一种算法技巧，通过预处理数组的前缀和，我们就可以查询任意敬意的和，通过前缀和算法技巧，我们可以将算法复杂度降到 $O(n)$。

#什么是前缀和

前缀和（Prefix Sum）是指一个数组中，从第一个元素到当前元素的累积和。通过预处理前缀和数组，我们可以快速计算任意区间的和。

举个例子：

给定一个数组 A = [1, 2, 3, 4, 5]，其前缀和数组 prefix_sum 为：

prefix_sum[1] = A[1] = 1
prefix_sum[2] = A[1] + A[2] = 1 + 2 = 3
prefix_sum[3] = A[1] + A[2] + A[3] = 1 + 2 + 3 = 6
prefix_sum[4] = A[1] + A[2] + A[3] + A[4] = 1 + 2 + 3 + 4 = 10
prefix_sum[5] = A[1] + A[2] + A[3] + A[4] + A[5] = 1 + 2 + 3 + 4 + 5 = 15

所以，前缀和数组 prefix_sum 为 [1, 3, 6, 10, 15]。

有了前缀和数组，要求任意区间的元素之和就很简单了，比如，要求 [3 5] 第 3 与第 5 个元素之间的和，就直接用 prefix_sum[5] - prefix_sum[2] = 15 - 3 = 12。

注意，这里需要用 prefix_sum[5] - prefix_sum[2] 而不是 prefix_sum[5] - prefix_sum[3]，想一想为什么呢？

#前缀和求解代码

因此，前面的拓展问题，如果用前缀和算法技巧来完成，分为两步：

1. 预处理阶段：计算并存储前缀和数组
2. 查询阶段：利用前缀和数组快速计算任意区间和

参考代码如下：

#include <bits/stdc++.h>
using namespace std;

int n, k, l, m;
int q[110], prefix_sum[110];

int main() {
  cin >> n >> k;
  
  for (int i = 1; i <= n; i++) cin >> q[i];
  
  // 预处理求出前缀和数组
  prefix_sum[1] = q[1];
  for (int i = 2; i <= n; i++) {
    prefix_sum[i] = prefix_sum[i - 1] + q[i];
  }
  
  while (k--) {
    cin >> l >> m;
    cout << prefix_sum[m] - prefix_sum[l - 1] << endl;
  }
  
  return 0;
}

#前缀和的优缺点

#优点

• 高效性： 预处理时间复杂度为 $O(n)$，单次查询时间复杂度为 $O(1)$。
• 简洁性： 代码实现简单，易于理解和维护。
• 广泛应用： 不仅限于一维数组，还可以扩展到多维数组和其他数据结构。

#缺点

• 需要额外的 $O(n)$ 空间来存储前缀和数组
• 当原始数组改变时需要重新计算前缀和（不适合频繁修改原始数据的场景）

#前缀和的应用

前缀和主要用于以下几种场景：

1. 区间和查询： 快速计算数组中任意区间的和。
2. 子数组和： 判断是否存在一个子数组，其和等于某个特定值。
3. 二维前缀和： 在二维数组中计算子矩阵的和。

#总结

前缀和虽然简单，但对于我们理解循环及数组的应用还是非常好的，而且它也是很多高级算法的基础，理解透彻后对学习其他算法很有帮助。