概述

在一段数列中，若要对区间 M[i..j] 的每个元素统一加上一个固定值 k，只需：

  • 在 M[i] 处 +k
  • 在 M[j+1] 处 -k

这一操作称为差分更新，它利用前缀和自动把 +k 扩散到整个区间，而区间外的影响被“截断”。

案例

航线：杭州 → 西安 → 成都 → 兰州 → 新疆 → 拉萨 → 昆明（共 6 段）

航段编号：
①杭州-西安　②西安-成都　③成都-兰州　④兰州-新疆　⑤新疆-拉萨　⑥拉萨-昆明

预订单（每条表示“从起飞机场到降落机场”的占座人数）：

  • 杭州-西安　20人
  • 杭州-新疆　16人
  • 成都-兰州　25人
  • 兰州-昆明　14人

问题：飞机驶离每一段时，机上有多少乘客？

tips:default tips: 本题在确保所有乘客都准时值机且航班正常的情况

解：
差分更新

设各航段初始值为 M = [0,0,0,0,0,0,0] ，差分数组为D，其中每个下标（从0开始）对应着每个航段，航段值为 k。

tips:default （Tips：本文使用**右开区间** `[i,j)`，即包含起飞机场、不包含落地机场；差分动作为 `D[i]+=k, D[j]−=k`。）
步骤 操作说明 k 值 差分动作 结果 D 数组
1 杭州-西安 20 D[0] += 20D[1] -= 20 [20, -20, 0, 0, 0, 0, 0]
2 杭州-新疆 16 D[0] += 16D[4] -= 16 [36, -20, 0, 0, -16, 0, 0]
3 成都-兰州 25 D[2] += 25D[3] -= 25 [36, -20, 25, -25, -16, 0, 0]
4 兰州-昆明 14 D[3] += 14D[6] -= 14 [36, -20, 25, -11, -16, 0, -14]

前缀和还原

设各航段的实际人数为 A[ i ] , 通过上面的差分数组D还原成最终实际人数的数据：

tips:default 前缀和还原动作为： A[0] = D[0] A[i] = A[i-1] + D[i] (i ≥ 1)
步骤 累加式 结果 说明
A[0] = D[0] 36 -
A[1] = A[0] + D[1] = 36 + (-20) 16 -
A[2] = A[1] + D[2] = 16 + 25 41 -
A[3] = A[2] + D[3] = 41 + (-11) 30 -
A[4] = A[3] + D[4] = 30 + (-16) 14 -
A[5] = A[4] + D[5] = 14 + 0 14 -
A[6] = A[5] + D[6] = 14 + (-14) 0 因为只有6个航段，这个可丢弃 
机场  0   1   2   3   4   5   6
      ↓   ↓   ↓   ↓   ↓   ↓
航段 0   1   2   3   4   5
答：

前缀和还原后各段实际人数：[36, 16, 41, 30, 14, 14]

实现代码
/**
 * 差分演示：右开区间 [start, end)
 * 文章示例：杭州 → 西安 → 成都 → 兰州 → 新疆 → 拉萨 → 昆明
 */
public class FlightDiff {

    public static void main(String[] args) {
        // 建差分数组（长度 = 航段数 + 1 )
        int[] diff = new int[6 + 1];
        System.out.println("初始航段 M：" + Arrays.toString(diff));

        // 差分更新：右开区间 [start, end)
        addPassengers(diff, 0, 1, 20);      // 杭州-西安　20人
        addPassengers(diff, 0, 4, 16);      // 杭州-新疆　16人
        addPassengers(diff, 2, 3, 25);      // 成都-兰州　25人
        addPassengers(diff, 3, 6, 14);      // 兰州-昆明　14人
        System.out.println("差分数组 D：" + Arrays.toString(diff));

        // 前缀和还原：临时快照
        int[] actual = restorePassengers(diff);
        System.out.println("实际人数 A：" + Arrays.toString(actual));
    }

    /**
     * 差分更新：右开区间 [start,end)
     * 只修改两个点，实现时间复杂度 O(1)
     */
    private static void addPassengers(int[] diff, int start, int end, int k) {
        diff[start] += k;
        // 右开：到 end 前结束
        diff[end] -= k;
    }

    /**
     * 前缀和还原：O(n)
     * actual[0] = diff[0]
     * actual[i] = diff[i-1] + diff[i]  (i>0)
     */
    private static int[] restorePassengers(int[] diff) {
        int[] actual = new int[diff.length - 1]; // 只保留航段数
        actual[0] = diff[0];
        for (int i = 1; i < actual.length; i++) {
            actual[i] = actual[i - 1] + diff[i];
        }
        return actual;
    }
}

输出结果：
初始航段 M：[0, 0, 0, 0, 0, 0, 0]
差分数组 D：[36, -20, 25, -11, -16, 0, -14]
实际人数 A：[36, 16, 41, 30, 14, 14]