差分和前缀和的原理、用法和区别。
前缀和(Prefix Sum)
核心思想:预处理数组的前缀和,快速回答「区间和查询」
适用场景:数组静态(更新少、查询多),需要频繁计算任意区间的和
1. 定义与构建
对于原数组 a[0...n-1] ,前缀和数组 preSum 满足:
preSum[i] = a[0] + a[1] + ... + a[i-1]
( preSum[0] = 0 ,方便边界计算)
构建代码:
vector<long long> buildPreSum(vector<int>& a) {
int n = a.size();
vector<long long> preSum(n + 1, 0);
for (int i = 0; i < n; ++i) {
preSum[i + 1] = preSum[i] + a[i];
}
return preSum;
}
2. 核心作用:O(1) 区间和查询
原数组区间 [l, r] (闭区间)的和为:
sum(l, r) = preSum[r + 1] - preSum[l]
示例:
原数组 a = [1, 2, 3, 4] ,则 preSum = [0, 1, 3, 6, 10]
查询 a[1..3] (元素 2,3,4 )的和: preSum[4] - preSum[1] = 10 - 1 = 9
差分(Difference Array)
核心思想:预处理差分数组,快速执行「区间更新」
适用场景:数组动态(更新多、查询少),需要频繁对区间进行加减操作
1. 定义与构建对于原数组
a[0...n-1] ,差分数组 diff 满足:
diff[i] = \begin{cases}
a[0] & (i=0) \\
a[i] - a[i-1] & (i>0)
\end{cases}
构建代码(直接初始化,或从原数组推导):
vector<int> buildDiff(vector<int>& a) {
int n = a.size();
vector<int> diff(n, 0);
diff[0] = a[0];
for (int i = 1; i < n; ++i) {
diff[i] = a[i] - a[i-1];
}
return diff;
}
2. 核心操作:O(1) 区间更新
对原数组 a 的区间 [l, r] 全部加 val ,只需操作差分数组:
diff[l] += val; // 起点 l 开始有增量
if (r + 1 < n) {
diff[r + 1] -= val; // 终点 r+1 处取消增量(防止扩散到区间外)
}
原理:差分数组记录的是「相邻元素的变化量」。当通过前缀和还原原数组时, diff[l] += val 的影响会传递到 a[l..n-1] ,而 diff[r+1] -= val 会抵消 r+1 之后的影响,最终只有 a[l..r] 被加上 val 。
3. 还原原数组(从差分 → 原数组)
对差分数组求前缀和,即可还原原数组:
vector<int> restoreArray(vector<int>& diff) {
int n = diff.size();
vector<int> a(n, 0);
a[0] = diff[0];
for (int i = 1; i < n; ++i) {
a[i] = a[i-1] + diff[i];
}
return a;
}
或更高效的原地操作(差分数组直接变原数组):
for (int i = 1; i < n; ++i) {
diff[i] += diff[i-1];
}
// 此时 diff 数组等价于原数组 a
前缀和 vs 差分:核心区别
特性 前缀和(Prefix Sum) 差分(Difference Array)
核心用途 快速查询区间和(静态数组) 快速执行区间更新(动态数组)
操作对象 原数组 → 前缀和数组(预处理) 原数组 → 差分数组(预处理)
时间复杂度 构建 O(n),查询 O(1) 构建 O(n),区间更新 O(1),还原 O(n)
典型场景 数组不变,频繁查区间和(如 LeetCode 560) 数组常变,频繁对区间加减(如 LeetCode 1109)
综合示例:前缀和 + 差分
题目:
1. 初始数组 a = [1, 2, 3, 4]
2. 对区间 [1, 3] (元素 2,3,4 )加 5
3. 查询最终数组的区间 [0, 2] (元素 1,7,8 )的和
步骤 1:用差分执行区间更新
原数组 a = [1, 2, 3, 4] ,构建差分数组:
diff = [1, 1, 1, 1] // 因为 2-1=1, 3-2=1, 4-3=1
对区间 [1, 3] 加 5 :
diff[1] += 5; // diff[1] = 6
if (3+1 < 4) diff[4] -=5; // 数组长度 4,r+1=4 越界,无需操作
此时差分数组 diff = [1, 6, 1, 1]
步骤 2:还原原数组(差分 → 原数组)
对 diff 求前缀和:
a[0] = 1
a[1] = 1 + 6 = 7
a[2] = 7 + 1 = 8
a[3] = 8 + 1 = 9
还原后数组 a = [1, 7, 8, 9]
步骤 3:用前缀和查询区间和
构建前缀和数组 preSum :
preSum = [0, 1, 8, 16, 25]
查询区间 [0, 2] 的和:
sum = preSum[3] - preSum[0] = 16 - 0 = 16
总结
- 前缀和是「区间和查询」的优化工具,适合数组静态、查询频繁的场景。
- 差分是「区间更新」的优化工具,适合数组动态、更新频繁的场景。
- 两者常配合使用:用差分处理更新,再用前缀和处理查询,覆盖更复杂的需求。
理解这两个技巧的核心逻辑后,很多数组操作的题目(尤其是竞赛题)都能迎刃而解。