第 03 课 差分
专题定位：面向零基础信奥学生的一维差分入门。掌握“记录变化、最后还原”的核心思想。
学习目标：理解差分数组的定义；知道区间修改为什么只需要改两个端点；能够使用差分解决区间修改、序列增减和固定长度区间修改问题。
一、差分的概念与计算
1. 数学定义
给定一维数组：
定义差分数组：
也可以规定 \(a_0=0\)，统一写成：
diff[i] 表示从第 \(i-1\) 项到第 \(i\) 项时，数值发生了多少变化。
例如：
原数组： 3 3 5 8 8
差分数组： 3 0 2 3 0
因为：
一句话理解：原数组记录“每个位置是多少”，差分数组记录“从前一个位置走到这里变化了多少”。
2. 从原数组计算差分
使用 1-based 下标时：
int a[N]; // 1-based
int diff[N + 2]; // 编程实践中，首尾往往多开一项，方便计算
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
// 构造差分数组
diff[1] = a[1];
for (int i = 2; i <= n; i++) {
diff[i] = a[i] - a[i - 1];
}
如果已经保证 a[0] = 0，也可以统一写成：
a[0] = 0;
for (int i = 1; i <= n; i++) {
diff[i] = a[i] - a[i - 1];
}
3. 由差分恢复原数组
由定义：
移项得到：
所以从左到右累加差分即可恢复：
long long current = 0;
for (int i = 1; i <= n; i++) {
current += diff[i];
a[i] = current;
}
数学上：
证明：
中间项全部抵消，只剩下 \(a_i\)。
4. 复杂度
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 构造差分数组 | \(O(n)\) | \(O(n)\) |
| 恢复原数组 | \(O(n)\) | \(O(1)\)（直接覆盖原数组时） |
二、区间修改的原理
1. 问题形式
现在要把区间 \([L,R]\) 中的每个数都增加 \(K\)：
同时变成：
如果直接修改原数组，需要循环访问 \(L\) 到 \(R\) 的每一个位置，单次操作复杂度为 \(O(R-L+1)\)。
差分的想法是：不立即修改区间内的每个数，而是记录这次变化的开始位置和结束位置。
2. 两个端点的关键操作
只需修改：
diff[L] += K;
diff[R + 1] -= K;
含义是：
- 从第 \(L\) 项开始，后面的恢复值整体多出 \(K\)；
- 从第 \(R+1\) 项开始，把多出的 \(K\) 抵消掉。
注意: 因为修改第n个元素时，需要用到 \(diff[n + 1]\) ,此处用到了下标 \(n + 1\) ，所以差分数组一般会开辟 \(n + 2\)个空间，如
int diff[N+2]={}.
3. 端点示意图
从这里开始 +K 从这里开始 -K
↓ ↓
下标： 1 ... L-1 | L ....... R | R+1 ..... n
diff[L] += K： +K +K +K +K +K +K +K +K
diff[R+1] -= K： -K -K -K -K
求前缀和抵消： +K +K +K +K 0 0 0 0
也可以把它理解成一盏“向后射出的增量灯”：
第 L 项： 打开 +K
第 R+1 项： 关闭 -K
效果叠加后，只有区间 [L,R] 中的元素受到了“修改”效果。
4. 为什么能覆盖整个区间
设修改后的差分为 \(diff'\)，恢复后的数组为 \(a'\)。由于恢复过程是前缀和：
分三种情况：
| 位置 | 端点标记情况 | 最终结果 |
|---|---|---|
| \(i<L\) | 还没遇到 +K |
\(a'_i=a_i\) |
| \(L\le i\le R\) | 已遇到 +K，还没遇到 -K |
\(a'_i=a_i+K\) |
| \(i\ge R+1\) | +K 和 -K 都遇到了 |
\(a'_i=a_i+K-K=a_i\) |
因此，只有 \([L,R]\) 内的元素增加了 \(K\)。
必须记住：
\[ diff[L]\mathrel{+}=K,\qquad diff[R+1]\mathrel{-}=K. \]数组通常开到
n + 2，保证R + 1可以安全访问。
5. 与前缀和的区别
| 工具 | 主要解决的问题 | 核心动作 |
|---|---|---|
| 前缀和 | 多次查询区间和 | 预处理后用两个前缀相减 |
| 差分 | 多次修改连续区间 | 修改两个端点，最后求前缀和 |
三、差分的应用
1. 区间修改问题
（1）题目模型
给定 \(n\) 个整数，之后进行 \(q\) 次修改。每次给出 \(L,R,K\)，使区间 \([L,R]\) 中所有数增加 \(K\)。最后输出最终数组。
（2）解题步骤
- 先构造原数组的差分；
- 每次修改执行
diff[L] += K、diff[R + 1] -= K； - 所有修改结束后，从左到右累加
diff； - 累加结果就是最终数组。
样例变化：
初始： 6 6 1 2 3
[3,5] -8： 6 6 -7 -6 -5
[2,4] +6： 6 12 -1 0 -5
[1,2] +9： 15 21 -1 0 -5
（3）完整代码
#include <iostream>
using namespace std;
const int N = 100000 + 5;
int n, q;
long long a[N];
long long diff[N + 2];
int main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
// 构造差分数组
diff[1] = a[1];
for (int i = 2; i <= n; i++) {
diff[i] = a[i] - a[i - 1];
}
// 区间修改
for (int i = 1; i <= q; i++) {
int L, R;
long long K;
cin >> L >> R >> K;
diff[L] += K;
diff[R + 1] -= K;
}
// 求差分数组的前缀和，还原最终数组
for (int i = 1; i <= n; i++) {
diff[i] += diff[i - 1];
}
for (int i = 1; i <= n; i++) {
cout << diff[i] << (i == n ? '\n' : ' ');
}
return 0;
}
时间复杂度为 \(O(n+q)\)，空间复杂度为 \(O(n)\)。
这一题就是差分的标准模板。
2. 序列增减问题
（1）题目模型
给定一个数列。每次可以选择一个区间，使区间内所有数同时加 \(1\) 或同时减 \(1\)。求：
- 使整个数列变成相同的数，最少需要多少次操作；
- 在最少操作次数下，最终可能得到多少种不同的相同数列。
（2）转化为相邻差分
定义：
数列全部相同时，所有相邻差分必须为 \(0\)。
一次区间加 \(1\)，只会影响区间左端和右端后一位：
因此，这道题可以理解为：把所有相邻差分逐渐消成 \(0\)。
（3）正差额与负差额
统计：
对于 \([2,n]\) 中的每个 diff[i]：
- 优先匹配正差额和负差额。一次操作可以同时配对消掉一份正差额和一份负差额，匹配次数为
min(positive, negative)； - 剩余的只有正差额或负差额，需要单独处理。修改
diff[1]或diff[n+1]不影响最终序列是否相等，因此可以选择 \([1,i]\) 或 \([i,n]\) 来消掉剩余差额； - 综上，最少操作数为：
在最少操作下，单独的正差额或负差额可选择落在最终公共值的不同方向上，因此最终公共值的可能数量为：
例如：
数列：1 1 2 2
差分：0 1 0
- 把 \([3,4]\) 减 \(1\)，得到
1 1 1 1； - 把 \([1,2]\) 加 \(1\)，得到
2 2 2 2。
此时 positive = 1、negative = 0。所以最少操作数为 \(1\)，最终结果有 \(2\) 种。
（4）完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
int n;
long long a[N];
long long diff[N + 2];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
// 构造差分数组
for (int i = 1; i <= n; i++) {
diff[i] = a[i] - a[i - 1];
}
long long positive = 0, negative = 0;
for (int i = 2; i <= n; i++) {
if (diff[i] > 0) {
positive += diff[i];
} else {
negative -= diff[i];
}
}
cout << max(positive, negative) << '\n';
cout << abs(positive - negative) + 1 << '\n';
return 0;
}
时间复杂度为 \(O(n)\)。代码只统计相邻差分，不需要模拟每次区间操作。
3. 定长区间修改问题
（1）题目模型
有 \(n\) 个灯，初始状态和目标状态都是由 0、1 组成的字符串。每次只能翻转一个长度固定为 \(m\) 的连续区间：
0变成1；1变成0。
求最少翻转次数；如果无法完成，输出 \(-1\)。
（2）转化为异或差分
先比较初始串和目标串：
- 相同的位置记为
need = 0； - 不同的位置记为
need = 1。
当前位置被翻转奇数次就能改变状态，被翻转偶数次则等于没有改变。因此这里使用异或：
当从位置 \(i\) 开始翻转长度为 \(m\) 的区间时：
flip[i] ^= 1;
flip[i + m] ^= 1;
表示翻转效果从 \(i\) 开始生效，从 \(i+m\) 开始失效。
（3）为什么必须从左到右贪心
扫描到位置 \(i\) 时，起点大于 \(i\) 的长度为 \(m\) 的区间已经无法覆盖位置 \(i\)。因此：
- 如果当前位置已经匹配，就不能再从 \(i\) 翻转；
- 如果当前位置不匹配，就必须从 \(i\) 开始翻转；
- 如果剩余长度不足 \(m\)，则一定无解。
贪心正确性：当前位置的决定被题目强制，无法留给后面的位置补救；因此从左到右的选择不仅可行，而且是最优的。
（4）样例
初始：10101
目标：11011
第 2 到第 4 个灯翻转一次：
10101 → 11011
答案为 \(1\)。
（5）完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1000000 + 5;
int n, m;
int t[N];
int d[N + 2];
int main() {
cin >> n >> m;
string s1, s2;
cin >> s1 >> s2;
// t[i] 表示第 i 个位置是否需要翻转
for (int i = 1; i <= n; i++) {
t[i] = (s2[i - 1] - '0') ^ (s1[i - 1] - '0');
}
// 构造异或差分数组
t[0] = t[n + 1] = 0;
for (int i = 1; i <= n + 1; i++) {
d[i] = t[i] ^ t[i - 1];
}
// 自左向右调整，让 d[] 全部变为 0
int cnt = 0;
for (int i = 1; i + m <= n + 1; i++) {
if (d[i] == 1) {
cnt++;
d[i] ^= 1;
d[i + m] ^= 1;
}
}
// 检查是否全部消除
for (int i = 1; i <= n; i++) {
if (d[i] == 1) {
cout << -1;
return 0;
}
}
cout << cnt;
return 0;
}
时间复杂度为 \(O(n)\)，空间复杂度为 \(O(n)\)。
四、常见错误与注意事项
| 编号 | 错误 | 后果 | 改正 |
|---|---|---|---|
| 1 | 把 diff[R + 1] -= K 写成 diff[R] -= K |
第 \(R\) 项被提前取消 | 结束位置是 \(R+1\) |
| 2 | 差分数组没有多开一位 | \(R=n\) 时访问越界 | 使用 n + 2 |
| 3 | 修改端点后直接输出 diff[i] |
输出变化量而不是最终值 | 最后求前缀和 |
| 4 | 把翻转当成普通加法 | 翻转两次无法正确抵消 | 使用异或记录奇偶 |
| 5 | 固定长度翻转中，剩余长度不足 \(m\) 仍然翻转 | 区间越界 | 输出 -1 |
| 6 | 大量累计值使用 int |
可能溢出 | 使用 long long |
重点记忆：普通数值修改使用加减差分；状态翻转使用异或差分；差分记录的是变化，不是最终数组。
五、方法、套路与策略小结
1. 区间修改经典问题
- 先构造差分数组；
- 左端点加上修改量；
- 右端点后一位减去修改量；
- 所有操作完成后求一次前缀和。
2. 序列增减问题
- 把“所有数相同”转化为“相邻差分全部为 \(0\)”；
- 统计正差额总量和负差额总量；
- 最少操作数为两者最大值；
- 最终结果种数为两者差的绝对值加 \(1\)。
3. 定长区间修改问题
- 先求出初始状态和目标状态的差异；
- 普通加减用数值差分；
- 状态翻转用异或差分；
- 固定长度区间从当前位置开始时，结束标记在
i + m； - 从左到右处理，当前位置的选择通常是被强制确定的。