差分数组的应用技巧

前缀和技巧 针对的算法场景是不需要对原始数组进行修改的情况下，频繁查询某个区间的累加和。
差分数组 主要适用场景是频繁对原始数组的某个区间的元素进行增减。

相关题目
1094. 拼车
1109. 航班预订统计
370. 区间加法

# 1094. 拼车
class Solution:def carPooling(self, trips: List[List[int]], capacity: int) -> bool:nums = [0]*1000df = Difference(nums)for trip in trips:df.increment(trip[1], trip[2]-1, trip[0])res = df.restore()for need in res:if need > capacity:return Falsereturn Trueclass Difference:def __init__(self, nums):assert len(nums)>0self.diff = [None]*len(nums)self.diff[0] = nums[0]for i in range(1, len(nums)):self.diff[i] = nums[i] - nums[i-1]# 给闭区间 [i, j] 增加 val（可以是负数）def increment(self, i, j, val):self.diff[i] += valif j + 1 < len(self.diff):self.diff[j+1] -= val# 根据差分数组还原结果def restore(self):self.res = [None]*len(self.diff)self.res[0] = self.diff[0]for i in range(1, len(self.diff)):self.res[i] = self.res[i-1] + self.diff[i]return self.res

# 1109. 航班预订统计
class Solution:def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:nums = [0]*ndf = Difference(nums)for booking in bookings:df.increment(booking[0]-1, booking[1]-1, booking[2])return df.restore()class Difference:def __init__(self, nums):assert len(nums)>0self.diff = [None]*len(nums)self.diff[0] = nums[0]for i in range(1, len(nums)):self.diff[i] = nums[i] - nums[i-1]# 给闭区间 [i, j] 增加 val（可以是负数）def increment(self, i, j, val):self.diff[i] += valif j + 1 < len(self.diff):self.diff[j+1] -= val# 根据差分数组还原结果def restore(self):self.res = [None]*len(self.diff)self.res[0] = self.diff[0]for i in range(1, len(self.diff)):self.res[i] = self.res[i-1] + self.diff[i]return self.res