AcWing 796. 子矩阵的和
原题链接
简单
作者:
lemon_242
,
2024-02-26 18:22:56
,
所有人可见
,
阅读 17
y总原样模板+注释理解
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N];
int s[N][N]; //存储前缀和的数组s
int main()
{
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
scanf("%d", &a[i][j]); //读入原数组
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; //计算前缀和,也就是s[i][j]的值
}
while (q -- ) //q个询问
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
//计算局部矩形的和,也就是规定了左上角和右下角坐标的局部矩形
//可以利用s里存储的前缀和数值直接计算
//计算公式:s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] 根据图形来记忆!!
printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}
return 0;
}