二维前缀和——比想象中的简单

看一下题先 这个q太大了，显然是不能暴力做 和一维前缀和类似的，我们将之拓展至二维空间：用二维数组s[i][j]来表示从(1,1)至(i,j)的矩阵中所有元素的和

我习惯用Excel来模拟这个过程 当我们读入a[i][j]时，s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]，不难看出维护s数组的过程是可以和读入同时进行的

int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        cin>>a[i][j];
        s[i][j]=s[i][j-1]+s[i-1][j]+a[i][j]-s[i-1][j-1];
    }

下一步是处理查询坐标(x1,y1),(x2,y2) 两个点的分布不确定，我们希望点1位于左上角，点2位于右下角，因此

cin>>x1>>y1>>x2>>y2;
if(x1>x2)
    swap(x1,x2);
if(y1>y2)
    swap(y1,y2);

ACwing的数据中给出的数据默认了这个原则，但是题干中并没有提到，所以我做的时候多想了一步

然后处理点1,2表示的矩形中的元素和 有图就很好推了 这个矩形中的元素和应该是s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]下面是全部代码

#include<bits/stdc++.h>
#define P system("pause")
#define E cout<<endl
using namespace std;
typedef long long ll;

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

int main(){
    ios::sync_with_stdio(false);
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            s[i][j]=s[i][j-1]+s[i-1][j]+a[i][j]-s[i-1][j-1];
        }
    int x1,y1,x2,y2;
    for(int i=1;i<=q;i++){
        cin>>x1>>y1>>x2>>y2;
        if(x1>x2)
            swap(x1,x2);
        if(y1>y2)
            swap(y1,y2);
        cout<<s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]<<endl;
    }

    return 0;
}