发表于 2024.06.14

• 一开始以为这种区间查询和更新问题需要使用线段树or树状数组的结构，没想到可以利用前缀和的逆形式 - 差分数组来解决，差分数组本质也是个前缀和，但区别在于其维护的是元素间的差值，而不是元素本身。这样，对于区间[l, r]的更新操作add(l, r, val)可以转化为diff[l] += val和diff[r + 1] -= val，而每个元素本身的值可以累加前面的差分值得到。这样，对于add(l, r, val)此类的更新操作操作，只需要O(1)的时间复杂度即可完成。差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。而前缀和主要适用原始数组不会被修改的情况下，频繁查询某个区间的累加和。

  class Solution:
      def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
          diff = [0] * 1001
          min_val = 0  # 记录最左侧的位置, 方便提前终止区间
          max_val = 0  # 记录最右侧的位置, 以方便提前终止区间
          for num_passengers, u, v in trips:
              diff[u] += num_passengers
              diff[v] -= num_passengers
              min_val, max_val = min(min_val, u), max(max_val, v)
  
          # 从左往右累加差分数组以恢复原数组, 并同时检查是否超载
          cur_num = 0
          for i in range(min_val, max_val):
              cur_num += diff[i]
              if cur_num > capacity:
                  return False
          return True

  关于差分数组的更多应用，可以参考：

  • https://labuladong.online/algo/data-structure/diff-array/
• LC 题目链接