前缀和与差分 (Prefix Sum & Difference)

LeetCodePrefix SumDifference前缀和差分算法

前缀和与差分（Prefix Sum & Difference）

前缀和用于快速计算区间和，差分用于高效处理区间修改，是数组区间问题的常用技巧。

原理与常见类型

  • 前缀和：sum[i] = a[0] + … + a[i-1]，区间和为sum[j+1]-sum[i]
  • 差分数组：diff[i] = a[i] - a[i-1]，区间加减可O(1)处理

典型例题

1. 区域和检索 - 数组不可变（前缀和）

class NumArray:
    def __init__(self, nums):
        self.sums = [0]
        for num in nums:
            self.sums.append(self.sums[-1] + num)
    def sumRange(self, i, j):
        return self.sums[j+1] - self.sums[i]

2. 航班预订统计（差分）

def corpFlightBookings(bookings, n):
    diff = [0]*(n+2)
    for l, r, v in bookings:
        diff[l] += v
        diff[r+1] -= v
    res = [0]*(n+1)
    for i in range(1, n+1):
        res[i] = res[i-1] + diff[i]
    return res[1:]

3. 连续子数组的和（前缀和+哈希）

def subarraySum(nums, k):
    count = 0
    pre = 0
    mp = {0:1}
    for x in nums:
        pre += x
        count += mp.get(pre-k, 0)
        mp[pre] = mp.get(pre, 0) + 1
    return count

应用场景

  • 区间和、区间频率统计
  • 区间加减、区间更新
  • 子数组和、区间计数

相关文章