【算法】一维二维数组前缀和，以及计算二维矩阵中的子矩阵和

前缀和的概念

通过构建一个前缀和数组，我们可以在常数时间（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+1for (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[1][1] = matrix[0][0] = 1
prefixSum[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] 补回重复减掉的部分。

示例计算
矩阵：

目标子矩阵：从 (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)的前缀和矩阵，初始化为0vector<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;
}