算法思路
1.首先,读取输入,包括矩阵的大小和元素以及查询的数量。
2.接着,构建一个前缀和数组 s,用于存储原始矩阵的前缀和信息。通过双重循环遍历原始矩阵中的每个元素,计算其对应的前缀和,并存储在 s 数组中。
3.对于每个查询,读取左上角和右下角的坐标,利用前缀和数组 s 可以在常数时间内计算出子矩阵的和。具体计算公式为 s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]。
4.输出每个查询的结果。
C++ 代码
#include<iostream>
using namespace std;
const int N=1010; // 定义矩阵大小的最大值
int n,m,q; // 矩阵的行数、列数以及询问的数量
int a[N][N],s[N][N]; // a[N][N]原始矩阵,存储输入的整数矩阵。s[N][N]存储原始矩阵的前缀和
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]);
}
}
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] 被重复计算了,因此要减去一次,
//最后再加上当前位置 (i, j) 的值 a[i][j],因为这个值被之前的操作减去了一次
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
}
while(q--) // 处理每一个询问
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2); // 输入询问的左上角坐标和右下角坐标
printf("%d\n",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);
}
return 0;
}