题目描述
求每个询问对应子矩阵的和.
样例
输入样例:
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
前缀和
一维前缀和
1.含义:
数组 a1,a2,...,an
前缀和数组 si = a1 + a2 + ... + ai
2.如何构造:
从前向后递推:s[i] = a[i] + s[i-1]
3.应用:
快速求出一段连续区间的和.常见于预处理优化算法时间.
a[l] + a[l+1] + ... + a[r] = s[r] - s[l-1]
前缀和在使用时一般下标从1开始.省去l==0时的特殊判断.
时间复杂度
构造:O(n)
查询:O(1)
二维前缀和
1.含义:
二维数组:a[i,j] 1<=i<=n 1<=j<=m
二维前缀和:s[i,j] = sum( a[i'][j'] 1<=i'<=i,1<=j'<=j)
2.如何构造:
同样是递推构造.先列后行.s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1]
3.应用:
快速求出一个子矩阵元素和.左上角坐标(x1,y1),右下角坐标(x2,y2)
s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][x2-1]
时间复杂度
构造:O(nm)
查询:O(1)
C++ 代码
#include<cstdio>
const int Max_N = 1010;
int n, m, q;
int a[Max_N][Max_N], s[Max_N][Max_N];
//求子矩阵和
int get_sum(int x1, int y1, int x2, int y2)
{
return s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1];
}
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] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];
}
}
while( q-- )
{
int x1, y1, x2, y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",get_sum(x1,y1,x2,y2));
}
return 0;
}