假设有一个长度为10000的数组，需要对区间[100, 5000]内的每个元素都加3，然后再对区间[200, 8000]内的每个元素减5，最后还要对区间[1000, 9000]内的每个元素加10。这样的操作要重复进行1000次，最后输出最终结果。
最直观的做法是每次区间操作都遍历一遍，时间复杂度是$O(n \times q)$，其中$n$是数组长度，$q$是操作次数。当$n$和$q$都达到$10^5$甚至更大时，这种做法会直接超时。
差分数组正是为这类场景而生的——它能把每次区间操作的时间复杂度降到$O(1)$，最终还原答案时再花$O(n)$时间，总复杂度变成$O(n + q)$。
前缀和与差分数组的互逆关系
理解差分数组，首先要理解它与前缀和的关系。前缀和数组prefix的定义是：
前缀和的核心价值在于：能在$O(1)$时间内回答任意区间的求和查询。区间$[l, r]$的和等于$prefix[r] - prefix[l-1]$。
差分数组则是前缀和的逆运算。给定原数组nums，其差分数组diff定义为：
$$diff[i] = nums[i] - nums[i-1] \quad (i > 0)$$
也就是说，差分数组的每个元素记录的是原数组相邻元素的差值。
图片来源: labuladong.online
从差分数组还原原数组，只需要做一次"前缀和"操作：
$$nums[0] = diff[0]$$$$nums[i] = nums[i-1] + diff[i] \quad (i > 0)$$
这个过程和构建前缀和数组完全一致。差分数组就是前缀和的逆，前缀和也是差分数组的逆。
区间修改的核心思想
差分数组的威力在于处理区间修改。假设要将原数组nums的区间$[l, r]$内所有元素都加上val。
直接操作原数组需要遍历$[l, r]$的每个元素，时间复杂度$O(r-l+1)$。但如果操作差分数组，只需要两步：
diff[l] += valdiff[r+1] -= val（如果$r+1$在数组范围内）
为什么这样做有效？
当还原原数组时，是从左往右累加diff的值。diff[l] += val意味着从nums[l]开始，往后的所有元素都会加上val。而diff[r+1] -= val则从nums[r+1]开始抵消这个增量。两个操作叠加，只有区间$[l, r]$内的元素被加上了val，区间外的元素不受影响。
图片来源: labuladong.online
这种"打标记、最后统一处理"的思想，把单次区间修改的代价从$O(n)$降到了$O(1)$。无论操作多少次，只需要维护差分数组，最后一次性还原即可。
差分数组工具类封装
将差分数组封装成一个工具类，可以方便地在各类题目中复用：
class Difference {
private int[] diff;
// 从初始数组构建差分数组
public Difference(int[] nums) {
diff = new int[nums.length];
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
// 对区间 [l, r] 内所有元素加上 val（val 可为负数）
public void increment(int l, int r, int val) {
diff[l] += val;
if (r + 1 < diff.length) {
diff[r + 1] -= val;
}
}
// 还原并返回原数组
public int[] result() {
int[] res = new int[diff.length];
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
}
注意increment方法中的边界检查：当$r+1$超出数组范围时，说明修改的是数组末尾，不需要再做减法操作。
LeetCode 370：区间加法的模板题
这道题是差分数组最直接的应用场景。
题目描述：给定长度为length的初始全零数组，和若干个更新操作updates，其中updates[i] = [start, end, inc]表示对区间$[start, end]$内所有元素增加inc。返回最终数组。
解题思路：这题几乎就是差分数组工具类的直接应用。初始数组全零，意味着差分数组也是全零，只需要依次执行区间修改，最后还原即可。
class Solution {
public int[] getModifiedArray(int length, int[][] updates) {
// 初始全零数组
int[] nums = new int[length];
Difference df = new Difference(nums);
for (int[] update : updates) {
int l = update[0];
int r = update[1];
int val = update[2];
df.increment(l, r, val);
}
return df.result();
}
}
class Difference {
private int[] diff;
public Difference(int[] nums) {
diff = new int[nums.length];
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
public void increment(int l, int r, int val) {
diff[l] += val;
if (r + 1 < diff.length) {
diff[r + 1] -= val;
}
}
public int[] result() {
int[] res = new int[diff.length];
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
}
复杂度分析：时间复杂度$O(n + q)$，空间复杂度$O(n)$，其中$n$是数组长度，$q$是操作次数。
LeetCode 1109：航班预订统计
这道题需要从题目描述中抽象出差分数组的模型。
题目描述：有n个航班，编号从1到n。给定预订记录bookings，其中bookings[i] = [first, last, seats]表示预订了航班first到last（包含两端）每个航班seats个座位。返回每个航班的总预订座位数。
解题思路：航班编号从1开始，而数组下标从0开始，需要做一个下标转换。预订区间$[first, last]$对应数组下标$[first-1, last-1]$。本质上就是对数组多次区间修改，最后输出结果。
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] nums = new int[n];
Difference df = new Difference(nums);
for (int[] booking : bookings) {
// 航班编号从1开始，转为数组下标需要减1
int l = booking[0] - 1;
int r = booking[1] - 1;
int val = booking[2];
df.increment(l, r, val);
}
return df.result();
}
}
易错点：航班编号和数组下标的对应关系。题目明确说航班编号从1开始，而区间包含两端，转换为数组下标时需要同时减1。
LeetCode 1094：拼车问题
这道题的难点在于理解题意并抽象出差分数组模型。
题目描述：一辆车向东行驶，给定trips数组，其中trips[i] = [numPassengers, from, to]表示在某位置from上车numPassengers人，在位置to下车。判断是否能在不超过capacity的情况下完成所有行程。
解题思路：每个trip本质上是一个区间操作——乘客在$[from, to-1]$区间内占用座位。为什么是$to-1$？因为题目说乘客在to位置下车，意味着在到达to时乘客已经离开，不再占用座位。
class Solution {
public boolean carPooling(int[][] trips, int capacity) {
// 题目给出位置范围是 [0, 1000]
int[] nums = new int[1001];
Difference df = new Difference(nums);
for (int[] trip : trips) {
int val = trip[0];
int l = trip[1];
// 乘客在 to 位置下车，所以占用区间是 [from, to-1]
int r = trip[2] - 1;
df.increment(l, r, val);
}
int[] res = df.result();
for (int num : res) {
if (num > capacity) {
return false;
}
}
return true;
}
}
关键点：理解乘客在to位置下车意味着什么。乘客在到达to时已经离开，所以实际占用区间是$[from, to-1]$。
LeetCode 1526：形成目标数组的最小操作次数
这道题展示了差分数组思想的另一种应用。
题目描述：给定目标数组target，初始有一个长度相同的全零数组。每次操作可以选择任意子数组，将子数组内所有元素加1。求最少需要多少次操作才能得到target数组。
解题思路：关键观察是——操作次数等于差分数组中所有正数元素的和。
为什么？考虑差分数组diff，其中diff[i] = target[i] - target[i-1]。如果diff[i] > 0，说明target[i]比target[i-1]大，这个增量必须通过一个从位置i开始的操作来产生。如果diff[i] < 0，说明target[i]比target[i-1]小，这可以通过在某个位置结束操作来实现。
实际上，每次操作可以理解为：选择一个起始位置和一个结束位置，对差分数组的起始位置加1，结束位置的后一个位置减1。最优策略是让每个正的diff[i]都对应一个从i开始的新操作。
class Solution {
public int minNumberOperations(int[] target) {
// 操作次数等于差分数组中所有正数的和
int operations = target[0];
for (int i = 1; i < target.length; i++) {
if (target[i] > target[i - 1]) {
operations += target[i] - target[i - 1];
}
}
return operations;
}
}
原理证明：设diff[i] = target[i] - target[i-1]（定义target[-1] = 0）。对于diff[i] > 0的情况，需要至少diff[i]次操作从位置i开始。所有正的diff[i]之和就是最少操作次数。
LeetCode 1589：最大排列和
这道题结合了差分数组和贪心策略。
题目描述：给定数组nums和查询数组requests，其中requests[i] = [start, end]表示查询区间$[start, end]$内所有元素的和。可以任意重排nums，求所有查询结果之和的最大值。
解题思路：要让总和最大，应该让数值大的元素出现在被查询次数多的位置。所以关键是统计每个位置被查询了多少次。
用差分数组统计每个位置的查询次数，然后对查询次数数组和原数组都排序，让大数和大次数配对。
class Solution {
public int maxSumRangeQuery(int[] nums, int[][] requests) {
int n = nums.length;
int MOD = 1_000_000_007;
// 用差分数组统计每个位置的查询次数
int[] diff = new int[n + 1];
for (int[] req : requests) {
diff[req[0]]++;
diff[req[1] + 1]--;
}
// 还原查询次数数组
int[] count = new int[n];
count[0] = diff[0];
for (int i = 1; i < n; i++) {
count[i] = count[i - 1] + diff[i];
}
// 排序：让大数和大次数配对
Arrays.sort(count);
Arrays.sort(nums);
long sum = 0;
for (int i = 0; i < n; i++) {
sum = (sum + (long) count[i] * nums[i]) % MOD;
}
return (int) sum;
}
}
关键点：题目要求结果对$10^9 + 7$取模，注意在计算过程中用long防止溢出。
LeetCode 2381：字母移位II
这道题将差分数组应用到字符串处理中。
题目描述：给定字符串s和移位操作数组shifts，其中shifts[i] = [start, end, direction]。direction = 1表示区间$[start, end]$内每个字母向前移一位（a→b，z→a），direction = 0表示向后移一位（b→a，a→z）。返回最终字符串。
解题思路：字母移位是循环的，本质上是模26的加减法。先用差分数组统计每个位置的净移位次数，然后对每个字符应用移位。
class Solution {
public String shiftingLetters(String s, int[][] shifts) {
int n = s.length();
int[] diff = new int[n + 1];
// 用差分数组记录每个位置的移位量
for (int[] shift : shifts) {
int start = shift[0];
int end = shift[1];
int direction = shift[2] == 1 ? 1 : -1;
diff[start] += direction;
diff[end + 1] -= direction;
}
// 还原移位次数数组
int[] shiftCount = new int[n];
shiftCount[0] = diff[0];
for (int i = 1; i < n; i++) {
shiftCount[i] = shiftCount[i - 1] + diff[i];
}
// 应用移位
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
// 计算移位后的字符，注意处理负数
int shifted = (c - 'a' + shiftCount[i] % 26 + 26) % 26;
sb.append((char) ('a' + shifted));
}
return sb.toString();
}
}
易错点：移位次数可能很大也可能为负，需要正确处理模运算。(x % 26 + 26) % 26这个技巧可以保证结果在$[0, 25]$范围内。
LeetCode 3355：零数组转换I
这道题是差分数组的判定问题。
题目描述：给定数组nums和查询数组queries，每次查询可以选择区间$[l, r]$内的任意下标子集，将选中的元素减1。判断是否能将所有元素变成0。
解题思路：每个查询$[l, r]$最多能让区间内每个元素减1（可以选择全部减1）。所以问题是：每个位置i被多少个查询覆盖，以及这个覆盖次数是否至少等于nums[i]。
用差分数组统计每个位置被覆盖的次数，然后判断是否每个位置都有足够的减量机会。
class Solution {
public boolean isZeroArray(int[] nums, int[][] queries) {
int n = nums.length;
int[] diff = new int[n + 1];
// 统计每个位置被覆盖的次数
for (int[] query : queries) {
diff[query[0]]++;
diff[query[1] + 1]--;
}
// 判断每个位置是否有足够的减量机会
int prefix = 0;
for (int i = 0; i < n; i++) {
prefix += diff[i];
if (nums[i] > prefix) {
return false;
}
}
return true;
}
}
关键理解：题目允许每次查询选择子集减1，所以只要覆盖次数足够，就一定可以精确减到0。
差分数组的局限性与扩展
差分数组虽然强大，但也有明显的局限性：
空间开销：差分数组需要和原数组相同大小的额外空间。当区间范围达到$10^9$时，直接开数组会爆内存。这种情况下需要使用离散化或树状数组/线段树等数据结构。
查询延迟：差分数组的优势在于批量修改、最后统一查询。如果需要边修改边查询，或者修改和查询交替进行，差分数组就不再适用。这时候需要线段树，它支持区间修改和区间查询都是$O(\log n)$。
单点修改效率低：如果只需要单点修改，直接操作原数组即可，用差分数组反而增加复杂度。
总结
差分数组是处理区间修改问题的高效工具。其核心思想是：
- 构建：$diff[i] = nums[i] - nums[i-1]$
- 区间修改：$diff[l] += val$，$diff[r+1] -= val$
- 还原：对差分数组求前缀和
时间复杂度从暴力法的$O(n \times q)$优化到$O(n + q)$，在处理大量区间修改操作时效果显著。
识别差分数组问题的关键特征：
- 多次区间修改操作
- 最后只需要输出最终结果
- 区间范围可以用数组下标表示
掌握差分数组，配合前缀和技巧，可以解决一大类数组区间问题。
参考资料
- Difference Array Technique - Labuladong Algo Notes
- Prefix sum array and difference array - PEG Wiki
- An Introduction To Difference Arrays - Codeforces
- LeetCode 370. Range Addition
- LeetCode 1109. Corporate Flight Bookings
- LeetCode 1094. Car Pooling
- LeetCode 1526. Minimum Number of Increments on Subarrays to Form a Target Array
- LeetCode 1589. Maximum Sum Obtained of Any Permutation
- LeetCode 2381. Shifting Letters II
- LeetCode 3355. Zero Array Transformation I