【算法】一维二维数组前缀和，以及计算二维矩阵中的子矩阵和
前缀和的概念
通过构建一个前缀和数组，我们可以在常数时间（O(1)）内使用前缀和数组计算任意子数组或子矩阵的和。
简单来说，就是把前面的项加在一起，使得新构建的前缀和数组中每一项都是原数组对应项之前的总和。
一维前缀和
前缀和数组 prefixSum 来记录从 arr[0] 到 arr[i] 的和：
prefixSum[i] = arr[0] + arr[1] + ... + arr[i]
对于任意一个区间 [l, r]，我们可以利用前缀和数组来快速计算该区间的和：
sum(l, r) = prefixSum[r] - prefixSum[l - 1]
- 这里，
prefixSum[r]表示从数组的开始到r的和。 prefixSum[l-1]表示从数组的开始到l-1的和。- 通过相减即可得到区间
[l, r]的和。
cpp案例
// # 一维前缀和的应用：快速计算数组区间的和
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 输入数组
int n;
cout << "请输入数组大小: ";
cin >> n;
vector<int> arr(n);
cout << "请输入数组元素: ";
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
// 计算前缀和
vector<int> prefixSum(n + 1, 0); // 前缀和数组，大小为 n+1
for (int i = 1; i <= n; ++i) {
prefixSum[i] = prefixSum[i - 1] + arr[i - 1];
}
// 输出前缀和数组
cout << "前缀和数组: ";
for (int i = 1; i <= n; ++i) {
cout << prefixSum[i] << " ";
}
cout << endl;
// 查询区间和
int queries;
cout << "请输入查询的区间数: ";
cin >> queries;
while (queries--) {
int l, r;
cout << "请输入区间 [l, r] (1-based index): ";
cin >> l >> r;
// 利用前缀和计算区间和
int sum = prefixSum[r] - prefixSum[l - 1];
cout << "区间 [" << l << ", " << r << "] 的和是: " << sum << endl;
}
return 0;
}
二维前缀和
- 二维前缀和的构建
二维前缀和用于快速计算矩阵中任意子矩阵的元素和。每个前缀和元素prefixSum[i][j]表示原矩阵从左上角(1,1)到(i,j)的所有元素总和。
构建公式：
prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + matrix[i-1][j-1]
示例矩阵：
matrix:
1 2 3
4 5 6
7 8 9
对应前缀和矩阵：
prefixSum:
0 0 0 0
0 1 3 6
0 5 12 21
0 12 27 45
每个值计算方法：
prefixSum[1][1] = matrix[0][0] = 1prefixSum[2][3] = prefixSum[1][3] + prefixSum[2][2] - prefixSum[1][2] + matrix[1][2] = 6 + 12 - 3 + 6 = 21
- 子矩阵求和
要快速计算左上角(i,j)到右下角(s,t)的子矩阵和，公式为：
sum = prefixSum[s][t] - prefixSum[i-1][t] - prefixSum[s][j-1] + prefixSum[i-1][j-1]
计算逻辑：
prefixSum[s][t]是从左上角到(s,t)的所有元素和。- 减去
prefixSum[i-1][t]去掉上方部分。 - 减去
prefixSum[s][j-1]去掉左方部分。 - 加上
prefixSum[i-1][j-1]补回重复减掉的部分。
- 示例计算
矩阵：
matrix:
1 2 3
4 5 6
7 8 9
目标子矩阵：从 (2,2) 到 (3,3)
子矩阵：
5 6
8 9
计算步骤：
prefixSum[3][3] = 45
prefixSum[1][3] = 6
prefixSum[3][1] = 12
prefixSum[1][1] = 1
sum = 45 - 6 - 12 + 1 = 28
cpp案例
#include <iostream>
#include <vector>
using namespace std;
// 计算二维矩阵前缀和
vector<vector<int>> computePrefixSum(const vector<vector<int>>& matrix)
{
int m{ static_cast<int>(matrix.size()) }; // 矩阵行数
int n{ static_cast<int>(matrix[0].size()) }; // 列
// 创建一个(m+1)x(n+1)的前缀和矩阵，初始化为0
vector<vector<int>> prefixSum(m + 1, vector<int>(n + 1, 0));
/*
1 2 3
4 5 6
7 8 9
我们计算 (1, 1) 的前缀和（对应 prefixSum[2][2]）：
当前值是 matrix[1][1] = 5。
上方部分是 prefixSum[1][2] = 3。
左侧部分是 prefixSum[2][1] = 5。
重叠区域是 prefixSum[1][1] = 1。
公式：
prefixSum[2][2] = 5 + 3 + 5 - 1 = 12*/
for (int i{ 1 }; i <= m; ++i)
{
for (int j{ 1 }; j <= n; ++j)
{
prefixSum[i][j] = matrix[i - 1][j - 1] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1];
}
}
return prefixSum;
}
// 根据前缀和矩阵计算子矩阵和
int getSubmatrixSum(const vector<vector<int>>& prefixSum, int i, int j, int s, int t)
{ // 使用前缀和公式计算子矩阵和
return prefixSum[s + 1][t + 1] - prefixSum[i][t + 1] - prefixSum[s + 1][j] + prefixSum[i][j];
// 可以在 O(1) 时间内得到任意区间（或子矩阵）的和。
int main_11()
{
int m{}, n{};
cout << "请输入矩阵行数m列数n(2 < m, n < 100): ";
cin >> m >> n;
// 检查矩阵大小是否合法
if (m <= 2 || n <= 2 || m >= 100 || n >= 100)
{
cout << " 行数或者列数不符合要求！\n";
return 1;
}
vector<vector<int>> matrix(m, vector<int>(n));
cout << "请输入矩阵元素：\n";
for (int i{}; i < m; ++i)
{
for (int j{}; j < n; ++j)
{
cin >> matrix[i][j];
}
}
// 计算前缀和
vector<vector<int>> prefixSum = computePrefixSum(matrix);
// 处理子矩阵查询
int testCases{};
cout << "请输入要测试的子矩阵个数：";
cin >> testCases;
// 查询并输出每个子矩阵的和
for (int k{}; k < testCases; ++k)
{
int i, j, s, t;
cout << "请输入第 " << k + 1 << " 个子矩阵的左上角坐标(i, j) 和右下角坐标(s, t):";
cin >> i >> j >> s >> t;
// 将输入的坐标转换成从0开始的索引
--i; --j; --s; --t;
// 验证坐标是否有效
if (i < 0 || j < 0 || s >= m || t >= n || i > s || j > t)
{
cout << "坐标输入错误！\n";
continue;
}
int sum{ getSubmatrixSum(prefixSum, i, j, s, t) };
cout << "子矩阵的和是：" << sum << '\n';
}
return 0;
}