前缀和算法通过预处理数组或矩阵，将区间查询的时间复杂度从 O(n) 降低至 O(1)。文章详细讲解了基础的一维前缀和模板、二维前缀和计算及状态转移方程。结合 LeetCode 经典例题，如寻找数组中心下标、除自身以外数组的乘积、和为 K 的子数组等，演示了前缀和与前缀积在哈希表配合下的应用技巧。重点分析了边界处理、负数取模修正及空间优化策略，提供 C++ 代码实现，帮助读者掌握高效解决区间求和及相关变体问题的核心方法。
题目：DP34.【模板】前缀和
示例 1 输入：
输出：
每次询问时，求出该区间的和以及包含多少个 q，并计算其重复次数，所消耗时间复杂度 O(n*q)。
前缀和是用于'快速得到某一段区间的和'，所需要消耗时间复杂度为 O(q+n)。
通过 arr 数组和'前缀和数组'之间关系，没有必要重新遍历 arr 数组求和，再填写到'前缀和数组'内，其中推导出递推公式：dp[i] = dp[i - 1] + add[i]。
预处理前缀和数组的过程，本质上就是个小的动态规划。无非就是状态标识，状态转移方程。
使用前缀和数组，'快速'求出'某一个区间内'所有元素的和：当询问的区间是 [l, r] 时：区间内所有元素的和为：dp[r] - dp[l - 1]。
默认情况下，C++ 中
vector<int> dp(n + 1)会将dp数组的所有元素初始化为0，因此dp[0]也是0。
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 1. 读取数据
int n, q;
cin >> n >> q;
vector<int> arr(n + 1);
// 输入原始数组
for (int i = 1; i <= n; i++) cin >> arr[i];
// 2. 预处理出来一个前缀和数组
vector<long long> dp(n + 1);
// 防止溢出
// 输入 DP 数组数据
for (int i = 1; i <= n; i++) dp[i] = dp[i - 1] + arr[i];
int l = 0, r = 0;
while (q--) {
cin >> l >> r;
cout << dp[r] - dp[l - 1] << endl;
}
return 0;
}
细节问题：为什么下标从 1 开始计数？
通过 [0, 2] 和 [1,2] 分析可得，dp[-1] 下标是负数存在越界访问，dp[0] 也需要单独赋值。不然下标 1 开始计算，解决了上面两个问题。
输入：
输出：
算法思路
其中，我们需要知道 dp[i][j] 元素表达含有，更好地去使用前缀和矩阵解决问题。
dp[i][j] 表示：从 [1, 1] 位置到 [i, j] 位置，这段区间里面所有元素的和
不理解为什么是从 [1, 1] 位置开始，可以结合上一道题目解析和本题数据氛围限制理解。
根据 dp[i][j] 元素的含义，推导其状态转移方程，分析是否存在等价关系，或者从前状态推导出后状态。在推导过程中，要注意细节，特别是从 dp[i-1][j-1] 或者面积的组合角度入手，确保理解 dp[i][j] 的具体含义。
细节问题：这里 D 面积是 [x1, y1] -> [x2, y2]，而对于 A 面积是 [1, 1] -> [x1 -1, y1 - 1]，注意看红色的线。
代码实现
#include <iostream>
using namespace std;
#include <vector>
int main() {
int n = 0, m = 0, q = 0;
cin >> n >> m >> q;
// 1. 读入数据
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];
// 2. 处理前缀和矩阵
vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
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] + arr[i][j] - dp[i - 1][j - 1];
// 3. 使用前缀和矩阵
int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
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;
}
算法思路
使用前缀和算法时，不能死记硬背模板，关键是理解其思想，并根据具体问题灵活调整。模板中的算法思路可以为我们提供思路，但需要根据题目微调。
对于需要快速统计某个元素之前或之后所有元素和的情况，可以分别构建前缀和矩阵和后缀和矩阵。通过图示帮助分析问题，提升理解与解决效率。
个人思考：在推导状态转移方程时，首先理解当前定义的含义，并从前后元素的关系入手，逐步构建方程。举个例子，假设 f[i] 表示区间 [0, i-1] 所有元素的和，那么 f[i-1] 表示区间 [0, i-2] 的和。为了使 f[i] 满足其定义，我们需要将 nums[i-1] 加入，从而得到状态转移方程。
细节问题：
代码实现：
class Solution {
public:
int pivotIndex(vector<int>& nums) {
int n = nums.size();
vector<int> f(n);
vector<int> 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 (f[i] == g[i]) return i;
return -1;
}
};
从下标 1 到 n-2 开始处理，因为下标 0 和 n-1 对应的数据已经特殊处理为 0，且没有实际意义。如果从下标 0 或 n-1 开始，可能会导致越界访问。
算法思路
直接暴力枚举，从从前往后遍历，枚举每一个位置需要 O（n），同时需要遍历每个数组，整体时间复杂度是个 N 方级别的。
如果需要用到前后数据元素积，我们需要搭建前缀积矩阵与后缀积矩阵。
'这个题和'724. 寻找数组的中心下标'的算法思路非常相似，主要区别在于细节处理，尤其是临界元素的取值问题。根据 f[i] = f[i-1] + nums[i-1] 的规律，当 i = 1 时，必须设定 f[0] = 1，以确保 f[1] 表示区间 [0, 0] 对应的原始数据 nums[0]，因为 1 乘任何数都等于它本身。
在'除自身以外数组的乘积'的解法中，我们不需要计算每个元素前面和后面的乘积，而是通过前缀积 f[i] 和后缀积 g[i] 来在每个位置 i 计算出左边和右边的乘积，从而避免了除法的使用。
最终每个 output[i] 的值是 f[i] * g[i]，这就得到了除 nums[i] 外的所有元素的乘积。
代码实现
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> f(n), g(n);
f[0] = g[n - 1] = 1;
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];
vector<int> ret(n);
for (int i = 0; i < n; i++) ret[i] = f[i] * g[i];
return ret;
}
};
算法思路
如果使用暴力枚举可以解决这道问题，但是我们可以有更好的解法。
'返回和为 k 的子数组个数'这类问题，我们可以通过'前缀和 + 哈希表'来优化。一个关键的思路是'以 i 位置为结尾的所有子数组'。
实际上，问题本质上仍然是暴力枚举的思路，之前我们是'以 i 位置为开始的所有子数组'。之所以选择'以 i 位置为结尾的子数组'，是因为我们想使用'前缀和 + 哈希表'来快速求出子数组的和。通过这种方式，我们能够高效地统计子数组的次数。
如果使用'以 i 位置为开始的子数组'，我们需要从已知位置向未知位置查找，不容易统计之前出现的子数组。而'以 i 位置为结尾的子数组'则是从未知位置向已知位置查找，可以通过哈希表来快速得出子数组和，提升效率。
问题转化为前缀和，就是之前前缀和数据可以重复使用，多转一。
魔鬼细节问题
sum[i] - k 含义
对于某个 i 位置，考虑到子数组和为 k 的问题，可以通过等价关系转化为：找出多少个前缀和等于 sum[i] - k。这里的 sum[i] - k 不是固定值，而是动态计算得到的。通过不断更新的前缀和，我们可以找到符合条件的子数组数量，判断以 i 位置为结尾的子数组和是否等于 k。
前缀和加入哈希表时机 在计算第 i 个位置之前，哈希表仅保存位置 [0, i-1] 的前缀和。如果提前将元素加入前缀和，效果不如直接暴力枚举，且会导致哈希表统计位置时出现问题。
不用真的创建一个前缀和数组
dp[i] = dp[i - 1] + nums[i]，这里无需额外创建前缀和数组来存储数据，哈希表负责处理前缀和。通过遍历一次前缀和并建立哈希表的映射关系即可。
默认前缀和全部等于 k
哈希表在后续统计时，如果 count(x) == 0，可能导致无法正确统计。因此，单独设置 hash[0] = 1 是为了避免这种情况。没有 hash[0] = 1 时，程序会缺少一个初始的前缀和 0。假设某个子数组的和恰好等于 k，且该子数组从数组的开头开始，如果没有这个初始前缀和 0，就无法通过 hash[sum - k] 条件识别这个子数组。
代码实现
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> hash;
int sum = 0, ret = 0;
hash[0] = 1; // 确保第一个数
for (auto x : nums) {
sum += x;
if (hash.count(sum - k)) ret += hash[sum - k];
hash[sum]++;
}
return ret;
}
};
算法思路
本题算法数量同'560. 和为 K 的子数组'类似，重点在于细节处理上。
补充知识：同余定理
这里只需要记住结论：(a - b) / p = k ....0 -> a% p = b% p
C++, Java：[负数 % 正数] 的结果以及修正
本题思路：
找到在 [0, i - 1] 区间内，有多少前缀和的余数 (x% k) 等于 sum[i] % k 的即可。
细节问题
代码实现
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
unordered_map<int, int> hash;
hash[0 % k]++;
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;
}
};
题目：525. 连续数组
算法思路
本题要求找出一个连续子数组，使得其中 0 和 1 的数量相等。
0 记为 -1，1 记为 1，问题就转化为寻找一个和为 0 的子数组。细节问题
默认前缀和为 0 的情况
当前缀和为 0 时，如果不做处理，无法正确计算子数组的长度。之所以设置 hash[0] = -1，是因为在计算子数组长度时，i - j 代表的是当前位置和前一个位置的差。为了能够正确计算从数组起始位置到当前下标的子数组长度，我们默认前缀和为 0 时的下标是 -1。
哈希表存储 hash<int_前缀和，int_下标>
如果有重复<sum, i>
只保留前面那一对<sum, i>。
代码实现
class Solution {
public:
int findMaxLength(vector<int>& nums) {
unordered_map<int, int> hash;
hash[0] = -1; // 默认有一个前缀和为 0 的情况
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;
}
};
题目：1314. 矩阵区域和
算法思路
该题目中需要计算'矩阵前缀和'，需要结合'【模板】二维前缀和'里面关于矩阵前缀和计算和使用。
通过
以下是模板，不用死记硬背，画图可以很快推理出来
计算矩阵前缀和：dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + mat[i - 1][j - 1];
使用部分矩阵前缀和：answer[i][j] = dp[x2][y2] - dp[x2][y1 -1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
细节问题
这里主要体现为 mat[i][j] 映射到 mat[i - 1][j - 1]，由于 dp 表的索引是从 1 开始，因此 x1、x2、y1、y2 都需要加 1 来适配原始矩阵的 0-based 索引。
class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
int m = mat.size(), n = mat[0].size();
// 创建 dp 表
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
// 填充 dp 表数据
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
// mat[i - 1][j - 1], 映射 mat 表格下标
int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
// 使用 dp 表填充新表格进行返回
vector<vector<int>> answer(m, vector<int>(n));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
x1 = max(i - k, 0) + 1;
y1 = max(j - k, 0) + 1;
x2 = min(i + k, m - 1) + 1;
y2 = min(j + k, n - 1) + 1;
answer[i][j] = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
}
return answer;
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online