前缀和

发表于 更新于 分类于 ，
本文字数： 907

前缀和算法的一二维示例

[l,r]的和 (一维)：

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

using namespace std;

int s[100000];

int main()
{
    int n,m,t;
    cin >> n >> m;
    s[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &t);
        s[i] += s[i - 1] + t;
    }
    int l,r;
    while (m--)
    {
        scanf("%d%d", &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 a[N][N],s[N][N];

int main()
{
    int n,m,q;
    cin >> 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] = s[i - 1][j] + s[i][j - 1] + a[i][j] - s[i - 1][j - 1];
    int x1,y1,x2,y2;
    while (q--)
    {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%dn", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }
    return 0;
}