1. 引言
想象一下：你在赛场上拿到一道题，其他选手都在疯狂卡常（比如用$O(n^2)$暴力），而你因为提前掌握了前缀和优化，瞬间把复杂度降到$O(n)$，轻松AC。这就是省一等奖和铜牌选手的关键差距！今天咱们就深挖一个能让你"降维打击"的核心技巧——前缀和与差分，解决那些让你抓狂的区间查询问题。
2. 核心概念讲解
前缀和（Prefix Sum）就是预先计算数组的前缀累加值，比如数组[a,b,c]的前缀和是[0, a, a+b, a+b+c]。查询区间[l,r]的和时，直接sum[r] - sum[l-1]，时间从$O(r-l+1)$降到$O(1)$！
差分（Difference Array）是前缀和的逆操作：对原数组做差分时，修改某个位置x的值delta，只需在差分数组diff[x]+=delta和diff[x+1]-=delta。还原原数组时再求前缀和即可。
图示对比：
原始数组: [3, 1, 4, 2]
前缀和: [0, 3, 4, 8, 10]
差分数组: [3, -2, 3, -2, 0]
3. C++代码示例
#include <bits/stdc++.h>
using namespace std;
// 构建前缀和数组
vector<int> buildPrefixSum(const vector<int>& arr) {
int n = arr.size();
vector<int> prefix(n + 1, 0);
for (int i = 1; i <= n; ++i) {
prefix[i] = prefix[i-1] + arr[i-1];
}
return prefix;
}
// 查询区间和 [l, r] (1-based)
int queryRangeSum(const vector<int>& prefix, int l, int r) {
if (l < 1 || r > prefix.size()-1) return 0;
return prefix[r] - prefix[l-1];
}
// 初始化差分数组（等于原数组）
vector<int> initDiffArray(const vector<int>& arr) {
int n = arr.size();
vector<int> diff(n + 1, 0); // 多开一位避免越界
diff[1] = arr[0]; // 1-based索引
for (int i = 2; i <= n; ++i) {
diff[i] = arr[i-1] - arr[i-2]; // arr[i-1]对应diff[i]
}
return diff;
}
// 差分更新（给arr[x]增加delta，0-based输入）
void diffUpdate(vector<int>& diff, int x, int delta) {
if (x < 0 || x >= diff.size()) return;
diff[x+1] += delta; // 注意：diff是1-based的
if (x+2 < diff.size()) diff[x+2] -= delta;
}
// 通过差分数组还原原数组
vector<int> restoreArray(const vector<int>& diff) {
int n = diff.size() - 1; // diff大小为n+1
vector<int> arr(n);
arr[0] = diff[1]; // arr[0] = diff[1]
for (int i = 1; i < n; ++i) {
arr[i] = arr[i-1] + diff[i+1];
}
return arr;
}
int main() {
// 测试用例：原始数组 [1, 2, 3, 4]
vector<int> arr = {1, 2, 3, 4};
// --- 前缀和操作 ---
auto prefix = buildPrefixSum(arr);
cout << "前缀和数组: ";
for (auto v : prefix) cout << v << " "; // 输出 0 1 3 6 10
cout << "\n查询[2,4]: " << queryRangeSum(prefix, 2, 4) << endl; // 输出 9 (2+3+4)
// --- 差分操作 ---
auto diff = initDiffArray(arr);
cout << "\n初始差分数组: ";
for (int i = 1; i <= arr.size(); ++i)
cout << diff[i] << " "; // 输出 1 1 1 1 0
// 给arr[2]加5（0-based）
diffUpdate(diff, 2, 5);
cout << "\n修改后差分数组: ";
for (int i = 1; i <= arr.size(); ++i)
cout << diff[i] << " "; // 输出 1 1 6 1 0
// 还原修改后的数组
auto newArr = restoreArray(diff);
cout << "\n新数组: ";
for (auto v : newArr) cout << v << " "; // 输出 1 2 8 4
return 0;
}
4. 算法分析
| 操作 | 时间复杂度 | 空间复杂度 | 备注 |
|——————–|————|————|——————————|
| 构建前缀和 | $O(n)$ | $O(n)$ | 需预处理 |
| 区间和查询 | $O(1)$ | - | 仅适用于可逆运算（如求和） |
| 差分数组初始化 | $O(n)$ | $O(n)$ | |
| 单点差分更新 | $O(1)$ | - | 批量修改神器 |
| 还原原数组 | $O(n)$ | $O(n)$ | 必须执行 |
适用场景：
频繁区间求和（如统计子段和、区间平均值）
批量区间增减（如给$[l,r]$所有元素加$delta$）
局限性：
不适用于不可逆运算（如最大值、最小值、乘积）
若数据频繁随机修改且无规律，效率低于线段树/树状数组
5. 经典例题
洛谷P1117【数列的零界】（差分应用）
给定初始数组和操作序列，每次对区间$[l,r]$的所有元素加$delta$，最后询问最终数组。
思路：
初始化差分数组
diff为arr的差分表示对每个操作
update(l, r, delta)执行diff[l] += delta; diff[r+1] -= delta最后通过
restoreArray(diff)还原最终数组
6. 推荐练习
入门：洛谷P1197【模板】前缀和
进阶：CF1235CArray and Operations （差分批量修改）
挑战：AtCoder ABC228DScore of Students （前缀和+离散化）
7. 小结
一句话总结：前缀和是区间求和的神器，差分是批量修改的黑魔法！下次见到"频繁区间操作"的问题，先想想能不能用它们。
预告：下期我们将学习更强大的数据结构——树状数组，实现$O(\log n)$的查询和修改！