题目说明
数据范围
样例
代码
二维前缀和题目
前缀和：S[i，j]表示第i行第j列左上角的元素和，例如图中绿色部分表示为 s[3,4]
①（x1,y1）（x2,y2）这一子矩阵中所有数的和如何计算？
求红颜色区域的所有数的和：（3 2 / 5 3）
公式
②s[i,j]如何计算？
公式
#include <bits/stdc++.h> using namespace std; const int N=1010; int a[N][N],S[N][N]; int main() { int n,m,q; cin>>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]; while(q--) { int x1,y1,x2,y2; 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]); } return 0; }
