【蓝桥杯C组】备赛基础篇之前缀和算法

Attacking-vincent 2020-05-17 原文

前缀和。

算法介绍：

设a为数组，a[i]中储存的是前i 个数（包括自己）的总和，相当于我们中学学过的前N项和，那么，弄成这样的好处是什么呢？假如我们要多次访问一段区间的总和，难道每次都加一次进行重复运算吗？？？而我们的前缀和就可以解决这个问题，提前预处理，访问到这段区间直接相减就得出了答案，避免了许多的重复运算。

基本代码解析：

#include<iostream>
using namespace std;

const int N = 100000 + 10;
int s[N], a[N];

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

    for (int i = 1;i <= n;i++) scanf("%d", &a[i]);
    for (int i = 1;i <= n;i++) s[i] = s[i - 1] + a[i];//保存前i项数之和。
    //这里可以只用一个循环和一个数组，为了方便理解，我将他分开了。

    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);
        //大段区域减小段区域，得到中间区域，l记得要-1，别把第l个数减去了。
    }
    return 0;
}

子矩阵和

那我们可不可以升级一下，解决二维的数组呢，当然是可以的，这时候我们s[i][j]的性质变了，变成了前 i、j 所有数的和，我们储存和访问的子矩阵的时候就要注意一下重复的部分了。

升级代码解析：

#include<iostream>
#include<cstdio>
using namespace std;

const int N = 1010;
int a[N][N], s[N][N];

int main() {
    int n, m, q, x1, x2, y1, y2;
    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] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
    //可在纸上画一个草图，要得到s[i][j]，先加上a[i][j]，加上s[i - 1][j] 和 s[i][j - 1]所表示的区域，这时候，我们发现，有一段子矩阵重复了，再减去 s[i - 1][j - 1]便是我们的答案了。

    while (q--) {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
        //要得到我们想要的子矩阵的数值，就要把旁边的数给减去，也就是s[x1 - 1][y2] 和 s[x2][y1 - 1]所代表的区域，在草图上我们发现又有重复的区域，也就多减了，所以我们把s[x1 - 1][y1 - 1]加上。
    }
    return 0;
}