归档157

682 字

3 分钟

前缀和

2025-10-02

数据结构与算法

前缀和#

前缀和用来快速求区间和。它的核心是提前做一次预处理，把“每次都遍历区间”变成“两个数组值相减”。

1、为什么需要前缀和#

假设有数组：

1
1 2 3 4 5

如果想求 [2, 4] 的和，也就是：

1
2 + 3 + 4 = 9

普通做法是每次循环一遍区间，复杂度是 O(n)。

如果有很多次查询，这样会很慢。前缀和可以把每次查询降到 O(1)。

2、一维前缀和公式#

定义：

1
s[i] = a[1] + a[2] + ... + a[i]

那么：

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

查询 [l, r] 的区间和：

1
a[l] + ... + a[r] = s[r] - s[l - 1]

3、一维前缀和模板#

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

4
const int N = 100010;
5

6
int n, m;
7
int a[N], s[N];
8

9
int main() {
10
    scanf("%d%d", &n, &m);
11

12
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
13

14
    for (int i = 1; i <= n; i++) {
15
        s[i] = s[i - 1] + a[i];
16
    }
17

18
    while (m--) {
19
        int l, r;
20
        scanf("%d%d", &l, &r);
21
        printf("%d\n", s[r] - s[l - 1]);
22
    }
23

24
    return 0;
25
}

这里建议数组从 1 开始存，这样 s[l - 1] 更自然。

4、二维前缀和解决什么问题#

二维前缀和用于快速求一个子矩阵的和。

比如矩阵里要查询左上角 (x1, y1) 到右下角 (x2, y2) 这个矩形区域的总和。

5、二维前缀和公式#

构造公式：

1
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]

查询公式：

1
sum = s[x2][y2]
2
    - s[x1 - 1][y2]
3
    - s[x2][y1 - 1]
4
    + s[x1 - 1][y1 - 1]

可以理解为：先取大矩形，再减掉上面和左边多算的部分，最后把左上角被减了两次的区域加回来。

6、二维前缀和模板#

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

4
const int N = 1010;
5

6
int n, m, q;
7
int a[N][N], s[N][N];
8

9
int main() {
10
    scanf("%d%d%d", &n, &m, &q);
11

12
    for (int i = 1; i <= n; i++) {
13
        for (int j = 1; j <= m; j++) {
14
            scanf("%d", &a[i][j]);
15
        }
16
    }
17

18
    for (int i = 1; i <= n; i++) {
19
        for (int j = 1; j <= m; j++) {
20
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
21
        }
22
    }
23

24
    while (q--) {
25
        int x1, y1, x2, y2;
26
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
27
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
28
    }
29

30
    return 0;
31
}

7、容易写错的地方#

（1）二维构造时循环边界写错#

1
for (int j = 1; j <= m; j++)

不要写成 j < m，否则最后一列不会被处理。

（2）查询循环变量写错#

二维前缀和通常有 q 次查询：

1
while (q--)

不要误写成 while (m--)。

（3）查询公式下标写混#

记住是：

1
右下 - 上方 - 左方 + 左上

总结#

前缀和适合“多次区间求和”。一维记住：

1
s[r] - s[l - 1]

二维记住：

1
大矩形 - 上面 - 左边 + 左上角

文章分享

如果这篇文章对你有帮助，欢迎分享给更多人！

前缀和

https://blog.tjcheng.cn/posts/migrated/old-77/

作者

TengJinCheng

发布于