一.问题描述
输入一个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 ;
}