输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式

第一行包含三个整数 n，m，q

接下来 n 行，每行包含 mm 个整数，表示整数矩阵。

接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。

输入样例：

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

输出样例：

17
27
21

代码如下：

#include<iostream>
using namespace std;
const int N= 1010;//类似于C语言中的#define N 1010; 
int n,m,q;
int a[N][N],s[N][N];//定义两个二维数组； 
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)//行从1开始定义
	for(int j=1;j<=m;j++)//列也从1开始定义
	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];//定义i行j列所有元素的和； 
	while(q--)
	{
		int x1,x2,y1,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;
}

前缀和：7.前缀和（C++）_瘦出腹肌的JingLi的博客-CSDN博客_前缀和c++

1.定义：s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]

 蓝色表示被计算过两次，浅蓝表示计算过一次，绿色表示还未被计算

 s[i-1][j]+s[i][j-1]-s[i-1][j-1]   如上图所示

因为s[i-1][j] 是前（i-1）行 （j) 列数的总和

       s[i][j-1] 是前（i）行 （j-1) 列数的总和

       s[i][j]    是前（i）行 （j) 列数的总和

所以s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1] +a[i][j]；

2.s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]

x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。

 白色表示0（没有加也没有减去），绿色表示1（加进去了），黑色表示-1（减去了）.

s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]

s[x2][y2]    表示的是前 x2 行 y2 列数的总和

s[x1-1][y2]表示的是前 x1-1 行 y2 列数的总和

以此类推：

所以要求绿色方格数的总和

最左上方的绿色方格是x1,y1。 最右下方的绿色方格是x2,y2

黑色方块(表示被多减去了一次)：s[x1-1][y1-1]

绿色方块：s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]