二维前缀和
课上练习
知识总结
二维前缀和-知识总结
二维前缀和-知识总结 一维前缀和概念 二维前缀和（Prefix Sum）是一种常见的数据处理技术，特别适用于高效计算二维数组某一段区间的和。它通过预处理数组，使得在进行区间和查询时能快速得到结果，从而避免了重复计算。
二维前缀和计算方法 假设有一个数组array，有n行m列。我们定义一个前缀和数组prefixsum，其大小也是n×m，使prefixsum[i][j]表示数组array从第1行第1列的点到第i行j列的元素的所有元素之和。利用递推公式求prefix_sum的值。
递推公式如下：
prefix_sum[i][j] = prefix_sum[i - 1][j] + prefix[i][j - 1] - prefix_sum[i - 1][j - 1] + array[i][j];代码示例如下：
1fill_n(prefix_sum, n * m, 0);
2for (int i = 0; i < n; ++i) {
3 for (int j = 0; j < m; ++j) {
4 prefix_sum[i][j] = prefix_sum[i - 1][j] + prefix[i][j - 1] - prefix_sum[i - 1][j - 1] + array[i][j];
5 }
6}算法评价 时间复杂度：O(n^2) 空间复杂度：O(n^2)
一维前缀和应用 求二维数组任意区间和方法 若已知数组array和该数组的前缀prefix_sum，计算任意区间的区间和时只需要知道区间起点和终点，即可在O(1)的时间内计算其区间和。
代码示例：
int x1 = 2, y1 = 3; // 区间左上角的点
int x2 = 5, y2 = 9; // 区间右下角的点
int sum = prefix_sum[x2][y2] - prefix_sum[x2][y1 - 1] - prefix[x1 - 1][y2] + prefix_sum[x1 - 1][y1 - 1];️课后作业
☝️总结作业
总结作业非常重要，请务必认真完成✔️
- 二维前缀和是用来解决什么问题的？
- 二维前缀和的递推公式是什么？
- 计算二维前缀和的时间复杂度和空间复杂度是多少？
- 利用二维前缀和计算二维区间和的计算公式是什么？
- 利用前缀和数组查询二次区间和的时间复杂度是多少？
✌️编程作业
考试只有一次提交机会，请务必本地检查正确后再提交❇️
👌编程作业标准答案
请在AC后或者思考15分钟没有进展后查看，不可抄代码❇️
L2213题解+参考代码
L2213题解+参考代码 题目链接 最大正方形：L2213
题解 我们需要在一个 n × m 的只包含 0 和 1 的矩阵里找出一个不包含 0 的最大正方形，并输出其边长。为了解决这个问题，我们可以使用二维前缀和来计算每个子矩阵中的 1 的数量，从而确定最大正方形的边长。
算法步骤 读取输入：读取矩阵的行数 n 和列数 m。 构建矩阵：读取矩阵的每个元素，存储在二维数组中。 构建前缀和矩阵： 创建一个 n+1 行 m+1 列的前缀和矩阵 prefix，初始化为 0。 填充前缀和矩阵，使 prefix[i][j] 表示从 (1, 1) 到 (i, j) 的子矩阵中 1 的数量。 查找最大正方形： 枚举每个点 (i, j) 作为正方形的右下角，尝试不同的边长 k。 使用前缀和矩阵快速计算子矩阵的和，判断其是否全为 1。 输出结果：输出最大正方形的边长。 示例代码 这里是使用 C++ 实现的示例代码：
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 // 读取输入
6 int n, m;
7 cin >> n >> m;
8 int matrix[50][50];
9 for (int i = 0; i < n; ++i) {
10 for (int j = 0; j < m; ++j) {
11 cin >> matrix[i][j];
12 }
13 }
14
15 // 初始化前缀和矩阵
16 int prefix[51][51] = {0};
17
18 // 填充前缀和矩阵
19 for (int i = 1; i <= n; ++i) {
20 for (int j = 1; j <= m; ++j) {
21 prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
22 }
23 }
24
25 // 查找最大正方形的边长
26 int maxLen = 0;
27 for (int i = 1; i <= n; ++i) {
28 for (int j = 1; j <= m; ++j) {
29 for (int k = 1; k <= min(i, j); ++k) {
30 int total = prefix[i][j] - prefix[i-k][j] - prefix[i][j-k] + prefix[i-k][j-k];
31 if (total == k * k) {
32 maxLen = max(maxLen, k);
33 }
34 }
35 }
36 }
37
38 // 输出结果
39 cout << maxLen << endl;
40
41 return 0;
42}L2214题解+参考代码
L2214题解+参考代码 题目链接 最大加权矩形：L2214
题解 要找到 n × n 矩阵中的最大加权矩阵，我们可以使用前缀和来进行枚举。具体来说，我们可以通过计算前缀和来快速求出任意子矩阵的和，然后枚举所有可能的子矩阵来找到最大和。
算法步骤 读取输入：读取矩阵的大小 n 和矩阵中的每个元素。 初始化前缀和数组：创建一个大小为 n+1 × n+1 的二维前缀和数组。 填充前缀和数组：计算前缀和，使 prefix[i][j] 表示从第一行第一列到第 i 行第 j 列的矩阵元素的和。 枚举所有子矩阵： 枚举所有可能的左上角 (i1, j1) 和右下角 (i2, j2)。 使用前缀和计算子矩阵的和，并更新最大和。 输出结果：输出最大加权矩阵的和。 示例代码 这里是使用 C++ 实现的示例代码：
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 // 读取输入
6 int n;
7 cin >> n;
8 int matrix[10][10];
9 for (int i = 0; i < n; ++i) {
10 for (int j = 0; j < n; ++j) {
11 cin >> matrix[i][j];
12 }
13 }
14
15 // 初始化前缀和矩阵
16 int prefix[11][11] = {0};
17
18 // 填充前缀和矩阵
19 for (int i = 1; i <= n; ++i) {
20 for (int j = 1; j <= n; ++j) {
21 prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
22 }
23 }
24
25 // 查找最大加权矩阵的和
26 int maxSum = INT_MIN;
27 for (int i1 = 1; i1 <= n; ++i1) {
28 for (int j1 = 1; j1 <= n; ++j1) {
29 for (int i2 = i1; i2 <= n; ++i2) {
30 for (int j2 = j1; j2 <= n; ++j2) {
31 int currentSum = prefix[i2][j2] - prefix[i1-1][j2] - prefix[i2][j1-1] + prefix[i1-1][j1-1];
32 maxSum = max(maxSum, currentSum);
33 }
34 }
35 }
36 }
37
38 // 输出结果
39 cout << maxSum << endl;
40
41 return 0;
42}