二维前缀和
图片优化链接
https://www.acwing.com/solution/content/237227/
题目描述
输入一个 n 行 m 列的整数矩阵,再输入 q 个询问,每个询问包含四个整数 x1,y1,x2,y2,
表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n,m,q。
接下来 n 行,每行包含 m 个整数,表示整数矩阵。
接下来 q 行,每行包含四个整数 x1,y1,x2,y2,表示一组询问。
输出格式
共 q 行,每行输出一个询问的结果。
数据范围
1≤n,m≤1000, 1≤q≤200000, 1≤x1≤x2≤n, 1≤y1≤y2≤m, −1000≤矩阵内元素的值≤1000
输入样例:
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
暴力写法
思路分析
首先,存入 n,m,q,接下来设置一个二层循环,存入这个矩阵的对应位置的每一项
再接下来,先设置一个一层循环,每层循环存入 x1, y1, x2, y2,定义一个sum = 0,
然后设置一个二层循环,
第一层循环的条件是 从 x1 到 x2,
第二层循环的条件是 从 y1 到 y2,
然后给其中的每一项都累加起来,然后输出就完事儿了,ok,上暴力代码
#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N];
int main(){
int n, m, q;
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 k = 1; k <= q; k ++){
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int sum = 0;
for (int i = x1; i <= x2; i ++)
for (int j = y1; j <= y2; j ++)
sum += a[i][j];
printf("%d\n", sum);
}
return 0;
}
数据范围是 1000 ,最多是三层循环,每层循环的遍历范围都可以取到一千,这样的话就是 10 的
9 次方了,但是 q 的取值范围其实更大,所以就必超时了
暴力吧,一暴力一个不吱声
优化写法
思路分析
我们是否可以像一维前缀和那样,再 O(1) 的时间范围内输出要询问的结果呢,答案是肯定的哈,这时候
我们还是需要处理处理一个前缀和,只不过这个前缀和是二维的,该怎么处理呢
多余的数据读入就不说了,现在假设 二维数组 a 用来存储每一项的数值,刚开始的第一项是 a[1][1],
a 为全局变量,没有读入数据的 a[i][j] 值为 0.
现在我们再定义一个二维数组 s,s[i][j] 表示 从 (0,0)(左上角) 到 (i,j)(右下角)之间所有元素的和,如下图
注意:灰线所框出的方格代表 a[i][j],而不是灰线交叉点代表 a[i][j],黑线交叉点代表 a[i][j] 的坐标,近似代表 a[i][j]
现在的问题是我们该如何来计算 s[i][j] 呢
是不是等于 s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i][j] 呢,不急,先画个图演示一下
可以发现,s[i - 1][j] + s[i][j - 1] + a[i] 是大于 s[i][j],为什么呢,因为 s[i - 1][j] + s[i][j - 1] + a[i]的数值
实际是比 s[i][j] 多了个 s[i - 1][j - 1] 的,我们只需要把 s[i - 1][j - 1] 减去就好了
所以 s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]
下面先展示一下二维数组 s 预处理的核心代码
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] + a[i][j];
ok,现在我们数据存储完了,前缀和也处理完了,那么,该如何单次询问在 O(1) 时间范围内输出我们想要得到的结果呢
是不是也可以像一维前缀和那样,直接做差就好了,答案是肯定的
但是是不是 直接输出 s[x2][y2] - s[x1][y1] 就好了,先画个图冷静一下
ok,看图,不能说我们要求的值跟 s[x2][y2] - s[x1][y1]一点儿关系没有吧,简直就是毫不相干,那么,我们该如何求
我们要求的数值呢,还是就着这个图,我们画一下,我们要求的那部分数值的和所代表的区域,用紫色横线 + 蓝色竖线了哈
其实我们要求的那部分数据的和所代表的区域,就是我们画的看着最乱七八糟的那块区域,但是我们还是可以依稀
从上面看到 乱七八糟 的这块区域和 s[x1][y1] 是有点重叠的,其实也很好解释
我们要求的是以左上角坐标为 (x1,y1)和 右下角坐标为 (x2,y2)的矩阵内所有元素的和
其中 我们要求的这个数值当中是包含 a[x1][y1] 的,但是直接减去 s[x1][y1] 势必会伤害到自家人,因为通过二维数组 s 的
初始化的过程中我们不难得到 s[x1][y1] 是包含 a[x1][y1] 的,但是答案跟 s[x2][y2] - s[x1][y1] 没有个卵的关系啊
这里就不再卖关子了,其实图已经画的很明显了
如果我们想单次询问再 O(1) 时间范围内找到并输出我们想要的答案的话
我们只需要输出 s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] 就好了
注意 最后那个符号是 “+”,因为s[x1 - 1][y1 - 1] 那一部分被减去了两次,所以要再加上
这里再附上一个终极图片
这次说的有点啰里啰唆了,上终极代码!
#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N], s[N][N];
int main(){
int n, m, q;
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] + a[i][j];
for (int k = 1; k <= q; k ++){
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}
return 0;
}