跳到主要内容
前缀和算法详解:从一维到二维的实战应用 | 极客日志
C++ 算法
前缀和算法详解:从一维到二维的实战应用 前缀和是一种通过预处理将区间查询复杂度降为 O(1) 的高效算法。本文涵盖了一维及二维前缀和的原理推导与代码实现,重点讲解了边界处理与坐标映射技巧。此外,结合哈希表扩展了前缀和的应用场景,包括寻找数组中心下标、计算除自身外数组乘积、统计和为 K 的子数组及其变体(整除、连续数组),以及矩阵区域和问题。内容包含 C++ 完整示例,适合算法初学者进阶阅读。
前缀和相关题解
1. 一维前缀和
核心思路:
处理区间求和问题时,暴力枚举会导致 O(N^2) 的时间复杂度。通过预处理一个前缀和数组,我们可以将单次查询优化至 O(1)。
定义 dp[i] 为区间 [1, i] 内所有元素的累加和。那么 dp[i-1] 自然存储了 [1, i-1] 的和。由此可得递推公式:
dp[i] = dp[i-1] + arr[i]
当需要计算区间 [l, r] 的和时,利用容斥原理,结果即为 dp[r] - dp[l-1]。
#include <iostream>
#include <vector>
using namespace std;
int main () {
int n, q;
cin >> n >> q;
vector<int > arr (n + 1 ) ;
for (int i = 1 ; i <= n; i++) {
cin >> arr[i];
}
vector<long long > dp (n + 1 , 0 ) ;
for (int i = 1 ; i <= n; i++) {
dp[i] = dp[i - 1 ] + arr[i];
}
int l, r;
while (q--) {
cin >> l >> r;
cout << dp[r] - dp[l - 1 ] << endl;
}
return ;
}
0
2. 二维前缀和 一维的扩展。若我们能计算出从 (0, 0) 到 (i, j) 矩形区域内所有元素的累加和,就能在 O(1) 时间内获取任意子矩阵的和。
为了简化边界判断,通常在原矩阵外围添加一行和一列 0。这样 DP 表的下标直接从 1 开始,无需特殊处理 i=0 或 j=0 的情况。
DP 表 sum[i][j] 对应原矩阵 matrix[i-1][j-1]。
sum[i][j] 表示左上角 (0,0) 到右下角 (i,j) 的红色区域和。
递推方程:
观察图形分解,sum[i][j] 可以看作:
sum[i-1][j] (上方矩形) + sum[i][j-1] (左方矩形) - sum[i-1][j-1] (重叠部分) + matrix[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]
查询操作:
给定左上角 (row1, col1) 和右下角 (row2, col2),对应的 DP 表下标需相应调整。利用容斥原理:
Result = 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<int >> arr (n + 1 , vector <int >(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 - 1 ][j] + dp[i][j - 1 ] - dp[i - 1 ][j - 1 ] + arr[i][j];
}
}
int x1, y1, x2, y2;
while (q--) {
cin >> x1 >> y1 >> x2 >> y2;
cout << dp[x2][y2] - dp[x1 - 1 ][y2] - dp[x2][y1 - 1 ] + dp[x1 - 1 ][y1 - 1 ] << endl;
}
return 0 ;
}
3. 寻找数组的中心下标 思路:
中心下标左侧元素之和等于右侧元素之和。我们可以分别预处理前缀和与后缀和数组,然后遍历查找相等的位置。
class Solution {
public :
int pivotIndex (vector<int >& nums) {
int n = nums.size ();
vector<int > f (n) , g (n) ;
for (int i = 1 ; i < n; i++) {
f[i] = f[i - 1 ] + nums[i - 1 ];
}
for (int i = n - 2 ; i >= 0 ; i--) {
g[i] = g[i + 1 ] + nums[i + 1 ];
}
for (int i = 0 ; i < n; i++) {
if (g[i] == f[i]) return i;
}
return -1 ;
}
};
4. 除自身以外数组的乘积 思路:
题目限制不能使用除法且要求 O(N) 时间。对于每个位置 i,结果由两部分组成:i 左侧所有数的乘积 × i 右侧所有数的乘积。
利用类似前缀和的思想,用两个数组分别记录前缀乘积和后缀乘积。
class Solution {
public :
vector<int > productExceptSelf (vector<int >& nums) {
int n = nums.size ();
vector<int > f (n, 1 ) , g (n, 1 ) , ans (n) ;
for (int i = 1 ; i < n; i++) {
f[i] = f[i - 1 ] * nums[i - 1 ];
}
for (int i = n - 2 ; i >= 0 ; i--) {
g[i] = g[i + 1 ] * nums[i + 1 ];
}
for (int i = 0 ; i < n; i++) {
ans[i] = f[i] * g[i];
}
return ans;
}
};
5. 和为 K 的子数组 思路:
设 sum[i] 为 [0, i] 的前缀和。若存在起始位置 x 使得 [x, i] 的和为 k,则 sum[i] - sum[x-1] = k,即 sum[x-1] = sum[i] - k。
问题转化为:在当前位置之前,有多少个前缀和等于 sum[i] - k?使用哈希表统计前缀和出现的次数即可。
class Solution {
public :
int subarraySum (vector<int >& nums, int k) {
unordered_map<int , int > hash;
hash[0 ] = 1 ;
int sum = 0 , ret = 0 ;
for (auto x : nums) {
sum += x;
if (hash.count (sum - k)) {
ret += hash[sum - k];
}
hash[sum]++;
}
return ret;
}
};
6. 和可被 K 整除的子数组 前置知识:
同余定理:若 (a - b) % n == 0,则 a % n == b % n。
C++ 取模陷阱:
C++ 中负数取模结果为负(如 -1 % 3 = -1)。为保证余数为正,统一使用 (a % n + n) % n。
思路:
与上一题类似,只需判断前缀和的余数是否相同。若 sum[i] % k == sum[x-1] % k,则中间段可被 k 整除。
class Solution {
public :
int subarraysDivByK (vector<int >& nums, int k) {
unordered_map<int , int > hash;
hash[0 ] = 1 ;
int sum = 0 , ret = 0 ;
for (auto x : nums) {
sum += x;
int r = (sum % k + k) % k;
if (hash.count (r)) {
ret += hash[r];
}
hash[r]++;
}
return ret;
}
};
7. 连续数组 思路:
将 0 视为 -1,1 视为 1。问题转化为寻找最长的子数组,其元素和为 0。
这依然是前缀和的应用。若 sum[i] == sum[x-1],则区间 [x, i] 的和为 0。我们需要记录每个前缀和第一次出现的位置,以最大化长度。
class Solution {
public :
int findMaxLength (vector<int >& nums) {
unordered_map<int , int > hash;
hash[0 ] = -1 ;
int sum = 0 , ret = 0 ;
for (int i = 0 ; i < nums.size (); i++) {
sum += (nums[i] == 0 ? -1 : 1 );
if (hash.count (sum)) {
ret = max (ret, i - hash[sum]);
} else {
hash[sum] = i;
}
}
return ret;
}
};
8. 矩阵区域和 思路:
基于二维前缀和。对于矩阵中每个点 (i, j),需要计算以它为中心、半径为 k 的矩形区域和。
左上角坐标:max(0, i-k), max(0, j-k)
右下角坐标:min(m-1, i+k), min(n-1, j+k)
注意 DP 表是 1-based 的,计算时需进行下标偏移。
class Solution {
public :
vector<vector<int >> matrixBlockSum (vector<vector<int >>& mat, int k) {
int m = mat.size (), n = mat[0 ].size ();
vector<vector<int >> dp (m + 1 , vector <int >(n + 1 , 0 ));
for (int i = 1 ; i <= m; i++) {
for (int j = 1 ; j <= n; j++) {
dp[i][j] = dp[i - 1 ][j] + dp[i][j - 1 ] - dp[i - 1 ][j - 1 ] + mat[i - 1 ][j - 1 ];
}
}
vector<vector<int >> ret (m, vector <int >(n));
for (int i = 0 ; i < m; i++) {
for (int j = 0 ; j < n; j++) {
int x1 = max (0 , i - k) + 1 ;
int y1 = max (0 , j - k) + 1 ;
int x2 = min (i + k, m - 1 ) + 1 ;
int y2 = min (j + k, n - 1 ) + 1 ;
ret[i][j] = dp[x2][y2] - dp[x1 - 1 ][y2] - dp[x2][y1 - 1 ] + dp[x1 - 1 ][y1 - 1 ];
}
}
return ret;
}
};
相关免费在线工具 加密/解密文本 使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
Markdown转HTML 将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
HTML转Markdown 将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online