前缀和与差分是算法竞赛和编程中非常重要的两种技巧，它们能够高效地处理区间查询和区间更新问题。本文将详细介绍这两种算法的原理、应用场景以及C++实现。
一、前缀和算法
1.1 前缀和的基本概念
前缀和（Prefix Sum）是一种预处理技术，它通过预先计算并存储数组的前缀和，使得后续的区间和查询可以在常数时间内完成。
给定一个数组arr，其前缀和数组prefix定义为：
prefix[i] = arr[0] + arr[1] + ... + arr[i]
特别地，prefix[0] = arr[0]。
1.2 前缀和的构建
以下是构建前缀和数组的C++实现：
vector<int> buildPrefixSum(const vector<int>& arr) {int n = arr.size();vector<int> prefix(n);prefix[0] = arr[0];for (int i = 1; i < n; i++) {prefix[i] = prefix[i-1] + arr[i];}return prefix;
}
1.3 前缀和的应用
前缀和最常见的应用是快速计算区间和。给定区间[L, R]，其和可以通过前缀和数组在O(1)时间内计算：
sum(L, R) = prefix[R] - (L > 0 ? prefix[L-1] : 0)
C++实现：
int rangeSum(const vector<int>& prefix, int L, int R) {if (L == 0) return prefix[R];return prefix[R] - prefix[L-1];
}
1.4 前缀和的变种
1.4.1 二维前缀和
对于二维数组，我们可以构建二维前缀和：
vector<vector<int>> build2DPrefixSum(const vector<vector<int>>& matrix) {int m = matrix.size(), n = matrix[0].size();vector<vector<int>> prefix(m, vector<int>(n));prefix[0][0] = matrix[0][0];for (int j = 1; j < n; j++) prefix[0][j] = prefix[0][j-1] + matrix[0][j];for (int i = 1; i < m; i++) prefix[i][0] = prefix[i-1][0] + matrix[i][0];for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i][j];}}return prefix;
}
计算子矩阵和的公式为：
sum(x1,y1,x2,y2) = prefix[x2][y2] - (x1>0 ? prefix[x1-1][y2] : 0) - (y1>0 ? prefix[x2][y1-1] : 0) + (x1>0 && y1>0 ? prefix[x1-1][y1-1] : 0)
1.4.2 前缀和的其他应用
前缀和还可以用于：
- 计算区间平均值
- 解决子数组和为特定值的问题
- 统计区间内满足某种条件的元素个数
二、差分算法
2.1 差分的基本概念
差分（Difference）是前缀和的逆运算，它主要用于高效处理区间更新操作。给定一个数组arr，其差分数组diff定义为：
diff[i] = arr[i] - arr[i-1] (i > 0)
diff[0] = arr[0]
2.2 差分的构建
以下是构建差分数组的C++实现：
vector<int> buildDifferenceArray(const vector<int>& arr) {int n = arr.size();vector<int> diff(n);diff[0] = arr[0];for (int i = 1; i < n; i++) {diff[i] = arr[i] - arr[i-1];}return diff;
}
2.3 差分的应用
差分最常见的应用是高效地进行区间更新。要对区间[L, R]内的所有元素增加val，只需要：
diff[L] += val
if (R + 1 < n) diff[R+1] -= val
C++实现：
void rangeAdd(vector<int>& diff, int L, int R, int val) {diff[L] += val;if (R + 1 < diff.size()) {diff[R+1] -= val;}
}
更新后，可以通过计算前缀和来恢复原始数组：
vector<int> recoverArray(const vector<int>& diff) {vector<int> arr(diff.size());arr[0] = diff[0];for (int i = 1; i < diff.size(); i++) {arr[i] = arr[i-1] + diff[i];}return arr;
}
2.4 差分的变种
2.4.1 二维差分
对于二维数组，我们可以使用二维差分来处理子矩阵的更新：
void rangeAdd2D(vector<vector<int>>& diff, int x1, int y1, int x2, int y2, int val) {diff[x1][y1] += val;if (x2 + 1 < diff.size()) diff[x2+1][y1] -= val;if (y2 + 1 < diff[0].size()) diff[x1][y2+1] -= val;if (x2 + 1 < diff.size() && y2 + 1 < diff[0].size()) diff[x2+1][y2+1] += val;
}
恢复二维数组：
vector<vector<int>> recover2DArray(vector<vector<int>>& diff) {int m = diff.size(), n = diff[0].size();vector<vector<int>> arr(m, vector<int>(n));arr[0][0] = diff[0][0];for (int j = 1; j < n; j++) arr[0][j] = arr[0][j-1] + diff[0][j];for (int i = 1; i < m; i++) arr[i][0] = arr[i-1][0] + diff[i][0];for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {arr[i][j] = arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1] + diff[i][j];}}return arr;
}
三、前缀和与差分的综合应用
3.1 区间更新+单点查询
使用差分数组可以高效实现区间更新，然后通过计算前缀和实现单点查询。
3.2 区间更新+区间查询
结合线段树或树状数组，可以实现更高效的区间更新和区间查询。
3.3 实际应用示例
问题描述：给定一个长度为n的数组，进行m次操作，每次操作将区间[L, R]内的元素增加val，最后输出最终的数组。
解决方案：
vector<int> rangeUpdates(int n, vector<vector<int>>& operations) {vector<int> diff(n, 0);for (auto& op : operations) {int L = op[0], R = op[1], val = op[2];diff[L] += val;if (R + 1 < n) diff[R+1] -= val;}vector<int> res(n);res[0] = diff[0];for (int i = 1; i < n; i++) {res[i] = res[i-1] + diff[i];}return res;
}
四、性能分析与比较
4.1 时间复杂度
- 前缀和：
- 构建：O(n)
- 查询：O(1)
- 差分：
- 构建：O(n)
- 更新：O(1)
- 恢复数组：O(n)
4.2 空间复杂度
两者都需要额外的O(n)空间存储前缀和或差分数组。
4.3 适用场景
- 前缀和：适用于查询多、更新少的场景
- 差分：适用于更新多、查询少的场景
五、总结
前缀和和差分是两种互补的算法技巧，它们在处理区间问题时表现出色。前缀和擅长快速计算区间和，而差分擅长高效进行区间更新。掌握这两种技巧可以大大提高解决相关算法问题的效率。
在实际应用中，我们常常需要根据问题的特点选择合适的算法，有时甚至需要将两者结合使用。理解它们的原理和实现方式，对于提升算法能力至关重要。
六、练习题
- 给定一个数组，求所有子数组的和的总和。
- 给定一个矩阵，求所有子矩阵的和的总和。
- 实现一个支持区间加法和区间求和的数据结构。
- 解决"最大子数组和"问题。
- 解决"和为K的子数组"问题。
希望这篇博客能帮助你深入理解前缀和与差分算法，并在实际编程中灵活运用它们。
怎么解决？)
