LeetCode 1109.航班预订统计（差分）

题目

• 1109. 航班预订统计

解题思路：差分

典型的【差分】模板题，只涉及【区间修改 + 单点查询】。

对于数组 [1,2,2,4]，其差分数组为 [1,1,0,2]，差分数组的第 i 个数即为原数组的第 i-1 个元素和第 i 个元素的差值，也就是说对差分数组求前缀和即可得到原数组。

当希望对原数组的某一个区间 [l,r] 施加一个增量$\text{inc}$ 时，差分数组D对应的改变是：D[l] 增加 $\text{inc}$，D[r+1] 减少 $\text{inc}$。

• D[l] += inc：由于差分是前缀和的逆向过程，这个操作对于将来的查询而言，带来的影响是对于所有的下标大于等于l的位置都增加了值 inc
• D[r+1] -= inc ：由于期望只对[l,r]产生影响，因此需要对下标大于r的位置进行减值操作，从而抵消“影响”

算法流程：

• 遍历给定的预定记录数组，每次以$O(1)$复杂度完成对差分数组的修改即可
• 完成差分数组的修改后，只需要求出差分数组的前缀和即可得到目标数组

class Solution {public int[] corpFlightBookings(int[][] bookings, int n) {int[] nums = new int[n + 1];for (int[] bs : bookings) {// 本题中日期从 1 开始，因此需要相应的调整数组下标对应关系int l = bs[0] - 1, r = bs[1] - 1, inc = bs[2];nums[l] += inc;nums[r + 1] -= inc;}int[] ans = new int[n];ans[0] = nums[0];for (int i = 1; i < n; i++) {ans[i] = ans[i - 1] + nums[i];}return ans;}
}

空间复杂度优化：

class Solution {public int[] corpFlightBookings(int[][] bookings, int n) {int[] nums = new int[n];for (int[] bs : bookings) {// 本题中日期从 1 开始，因此需要相应的调整数组下标对应关系int l = bs[0] - 1, r = bs[1] - 1, inc = bs[2];nums[l] += inc;// 当 r 为 n 时，无需修改 d[r]，因为这个位置溢出了下标范围// 如果求前缀和时考虑该位置，那么该位置对应的前缀和值必定为 0if (bs[1] < n) {nums[r + 1] -= inc;}            }// 求原数组a[]的时候在,推导式子 a[i] = a[i−1] + D[i] 时// 把已经使用过的较小的D[]直接当成a[]即可for (int i = 1; i < n; i++) {nums[i] += nums[i - 1];}return nums;}
}

• 时间复杂度：$O(n+m)$，其中 $n$ 为要求的数组长度，$m$ 为预定记录的数量。需要对于每一条预定记录处理一次差分数组，并最后对差分数组求前缀和。

• 空间复杂度：$O(1)$。只需要常数的空间保存若干变量，注意返回值不计入空间复杂度

再总结一下（加粗字体为最佳方案）：

• 数组不变，区间查询：前缀和、树状数组、线段树；
• 数组单点修改，区间查询：树状数组、线段树；
• 数组区间修改，单点查询：差分、线段树；
• 数组区间修改，区间查询：线段树。

注意：上述总结是对于一般性而言的（能直接解决的），对标的是模板问题。但存在经过一些经过“额外”操作，对问题进行转化，从而使用别的解决方案求解的情况。

例如某些问题，可以先对原数组进行差分，然后使用树状数组，也能解决区间修改问题。

或者使用多个树状数组来维护多个指标，从而实现类似线段树的持久化标记操作。

Reference

• 航班预订统计

• 【区间求和问题】差分入门模板题

• 差分-算法竞赛专题解析