Day6 前缀和 Acwing 796. 子矩阵的和 AcWing 795. 前缀和 【C++】

1、一维 前缀和2、子矩阵的和

​

题目
​​​​​​​​

思路 先列表计算 每个前n项和O(n) 然后直接输入计算 O（1）​​​​

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

作用 ： 快速求一段数之和

#include 

using namespace std;

const int N=100010;

int n,m;
int a[N],s[N];

int main () {
    scanf ("%d%d", &n,&m);
    for (int i = 1;i <= n;++ i) scanf ("%d",&a[i]); //从1开始读取
    for (int i = 1;i <= n;++ i) s[i]=s[i-1]+a[i];  //公式

    while (m --) { 
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%dn",s[r]-s[l-1]);
    }
    return 0;
}

题目

思路 计算每一个矩阵的总和 O（n^2） 然后 直接求和

还是得我灵魂画手来 每部分颜色表示相应数组的总和

代码：

#include 

using namespace std;

const int N=1010;

int a[N][N],s[N][N];

int main () {
    int n,m,q;
    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]);
            s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j]; // 求前缀和
        }

    while (q --) {
       
        int x1,y1,x2,y2;
        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;
}

感谢观看

​