差分数组的应用技巧

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

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

# 1094. 拼车
class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        nums = [0]*1000
        df = 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 False
        return True


class Difference:
    def __init__(self, nums):
        assert len(nums)>0
        self.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] += val
        if 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

    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

# 1109. 航班预订统计
class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        nums = [0]*n
        df = 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)>0
        self.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] += val
        if 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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38