---
title: "前缀和"
description: "前缀和、差分、双指针、滑动窗口等高频算法套路。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 前缀和

![](https://img.dailyup.xyz/originals/8208462642019-cbe872dc-0551-4082-ba61-8d321dd936d4.png)


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

## 问题背景

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

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

```
7 3 5
1 2 3 4 5 6 7
```

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

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

## 朴素解法

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

代码也很简单：

```cpp
#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
1 2 3 4 5 6 7
2 4
1 5
3 5
```

这里的 `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`

因此输出：

```
9
15
12
```

## 拓展问题朴素解法

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

```cpp
#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` 为：
```cpp
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. **查询阶段**：利用前缀和数组快速计算任意区间和

参考代码如下：

```cpp
#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. **二维前缀和：** 在二维数组中计算子矩阵的和。

## 总结

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

Source: https://cppguide.xyz/algopatterns/prefixsum/index.mdx