自我建设外贸网站,深圳微商城网站设计公司,网页游戏网站首页,网站运营推广该如何做文章目录 796.子矩阵的和题目描述前缀和 796.子矩阵的和
题目描述
输入一个 n 行 m 列的整数矩阵#xff0c;再输入 q 个询问#xff0c;每个询问包含四个整数 x1,y1,x2,y2#xff0c;表示一个子矩阵的左上角坐标和右下角坐标。 对于每个询问输出子矩阵中所有数的和。
输… 文章目录 796.子矩阵的和题目描述前缀和 796.子矩阵的和
题目描述
输入一个 n 行 m 列的整数矩阵再输入 q 个询问每个询问包含四个整数 x1,y1,x2,y2表示一个子矩阵的左上角坐标和右下角坐标。 对于每个询问输出子矩阵中所有数的和。
输入格式 第一行包含三个整数 nmq。 接下来 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前缀和
#include bits/stdc.h // 包含大部分标准库
using namespace std;const int z 1010; // 设置数组的最大长度因为数据范围是1≤n,m≤1000
int a[z][z], s[z][z]; // a是原始的矩阵s是用来存储前缀和的矩阵int main()
{int n, m, q; // n是行数m是列数q是查询次数scanf(%d %d %d, n, m, q); // 读入n, m, qfor (int i 1; i n; i) // 从1开始因为前缀和需要从(1,1)开始计算{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];}}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;
}这段代码的核心思想是二维前缀和。二维前缀和是一种数据预处理技术它使得我们能够快速在常数时间内查询任何子矩阵的元素和。二维前缀和 s[i][j] 表示原始矩阵中所有位于第1行第1列到第i行第j列形成的子矩阵的元素之和。
这样如果我们想要计算任何子矩阵x1, y1到x2, y2的元素和我们可以通过四个前缀和来计算这是通过以下方式完成的
s[x2][y2] - 左边的矩形s[x2][y1 - 1] - 上边的矩形s[x1 - 1][y2] 因为重复减去了左上角的矩形所以要加回来s[x1 - 1][y1 - 1]这个方法大大减少了查询的时间复杂度使得即使在大量查询中也能保持高效的性能。
