二维前缀和

输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1 , y1 , x2 , y2 ，表示一个子矩阵,(x1,y1)为左上角坐标，（x2,y2）为右下角坐标。对于每个询问输出子矩阵中所有数的和。

定义两个二维数组，一个存矩阵的数字a[][]，一个存和s[][],s[i][j]表示在二维数组中，左上角（1,1）到右下角（i,j）所包围的矩阵元素的和。

二维前缀和预处理公式：s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]

二位前缀和结论：sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m,q;
	cin>>n>>m>>q;
	int a[n+1][m+1];//存矩阵的元素
	int s[n+1][m+1];//存矩阵范围内元素和
	for(int i=1;i<=n;i++){//循环从1开始
		for(int j=1;j<=m;j++){
			cin>>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]+a[i][j]-s[i-1][j-1];//二维前缀和预处理公式
		}
	}
	int x1,y1,x2,y2;
	while(q--){
		int sum=0;
		cin>>x1>>y1>>x2>>y2;
		sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];//二位前缀和结论
		cout<<sum<<endl;
	}
	return 0;
}