差分算法
一、 复习一维前缀和
定义：
前缀和数组 s[i] 表示原数组 a[0] 到 a[i] 的和：
s[i] = a[0] + a[1] + ... + a[i]
应用场景：
- 快速计算区间
[l, r]的和：sum = s[r] - s[l-1] - 时间复杂度：预处理 O(n)，查询 O(1)。
// 前缀和复习代码
int a[] = {0,1,3,5,7,9}; // 原始数组（1-based）
int b[6] = {0}; // 前缀和数组
for(int i=1; i<=5; i++)
b[i] = b[i-1] + a[i];
// b[3] = 1+3+5=9
二、差分引入
问题场景：对数组进行m次区间加减操作，最后输出数组元素
- 暴力法：O(mn)
- 差分优化：O(m+n)
差分定义：
- 原数组a的差分数组d满足： d[i] = a[i] - a[i-1] (i≥1)
- 前缀和与差分互为逆运算
容易发现，前缀和 与 差分 是一对互逆运算。
也就是说：
如果数列 ( a ) 的差分序列是 ( d )，那数列 ( a ) 的前缀和就是 ( b )。
公式推导如下：
所以，( A_i ) 表示 ( D ) 序列前 ( i ) 个元素的和。
即：( A ) 数列是 ( D ) 数列的前缀和。
比如下面的例子，说明了前缀和与差分之间的互逆关系。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
| A | 3 | 5 | 2 | 1 | 8 | 10 | 3 | 4 |
| D | 3 | 2 | -3 | -1 | 7 | 2 | -7 | 1 |
| B | 3 | 5 | 2 | 1 | 8 | 10 | 3 | 4 |
前缀和与差分的互逆关系
三、差分处理区间修改
核心思想：
- 对区间
[l, r]加k，只需修改差分数组的两个位置：d[l] += kd[r+1] -= k（若r+1超出数组范围则省略）
数学解释：
d[l] += k会导致前缀和计算时，a[l], a[l+1], ..., a[n-1]全部加k。d[r+1] -= k抵消了a[r+1]及之后的元素的多余增量，确保只有[l, r]被修改。
示例：
初始差分数组 d = [1, 2, -1, 3, 2]
对区间 [1, 3] 加 3：
d[1] += 3→d[1] = 5d[4] -= 3→d[4] = -1
新差分数组：[1, 5, -1, 3, -1]
前缀和恢复：[1, 6, 5, 8, 7]
四、算法实现
差分模板：
#include <iostream>
using namespace std;
const int N = 1e5+10;
int a[N], d[N]; // 原数组和差分数组
// 构造差分数组
void init(int n) {
for(int i=1; i<=n; i++) {
d[i] = a[i] - a[i-1];
}
}
// 区间[l,r]加c
void add(int l, int r, int c) {
d[l] += c;
d[r+1] -= c;
}
// 通过差分数组还原数组
void restore(int n) {
for(int i=1; i<=n; i++) {
a[i] = a[i-1] + d[i];
}
}
int main() {
int n = 5; // 示例数组长度
// 初始化原始数组（1-based）
for(int i=1; i<=n; i++)
a[i] = 0;
// 构造初始差分数组
init(n);
// 执行区间操作示例
add(2,4,3); // [2,4]加3
add(1,5,1); // 全体加1
// 还原数组
restore(n);
// 输出结果：1 4 4 4 1
for(int i=1; i<=n; i++)
cout << a[i] << " ";
return 0;
}
1、例题解析
题目描述： 初始全零数组，进行3次操作：
- [1,3] 加2
- [2,4] 加-1
- [3,5] 加3 求最终数组
差分处理：
// 创建全零差分数组
memset(d,0,sizeof d);
add(1,3,2); // d[1]+=2, d[4]-=2
add(2,4,-1); // d[2]+=-1, d[5]-=-1
add(3,5,3); // d[3]+=3, d[6]-=3
restore(5);
// 输出结果：2 1 4 2 3
2、练习一
3、小结
差分三要素：
1. 差分数组定义：d[i] = a[i] - a[i-1]
2. 区间修改：d[l] +=c, d[r+1] -=c
3. 前缀还原：a[i] = a[i-1] + d[i]
边界处理与注意事项:
1. **数组越界**：若 `r` 是最后一个元素，`r+1` 超出数组范围时，无需执行 `d[r+1] -= k`。
2. **索引问题**：根据题目要求明确索引是 0-based 还是 1-based。
3. **初始数组为 0 的特殊情况**：直接初始化差分数组为全 0，无需额外计算。