航班预订统计（区间批量加）为什么用差分数组？

简化版

有 n 个航班,若干条预订记录 [first, last, seats] 表示「第 first 到 last 号航班每个都加 seats 个座位」,求每个航班最终的订座数。这是差分数组的模板应用:每条预订就是一次「区间加」,用差分 diff[first-1] += seats、diff[last] -= seats O(1) 处理,所有预订记完后前缀和还原即得答案。总 O(记录数 + n),远优于「每条预订遍历区间」的 O(记录数 × n)。

详细版

int[] corpFlightBookings(int[][] bookings, int n) {
    int[] diff = new int[n + 1];             // 多一位防 last 越界
    for (int[] b : bookings) {
        int first = b[0], last = b[1], seats = b[2];
        diff[first - 1] += seats;            // 航班号从 1 开始，转成下标 first-1
        diff[last] -= seats;                 // last 号(下标 last-1)之后抵消 → diff[last]
    }
    int[] res = new int[n];
    res[0] = diff[0];
    for (int i = 1; i < n; i++)
        res[i] = res[i - 1] + diff[i];       // 前缀和还原
    return res;
}

航班号 1-indexed → 下标 0-indexed:[first, last] 对应下标 [first-1, last-1]。
差分区间加:diff[first-1] += seats、diff[(last-1)+1] -= seats(即 diff[last] -= seats)。
前缀和还原得到每个航班的总订座。

完整版教学

一、识别这是差分题

题目特征非常典型:「多条区间更新(每条给一段连续航班加座位)+ 最后统一查询(每个航班的总数)」。这正是差分数组的适用模式——更新在前、查询在后、且都是区间批量加。看到「若干个 [左, 右, 值] 表示区间加,求最终每个位置的值」,就应该立刻想到差分。

二、朴素做法为什么慢

朴素做法:对每条预订 [first, last, seats],遍历 first 到 last,每个航班都 += seats。如果有 m 条预订、每条覆盖的航班平均长度接近 n,总复杂度 O(m·n)。当 m 和 n 都很大(比如各 1e4~1e5),O(m·n) 会超时。差分把每条预订的处理从 O(区间长度) 降到 O(1),这是本题优化的关键。

三、差分的两步处理

用差分数组,每条预订只做两个 O(1) 操作:

diff[first-1] += seats:从 first 号航班开始加 seats。
diff[last] -= seats:到 last 号之后抵消(下标 last-1 是最后一个要加的,last-1+1 = last 处减掉)。

所有预订都这样记完(共 O(m)),差分数组就「编码」了所有区间加操作。最后一次前缀和还原(O(n)),把差分变回真实的每个航班订座数。总 O(m + n)。

四、下标转换的坑(重点)

本题航班号是 1-indexed(从 1 开始),而数组下标是 0-indexed,转换时最容易错:

航班号 [first, last] 对应数组下标 [first-1, last-1]。
差分区间加公式 diff[l] += v; diff[r+1] -= v,代入 l = first-1、r = last-1:
- diff[first-1] += seats
- diff[(last-1)+1] -= seats → diff[last] -= seats
差分数组要开 n+1 长度,因为 diff[last] 在 last == n 时会用到下标 n。

把「航班号」和「数组下标」的偏移理清楚,是本题不出错的关键。

五、同类应用

差分「区间批量加」的模式,还出现在很多题里:

拼车(LeetCode 1094):每个行程 [乘客数, 上车点, 下车点) 是区间 [start, end) 加乘客,差分后检查是否有位置超过车容量。注意下车点是开区间(下车即离开),所以是 diff[end] -= num 而不是 end+1。
区间加法、统计每个时间点的在线/在场人数、会议室重叠等。
只要是「大量 [左,右,值] 区间加,最后看每个位置」,都是差分。

六、复杂度与要点

时间 O(m + n):m 条记录各 O(1) + 一次 O(n) 还原。
空间 O(n):差分数组。
要点:识别「区间加 + 最后查询」→ 用差分;每条区间加两个端点 O(1);注意 1-indexed 到 0-indexed 的下标转换和开/闭区间(下车点是开区间);差分数组多开一位防越界。

七、从公式证明到手算闭环

这道题成立的核心是：每条预订在 first 航班开启 seats 增量，在 last+1 关闭，最终前缀值就是每个航班总座位数。先明确每个数组槽或哈希键的数学含义，代码中的下标偏移才不是死记硬背。

for [first,last,seats]:
  diff[first-1] += seats
  if last < n: diff[last] -= seats
answer[i] = answer[i-1] + diff[i]

带数字推演：n=5，预订 [1,2,10] 与 [2,5,20] 生成差分 [10,20,-10,0,0]，结果 [10,30,20,20,20]。手算时同时列出原数组、辅助状态和本轮新增答案，能够直接发现端点偏一、初始化遗漏以及更新顺序错误。

核对维度	本题结论
正确性依据	每条预订在 first 航班开启 seats 增量，在 last+1 关闭，最终前缀值就是每个航班总座位数
复杂度	处理 b 条预订 O(b)，还原 n 个航班 O(n)，总 O(b+n)
关键边界	题目航班编号从 1 开始而数组从 0 开始；last=n 时不存在关闭位置；座位累计可能需 64 位

记忆钩子：不要先背代码，先说清辅助状态“代表哪一段”；公式只是把重叠部分消掉或把边界影响传播出去。

八、实现边界与测试策略

实现时最需要警惕的是：题目航班编号从 1 开始而数组从 0 开始；last=n 时不存在关闭位置；座位累计可能需 64 位。这不是语法细节，而是决定算法是否仍满足题目语义的前提。

提交前应分别验证：

空数组或最小合法规模，确认哨兵位置和初始化。
查询或更新紧贴左、上边界，确认没有访问负下标。
查询或更新紧贴右、下边界，确认“终点后一位”不会越界。
包含 0、负数或重复前缀的样例，确认频次与取模语义。
大数输入，确认累计和、乘积或答案数量的整数类型足够。

如果需求从离线变成在线，或从单次恢复变成更新查询交错，原方法可能不再合适。此时应根据操作类型改用树状数组、线段树、二维结构或其他能维护动态状态的数据结构，而不是强行沿用静态前缀模型。

九、常见误区与追问

误区：每条预订应循环更新所有航班。 差分只写两个边界，避免区间长度成本。
误区：last 应直接作为数组右端下标。 first-1 是起点，而关闭点正是 0-based 的 last。
误区：last=n 时也要写 diff[n]。 若数组只开 n 个位置会越界，可判界或开 n+1。
追问：为什么答案要再前缀累加？ 差分保存的是变化量，不是每架航班最终座位。
追问：如果要随时查询某航班怎么办？ 离线题用差分；在线更新查询可用树状数组。
追问：复杂度为什么不是 O(bn)？ 每条预订固定两次写入，只有最后统一扫描 n 次。

十、加强记忆

航班预订统计 = 差分数组模板应用:每条 [first,last,seats] 是一次区间加,用 diff[first-1]+=seats、diff[last]-=seats(1-indexed 转 0-indexed)O(1) 处理,所有记录完成后前缀和还原,总 O(m+n)(朴素 O(m·n))。识别信号:「多条区间加 + 最后查每个位置」。注意下标偏移和开闭区间(拼车下车点是开区间用 diff[end]-=)。差分数组多开一位防越界。

简化版

详细版