基础算法学习——二维前缀和
题目描述
二维前缀和思想
和一维前缀和一样
题解
1）构造一个二维数组s[N][N]使得二维数组里的每一个元素都是原来数组的前缀和
s[i][j] = s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
2）要求子矩阵的和，则可以通过s[N][N]来求
s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
完整代码
#include<stdio.h>
#define N 1001
int a[N][N],s[N][N];
int main(void)
{
int n,m,q,i,j; scanf("%d%d%d",&n,&m,&q);
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
scanf("%d",&a[i][j]);
s[i][j] = s[i][j-1]+s[i-1][j]-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
",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);
}
}
下一篇：
统计文本中某些词出现的次数