前缀和板子题。 如果你不会二维前缀和，请自己查阅资料。 直接上代码：

#include <iostream> using namespace std; int n,m,q,r,c,x,y,a[1005][1005],s[1005][1005]; int main(){ 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]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1]; } while(q--){ cin>>r>>c>>x>>y; cout<<s[x][y]-s[x][c-1]-s[r-1][y]+s[r-1][c-1]<<endl; } return 0; }

思路： 这道题可以通过前缀和来做。 重点：二维数组的前缀和要用一维数组记录 前缀和数组rc第i行第j列的下标是rc[(i-1)×m+j] 代码：

#include<bits/stdc++.h> using namespace std; int n,m,q,s[1001][1001],a,b,x,y; int main(){ cin>>n>>m>>q; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){ scanf("%d ",&s[i][j]); } for(int i=1;i<=n;++i) for(int j=1;j<m;++j) s[i][j+1]+=s[i][j]; for(int j=1;j<=m;++j) for(int i=1;i<n;++i) s[i+1][j]+=s[i][j]; while(q--){ scanf("%d %d %d %d",&a,&b,&x,&y); printf("%d\n",s[x][y]-s[a-1][y]-s[x][b-1]+s[a-1][b-1]); } return 0; }

这道题不能用暴力 上代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 难度：中等

二维前缀和 (此处的 numnumnum 指矩阵, preprepre 指前缀和数组, ansansans 指询问的回答) prei,j=numi,j+prei−1,j+prei,j−1−prei−1,j−1(i,j>1)pre_{i,j}=num_{i,j}+pre_{i-1,j}+pre_{i,j-1}-pre_{i-1,j-1}(i,j>1)prei,j =numi,j +prei−1,j +prei,j−1 −prei−1,j−1 (i,j>1) ans=prex,y−prea−1,y−prex,b−1+prea−1,b−1(a,b>1)ans=pre_{x,y}-pre_{a-1,y}-pre_{x,b-1}+pre_{a-1,b-1}(a,b>1)ans=prex,y −prea−1,y −prex,b−1 +prea−1,b−1 (a,b>1) 怎么感觉这两个公式这么像(只是符号变了) Code：