AcWing 796. 子矩阵的和
原题链接
简单
作者:
Kurumi.
,
2024-03-04 10:52:43
,
所有人可见
,
阅读 18
用公式s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
int n,m,q,i,j;
const int N = 1010;
int a[N][N],s[N][N];
int main()
{
n=read(),m=read(),q=read();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
a[i][j]=read(),s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];//输入+预处理
while(q--){//区间查询
int x1=read();int y1=read();int x2=read();int y2=read();
cout<<s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]<<'\n';
}
return 0;
}