前缀和(2)_【模板】二维前缀和_模板
个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创前缀和(2)_【模板】二维前缀和_模板
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌
目录
1. 题目链接 :
2. 题目描述 :
描述
输入描述：
输出描述：
示例1
3. 解法(二维前缀和) :
题目分析:
算法思路:
1. 前缀和矩阵
2. 使用前缀和矩阵
代码展示:
结果分析:
1. 题目链接 :
OJ链接: 【模板】二维前缀和
2. 题目描述 :
描述
给你一个 n 行 m 列的矩阵 A ，下标从1开始。
接下来有 q 次查询，每次查询输入 4 个参数 x1 , y1 , x2 , y2
请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和，
输入描述：
第一行包含三个整数n,m,q.
接下来n行，每行m个整数，代表矩阵的元素
接下来q行，每行4个整数x1, y1, x2, y2，分别代表这次查询的参数
1≤n,m≤10001≤n,m≤1000
1≤q≤1051≤q≤105
−109≤a[i][j]≤109−109≤a[i][j]≤109
1≤x1≤x2≤n1≤x1≤x2≤n
1≤y1≤y2≤m1≤y1≤y2≤m
输出描述：
输出q行，每行表示查询结果。
示例1
输入：
3 4 3 1 2 3 4 3 2 1 0 1 5 7 8 1 1 2 2 1 1 3 3 1 2 3 4
输出：
8 25 32
3. 解法(二维前缀和) :
题目分析:
比如示例1:
3 4 ---> 输入一个3行4列的数组:
3 ---> 3次询问:
算法思路:
类比于一维数组的形式,如果我们能处理出来从[0, 0]位置到[i, j]位置这片区域内所有元素的累加和,就可以在O(1)的时间内,搞定矩阵内任意区域内所有元素的累加和.因此我们接下来仅需完成两步即可:
1. 前缀和矩阵
a.sum[i][j] 的含义：
sum[i][j] 表示，从[0, 0] 位置到[i, j] 位置这段区域内，所有元素的累加和。对应
下图的红色区域：
b.递推方程：
其实这个递推方程非常像我们小学做过求图形面积的题，我们可以将[0, 0] 位置到[i, j]
位置这段区域分解成下面的部分：
sum[i][j] = 红 + 蓝 + 绿 + 黄，分析⼀下这四块区域：
i.黄色部分最简单，它就是数组中的 matrix[i - 1][j - 1] （注意坐标的映射关系）
ii.单独的蓝不好求，因为它不是我们定义的状态表示中的区域，同理，单独的绿也是；
iii.但是如果是红 + 蓝，正好是我们 dp 数组中 sum[i - 1][j] 的值，美滋滋；
iv.同理，如果是红 + 绿，正好是我们 dp 数组中 sum[i][j - 1] 的值；
v.如果把上面求的三个值加起来，那就是黄 + 红 + 蓝 + 红 + 绿，发现多算了一部分红的面积，
因此再单独减去红的面积即可；
vi.红的面积正好也是符合 dp 数组的定义的，即 sum[i - 1][j - 1]
综上所述，我们的递推方程就是：
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j -1] + matrix[i - 1][j - 1]
2. 使用前缀和矩阵
对于左上角(row1, col1) 、右下角(row2, col2) 围成的区域，正好是红色的部分。因
此我们要求的就是红色部分的面积，继续分析几个区域：
i.黄色，能直接求出来，就是 sum[row1 - 1, col1 - 1]
ii.绿色，直接求不好求，但是和⻩⾊拼起来，正好是 sum 表内 sum[row1 - 1][col2]
的数据；
iii.同理，蓝色不好求，但是 蓝 + 黄 = sum[row2][col1 - 1] ；
iv.再看看整个面积，好求嘛？非常好求，正好是 sum[row2][col2] ；
v.那么，红色就 = 整个面积 - 黄 - 绿 - 蓝，但是绿蓝不好求，我们可以这样减：整个面积 - （绿+ 黄 ） - （蓝 + 黄），这样相当于多减去了⼀个黄，再加上即可
综上所述：红 = 整个面积 - （绿 + 黄） - （蓝 + 黄） + 黄，从而可得红色区域内的元素总和为：
sum[row2][col2] - sum[row2][col1 - 1] - sum[row1 - 1][col2] + sum[row1 -1][col1 - 1]
代码展示:
#include <iostream>
#include <vector>
using namespace std;int main() {int n, m, q;cin >> n >> m >> q;vector<vector<long long>> arr(n + 1, vector<long long>(m + 1));for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> arr[i][j];vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + arr[i][j];while (q--){int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;cout << dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1] << endl;}return 0;
}
注意:
这道题数组的下标是从1开始,如果从0开始,我们还需要考虑边界问题
结果分析:
时间复杂度
输入阶段：读取n* m个元素，时间复杂度为O(n×m)。
前缀和计算：计算二维前缀和的过程也是一个双重循环，时间复杂度同样为O(n×m)。
查询阶段：每次查询的时间复杂度为O(1)，而总共要处理q个查询，因此查询的总时间复杂度为O(q)。
综上，整体时间复杂度为：O(n×m + q)
空间复杂度
数组存储：
arr数组占用空间O(n×m)。
dp数组同样占用空间O(n×m)。
因此，整体空间复杂度为：O(n×m)
总结
时间复杂度：O(n×m + q)
空间复杂度：O(n×m)