每日打卡-8.1

一.问题描述

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

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

二.设计思路

很典型的二维前缀模板题
 先求前缀和 ， 再利用公式ans = s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1] 求出答案即可

三.流程图

四.伪代码 

1

五.代码实现 

1# include <iostream>
using namespace std ; 
const int N = 1e3 + 10 ; 
int a[N][N];
int sum[N][N];
int main(){
	int m , n , q;
	cin >> n >> m >> q;
	for (int i = 1 ; i <= n ; i ++)
		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 ++)
			sum[i][j] = sum[i-1][j] + sum[i][j-1] -sum[i-1][j-1] +a[i][j];
	// 求指定区间的和
	while (q --){
		int x1 , x2 , y1 , y2 ;
		cin >> x1 >> y1 >> x2 >> y2 ;
		cout << sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1] <<endl; 
	}
	return 0 ;
}