 一条？)
LeetCode 1109「航班预订统计」，场景真实得不像算法题：
你收到2万条预订记录，每条都是“从第a天到第b天，每天加c个座位”。
要你算出每一天的总座位数。
大多数人第一反应：
forfirst, last, seatsinbookings:
fordayinrange(first, last+1):
ans[day] += seats
「然后 TLE（超时）了。」
2万条记录 × 平均1万天 = 2亿次加法，不超时才怪。
「但差分数组告诉你：每条区间更新，只需要改两个数。」
📦 题目速览（30 秒读懂）
有
n个航班（编号 1~n），给你m条预订记录[first, last, seats]，表示从first到last的每个航班都增加seats个座位。
返回每个航班最终的座位总数。
「示例：」
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5 输出：[10, 55, 45, 25, 25]「约束：」n和m都 ≤ 2×10⁴，暴力O(n*m)必挂。
🧠 核心思路：区间更新 = 开头 + 关水龙头，最后前缀和还原
暴力到底慢在哪里？
每条记录要遍历它覆盖的所有航班，区间越长越慢。而且多条记录之间相互独立，无法复用中间结果。
优化的数学本质——差分数组
区间[first, last]统一加seats，等价于：
在 first处“开始加” →diff[first] += seats在 last+1处“停止加” →diff[last+1] -= seats
这就像一排水龙头：
你在位置1打开阀门（流量 +10） 在位置3关掉阀门（流量 -10） 那么位置1~2都流了10，位置3及以后不流
「最后对整个diff做一次前缀和」，就能还原出每个位置的最终值。
「每条记录O(1)，总共O(m)，还原O(n)，总复杂度O(m+n)。」
🖼️ 图解全过程（一眼就懂）
以bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5为例：
「Step 1：差分数组初始全0」
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| diff | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
「Step 2：处理每条记录（只改两个位置）」
| 预订 | 操作 | diff 变化 |
|---|---|---|
| [1,2,10] | diff[1]+=10, diff[3]-=10 | [0,10,0,-10,0,0,0] |
| [2,3,20] | diff[2]+=20, diff[4]-=20 | [0,10,20,-10,-20,0,0] |
| [2,5,25] | diff[2]+=25, diff[6]-=25 | [0,10,45,-10,-20,0,-25] |
「Step 3：前缀和还原（从左到右累加）」
| 航班 i | 累加过程 | 结果 |
|---|---|---|
| 1 | total = 0 + 10 | 「10」 |
| 2 | total = 10 + 45 | 「55」 |
| 3 | total = 55 + (-10) | 「45」 |
| 4 | total = 45 + (-20) | 「25」 |
| 5 | total = 25 + 0 | 「25」 |
最终：[10, 55, 45, 25, 25]✅
看到了吗？「无论区间多长，每条记录只动了两个数。」
💻 代码实现（Python + Java，附防坑版）
Python 版
classSolution:
defcorpFlightBookings(self, bookings: List[List[int]], n: int)-> List[int]:
# 多开 2 个位置，防止 last+1 越界
diff = [0] * (n +2)
forfirst, last, seatsinbookings:
diff[first] += seats
diff[last +1] -= seats
# 前缀和还原
ans = [0] * n
total =0
foriinrange(1, n +1):
total += diff[i]
ans[i -1] = total
returnans
Java 版
classSolution{
publicint[] corpFlightBookings(int[][] bookings,intn) {
int[] diff =newint[n +2];// 多开 2 位防越界
for(int[] b : bookings) {
diff[b[0]] += b[2];
diff[b[1] +1] -= b[2];
}
int[] ans =newint[n];
inttotal =0;
for(inti =1; i <= n; i++) {
total += diff[i];
ans[i -1] = total;
}
returnans;
}
}
⚠️「致命坑（必看）」：
diff长度必须是n + 2，因为当last = n时，diff[n+1]会被访问。少开一位会数组越界。还原时循环从1到n，对应航班编号，而ans下标是0到n-1。
⏱️ 复杂度分析（面试必问）
「处理预订」：O(m)，每条O(1) 「前缀和还原」：O(n) 「总时间」：O(m + n)，暴力是O(m × n) 「空间」：O(n)（差分数组）
当m = n = 2×10⁴时，差分数组4×10⁴次操作 vs 暴力4×10⁸次，「差距1万倍」。
🚀 举一反三：4 道高频变种题，一套框架通吃
| 题目 | 差异点 | 应对策略 |
|---|---|---|
| 「LeetCode 1094. 拼车」 | 区间上下车，判断是否超载 | 差分记录每站人数变化，还原后检查是否超过容量 |
| 「LeetCode 370. 区间加法」（会员题） | 纯差分模板 | 直接套模板，改两个位置 + 前缀和 |
| 「LeetCode 1854. 人口最多的年份」 | 出生-死亡区间，找人口峰值年 | 差分记录每年人口变化，还原后找最大值 |
| 「LeetCode 798. 得分最高的最小轮调」（进阶） | 区间加分，求最大得分索引 | 差分记录每个轮调位置的变化量 |
💬 面试追问模拟（提前准备，惊艳全场）
「Q1：差分数组和前缀和到底是什么关系？」
它们互为逆运算。
原数组 → 差分数组（相邻差）： diff[i] = nums[i] - nums[i-1]差分数组 → 原数组（前缀和）： nums[i] = nums[i-1] + diff[i]前缀和擅长“频繁区间查询”，差分数组擅长“频繁区间更新”，它们是同一枚硬币的两面。
「Q2：如果既有区间更新，又有区间查询，差分数组还够用吗？」
不够。差分数组只支持“最后统一查询”，如果更新和查询交替频繁，需要「树状数组（Fenwick Tree）「或」线段树」，它们支持 O(log n) 的区间更新 + 区间查询。
「Q3：差分数组能处理二维区间更新吗？（比如子矩阵全部 +v）」
可以。二维差分用容斥原理：
diff[x1][y1] += v，diff[x2+1][y1] -= v，diff[x1][y2+1] -= v，diff[x2+1][y2+1] += v
最后对每一行做前缀和，再对每一列做前缀和还原。
🧩 实战小技巧（刷题党必备）
「口诀」：区间更新，左加右减；前缀还原，一路累加。 「模板」：凡是“给区间加同一个值，最后求每个位置的值”，直接用差分数组。 「空间优化」：如果不需要保留原始差分数组，可以直接在答案数组上做差分（原地操作），节省O(n)空间。
📈 实际应用场景（不止是刷题）
「酒店/航班预订系统」：批量统计各日期的房间/座位预订量 「会议室调度」：统计各时间段会议室占用数 「交通流量分析」：统计各路段在某时段内的车流量 「游戏经验值分配」：给某等级区间的玩家批量发放经验 「工资/税务计算」：某收入区间的税率批量调整
🎁 今日思考题
如果
bookings中既有“加座位”也有“退座位”（负值），差分数组需要改什么？
「提示」：完全不用改！seats可以为负数，diff[first] += seats和diff[last+1] -= seats逻辑完全通用。那如果每条记录不是“区间统一加”，而是“区间统一赋值为某个值”，差分数组还能用吗？欢迎评论区讨论 🧠
