当前位置：首页 > news >正文

差分和前缀和

news 2025/7/14 15:53:17

差分和前缀和的原理、用法和区别。

前缀和（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