前缀和的作用是快速求数组中一段区间内的所有数之和。

Sj−Si−1=ai+...+ajS_j - S_{i-1} = a_i + ... + a_j

程序实现上，前缀和数组下标从 1 开始，因为求 [1, x] 之间的和，可以通过 S[x] - S[0] 计算，不必特判 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

const int N = 100010;
int a[N];
int s[N];
int main() {
    // 让 cin 更快，副作用是不能再使用 scanf
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) {
        s[i]=s[i-1]+a[i];
    }
    for(int i=0;i<m;i++) {
        int l,r;
        cin >> l >> r;
        cout << s[r]-s[l-1] << endl;
    }
    return 0;
}

二位情况下求子矩阵的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], s[N][N];

int main() {
    scanf("%d%d%d", &n, &m, &q);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            scanf("%d", &a[i][j]);
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }

    while(q--) {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d", &x1,&y1,&x2,&y2);
        printf("%d\n", s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);
    }
    return 0;
}