1109. 航班预订统计（Corporate Flight Bookings）

频次 ★★★ · 难度 🟡 · 高频：美团

题目

[first, last, seats] 表示预定的区间，返回每个航班的预定总数。

思路

差分数组：diff[first] += seats; diff[last+1] -= seats，前缀和恢复。

代码

public int[] corpFlightBookings(int[][] bookings, int n) {
    int[] diff = new int[n + 2];
    for (int[] b : bookings) {
        diff[b[0]] += b[2];
        diff[b[1] + 1] -= b[2];
    }
    int[] res = new int[n];
    int cur = 0;
    for (int i = 0; i < n; i++) {
        cur += diff[i + 1];
        res[i] = cur;
    }
    return res;
}

复杂度

• 时间：O(n)
• 空间：O(n)

边界条件

• 航班号 1-indexed：bookings 里的 first/last 从 1 开始，所以 diff 开 n+2——要放得下 diff[n+1]（当 last == n 时的右端点减法）
• 区间是闭的：[first, last] 两端都算，所以是 diff[last+1] -= seats。与 1094. 拼车 的左闭右开正好相反
• first == last：单个航班，加了又在下一位减掉，只影响一个位置
• 空 bookings：返回全 0 数组

变式

• 1094. 拼车：同样的差分，但区间左闭右开，且只需判是否越限而不必输出全部
• 区间加等差数列：做两次差分（差分的差分），还原时做两次前缀和
• 二维区间加：二维差分，diff[r1][c1] += v; diff[r1][c2+1] -= v; diff[r2+1][c1] -= v; diff[r2+1][c2+1] += v，还原时求二维前缀和
• 边改边查：差分失效（每次查询都要 O(n) 还原），改用树状数组

易错点

• diff 必须开 n+2 而不是 n+1。last 最大取 n，diff[last+1] 就是 diff[n+1]，开 n+1 会数组越界。这是本题最高频的错
• 1-indexed 和 0-indexed 混用：diff 按航班号 1..n 存，而 res 是 0..n-1，所以还原时是 cur += diff[i+1]。把这两个下标空间混起来，结果会整体偏移一位
• 别在还原前就去读 diff[i] 当答案——差分数组存的是增量，不是值

面试追问

• 差分数组的本质是什么：它是原数组的「导数」。diff[i] = a[i] - a[i-1]，前缀和是它的「积分」。区间加一个常数，反映在导数上就只有两个端点变了——这就是 O(1) 完成区间修改的全部原理。
• 为什么右端点是 last+1 而不是 last：diff[i] 影响的是「从 i 开始往后的所有位置」。要让影响止于 last，就得在 last+1 处抵消。减法的位置永远是「区间结束的下一格」，闭区间就是 last+1，左闭右开区间就是 to。
• 差分适合什么场景、不适合什么：适合「离线批量区间修改、最后一次性读全量」。不适合边改边查——每次查都要 O(n) 还原。后者要上树状数组（单点加/区间查）或线段树（区间加/区间查，带懒标记）。
• 这题和 MySQL 的批量更新有可比性吗：思路上有。都是把「N 次小修改」攒成「一次大计算」，用一次全量扫描摊薄每次修改的成本——和摊还分析里「批处理摊薄固定开销」是同一个道理。

关联题

• 同套路：1094. 拼车