差分数组（Difference Array）是一种高效处理区间更新的技巧。当需要对数组的某个区间 [l, r] 内的所有元素同时加上一个值 v 时，暴力方法需要 O(r-l+1) 时间，而差分数组只需 O(1) 时间。本文用Java实现差分数组，讲解其原理、区间更新操作与前缀和还原，并结合实际例题展示应用场景。
核心原理
差分数组 diff 与原数组 arr 的关系：
diff[0] = arr[0]
diff[i] = arr[i] - arr[i-1] (i > 0)
反过来，原数组可以通过前缀和还原：
arr[i] = diff[0] + diff[1] + ... + diff[i]
关键性质：对原数组区间 [l, r] 每个元素加 v，等价于：
– diff[l] += v
– diff[r+1] -= v（如果 r+1 在范围内）
这样单次区间更新仅需两次单点修改，复杂度为 O(1)。
为什么差分数组有效
原数组: [3, 3, 3, 3, 3, 3]
差分数组: [3, 0, 0, 0, 0, 0]
对[1,3]加2:
diff[1] += 2 → [3, 2, 0, 0, 0, 0]
diff[4] -= 2 → [3, 2, 0, 0, -2, 0]
前缀和还原: [3, 5, 5, 5, 3, 3]
↑ ↑ ↑
只有这三个位置增加了2
Java完整实现
import java.util.Arrays;
/**
* 差分数组（Difference Array）
* 高效处理区间更新，单次更新O(1)，最终还原O(n)
*/
public class DifferenceArray {
private long[] diff; // 差分数组
private int n; // 数组长度
/**
* 从原数组构建差分数组
*/
public DifferenceArray(int[] arr) {
this.n = arr.length;
this.diff = new long[n];
diff[0] = arr[0];
for (int i = 1; i < n; i++) {
diff[i] = arr[i] - arr[i - 1];
}
}
/**
* 区间更新：对[l, r]区间内每个元素加上value
* 时间复杂度: O(1)
*/
public void rangeAdd(int l, int r, long value) {
if (l < 0 || r >= n || l > r) {
throw new IllegalArgumentException("无效的区间范围");
}
diff[l] += value;
if (r + 1 < n) {
diff[r + 1] -= value;
}
}
/**
* 单点更新：对位置idx加上value
* 等价于 rangeAdd(idx, idx, value)
*/
public void pointAdd(int idx, long value) {
rangeAdd(idx, idx, value);
}
/**
* 前缀和还原：从差分数组还原出最终数组
* 时间复杂度: O(n)
*/
public long[] reconstruct() {
long[] result = new long[n];
result[0] = diff[0];
for (int i = 1; i < n; i++) {
result[i] = result[i - 1] + diff[i];
}
return result;
}
/**
* 获取某个位置的当前值（不还原整个数组）
* 时间复杂度: O(n)，若频繁查询建议先还原
*/
public long getValue(int idx) {
long sum = 0;
for (int i = 0; i <= idx; i++) {
sum += diff[i];
}
return sum;
}
/**
* 打印差分数组（调试用）
*/
public void printDiff() {
System.out.println("差分数组: " + Arrays.toString(diff));
}
/**
* ========== 二维差分数组 ==========
* 用于矩阵的矩形区域更新
*/
public static class Diff2D {
private long[][] diff;
private int rows, cols;
public Diff2D(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.diff = new long[rows + 2][cols + 2]; // 多开一圈避免越界判断
}
/**
* 矩形区域更新：对[x1,y1]到[x2,y2]的矩形区域每个元素加value
* 时间复杂度: O(1)
*/
public void rangeAdd(int x1, int y1, int x2, int y2, long value) {
diff[x1][y1] += value;
diff[x2 + 1][y1] -= value;
diff[x1][y2 + 1] -= value;
diff[x2 + 1][y2 + 1] += value;
}
/**
* 还原二维数组
*/
public long[][] reconstruct() {
long[][] result = new long[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
long val = diff[i][j];
if (i > 0) val += result[i - 1][j];
if (j > 0) val += result[i][j - 1];
if (i > 0 && j > 0) val -= result[i - 1][j - 1];
result[i][j] = val;
}
}
return result;
}
}
public static void main(String[] args) {
// ========== 一维差分数组演示 ==========
System.out.println("=== 一维差分数组演示 ===");
int[] arr = {0, 0, 0, 0, 0, 0, 0, 0};
DifferenceArray da = new DifferenceArray(arr);
da.printDiff();
// 执行多次区间更新
da.rangeAdd(1, 3, 5); // [0, 5, 5, 5, 0, 0, 0, 0]
da.rangeAdd(2, 5, 3); // [0, 5, 8, 8, 3, 3, 0, 0]
da.rangeAdd(0, 7, 1); // [1, 6, 9, 9, 4, 4, 1, 1]
da.rangeAdd(4, 4, 10); // [1, 6, 9, 9, 14, 4, 1, 1]
da.printDiff();
long[] result = da.reconstruct();
System.out.println("还原结果: " + Arrays.toString(result));
// 验证
System.out.println("验证:");
System.out.println(" 位置0: 0+1=1 ✓");
System.out.println(" 位置1: 0+5+1=6 ✓");
System.out.println(" 位置2: 0+5+3+1=9 ✓");
System.out.println(" 位置4: 0+3+1+10=14 ✓");
// ========== 二维差分数组演示 ==========
System.out.println("\n=== 二维差分数组演示 ===");
Diff2D diff2d = new Diff2D(5, 5);
// 在(1,1)到(3,3)区域加1
diff2d.rangeAdd(1, 1, 3, 3, 1);
// 在(2,2)到(4,4)区域加2
diff2d.rangeAdd(2, 2, 4, 4, 2);
long[][] matrix = diff2d.reconstruct();
System.out.println("二维还原结果:");
for (long[] row : matrix) {
System.out.println(Arrays.toString(row));
}
// ========== 经典例题：航班预订统计 ==========
System.out.println("\n=== 例题：航班预订统计 ===");
// bookings[i] = [first, last, seats] 表示从first到last航班预订seats个座位
int[][] bookings = {{1, 2, 10}, {2, 3, 20}, {2, 5, 25}};
int nFlights = 5;
int[] answer = corpFlightBookings(bookings, nFlights);
System.out.println("航班预订: " + Arrays.deepToString(bookings));
System.out.println("每航班座位: " + Arrays.toString(answer));
// 期望: [10, 55, 45, 25, 25]
}
/**
* 经典例题：航班预订统计（LeetCode 1109）
* 使用差分数组解决
*/
public static int[] corpFlightBookings(int[][] bookings, int n) {
long[] diff = new long[n + 2];
// 所有预订转化为差分数组操作
for (int[] booking : bookings) {
int first = booking[0] - 1; // 转为0索引
int last = booking[1] - 1;
int seats = booking[2];
diff[first] += seats;
diff[last + 1] -= seats;
}
// 前缀和还原
int[] result = new int[n];
long sum = 0;
for (int i = 0; i < n; i++) {
sum += diff[i];
result[i] = (int) sum;
}
return result;
}
/**
* 进阶例题：拼车判断（LeetCode 1094）
* 判断车辆容量是否足够承载所有乘客
*/
public static boolean carPooling(int[][] trips, int capacity) {
// 最多1000个站点
long[] diff = new long[1001];
for (int[] trip : trips) {
int num = trip[0];
int from = trip[1];
int to = trip[2];
diff[from] += num;
diff[to] -= num; // 到to站点时乘客已下车
}
long current = 0;
for (long d : diff) {
current += d;
if (current > capacity) {
return false;
}
}
return true;
}
}
进阶应用：区间最值与差分约束
区间加法与单点查询
差分数组天然支持区间加法与单点查询。如果需求是”区间加、区间求和”，可以结合树状数组或线段树实现。
差分约束系统
差分数组的思想是差分约束系统的特例。对于不等式 x[i] - x[i-1] <= c，可以用最短路算法求解。差分数组则处理等式形式的约束。
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 构建差分数组 | O(n) | O(n) |
| 区间更新 | O(1) | O(1) |
| 单点查询 | O(n)（不还原）/ O(1)（还原后） | O(n) |
| 还原整个数组 | O(n) | O(n) |
对于 m 次区间更新 + 1 次最终查询：
– 暴力方法：O(m · n)
– 差分数组：O(m + n)
当 m 很大时（如 10⁵ 次更新），差分数组的优势极其明显。
适用场景总结
差分数组最适合以下场景：
- 频繁区间更新，少量最终查询：如航班预订、教室占用统计
- 二维矩形区域更新：如图像处理中的区域加值、游戏地图的范围伤害
- 作为高级数据结构的基础：如线段树懒标记的底层原理就是差分思想
- 与前缀和配合使用：差分是前缀和的逆运算，两者常组合使用
掌握差分数组后，可以将 O(n) 的区间操作优化到 O(1)，是算法竞赛和工程开发中不可或缺的技巧。
