当前位置：首页 > news >正文

前缀和与差分进阶总结 | 技巧归纳与实战应用

news 2026/5/24 0:57:21

前缀和与差分进阶总结 | 技巧归纳与实战应用

引言

前缀和与差分是数组处理中两种重要且互补的技术。它们看似简单，却在 LeetCode 和实际工程中有着广泛的应用。前缀和将区间查询从 O(n) 优化到 O(1)，差分将区间更新从 O(n) 优化到 O(1)。两者的结合使用可以高效解决大量区间查询和更新问题。

本文将对前缀和与差分的进阶应用进行系统性的总结归纳，帮助读者建立完整的知识体系。

前缀和的类型分类

一维前缀和

一维前缀和是最基础的形式。给定数组 nums，定义 prefix[i] = sum(nums[0:i])，即前 i 个元素的和。使用前缀和，可以 O(1) 计算任意区间 [l, r] 的和：sum[l, r] = prefix[r+1] - prefix[l]。

一维前缀和的应用场景包括：

LeetCode 303：区域和检索（不可变数组）
LeetCode 560：和为 K 的子数组
LeetCode 724：寻找数组的中心下标

二维前缀和

二维前缀和是前缀和概念在二维数组上的扩展。给定矩阵 matrix，定义 prefix[i][j] 为以 (0, 0) 为左上角、(i, j) 为右下角的矩形区域中所有元素的和。

二维前缀和的计算公式：prefix[i][j] = matrix[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]

二维前缀和的应用场景包括：

LeetCode 304：二维区域和检索（不可变矩阵）
LeetCode 1314：矩阵区域和

前缀积与前缀最大值

前缀和可以推广到其他满足结合律的运算：

前缀积：prefix[i] = prod(nums[0:i])
前缀最大值：prefix[i] = max(nums[0:i])
前缀最小值：prefix[i] = min(nums[0:i])

这些推广在特定问题中非常有用。

差分的类型分类

一维差分

一维差分数组 diff 定义为：diff[i] = nums[i] - nums[i-1]（i > 0），diff[0] = nums[0]。

区间更新 [l, r] 加上 val 的操作转化为：diff[l] += val，diff[r+1] -= val。

差分的核心价值在于：将 O(n) 的区间更新转化为 O(1) 的单点更新，最后通过一次前缀和计算得到最终结果。

二维差分

二维差分用于批量更新矩阵中的矩形区域。更新矩形 [(r1, c1), (r2, c2)] 加上 val 的操作转化为四个角落的差分更新：

diff[r1][c1] += val
diff[r1][c2+1] -= val
diff[r2+1][c1] -= val
diff[r2+1][c2+1] += val

然后对差分数组求二维前缀和得到更新后的矩阵。

前缀和与哈希表结合

核心思想

前缀和与哈希表结合是解决"子数组统计"问题的强大工具。其核心思想是：将"子数组的某种属性"转化为"两个前缀和的差"，然后使用哈希表快速查找满足条件的配对。

典型应用

LeetCode 560（和为 K 的子数组）：子数组和等于 K <=> 两个前缀和的差等于 K

def subarraySum(nums, k): prefix_sum = 0 count = 0 prefix_map = {0: 1} for num in nums: prefix_sum += num count += prefix_map.get(prefix_sum - k, 0) prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1 return count

LeetCode 523（连续的子数组和）：子数组和是 K 的倍数 <=> 两个前缀和对 K 同余

def checkSubarraySum(nums, k): prefix_sum = 0 index_map = {0: -1} for i, num in enumerate(nums): prefix_sum += num mod = prefix_sum % k if k != 0 else prefix_sum if mod in index_map: if i - index_map[mod] >= 2: return True else: index_map[mod] = i return False

LeetCode 1248（统计优美子数组）：恰好 K 个奇数 <=> 两个前缀和（奇数计数）的差等于 K

def numberOfSubarrays(nums, k): prefix_sum = 0 count = 0 prefix_map = {0: 1} for num in nums: prefix_sum += num % 2 count += prefix_map.get(prefix_sum - k, 0) prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1 return count

滑动窗口与前缀和

滑动窗口的特殊情况

对于有序数组或具有单调性的数组，滑动窗口可以代替哈希表。例如，在和至少为 K 的子数组问题中：

def minSubArrayLen(k, nums): left = 0 current_sum = 0 min_len = float('inf') for right in range(len(nums)): current_sum += nums[right] while current_sum >= k: min_len = min(min_len, right - left + 1) current_sum -= nums[left] left += 1 return min_len if min_len != float('inf') else 0

何时使用滑动窗口 vs 哈希表

滑动窗口适用于：

数组元素有单调性（如正数数组）
需要找最长/最短子数组
问题具有"扩张-收缩"的模式

哈希表适用于：

数组元素没有单调性
需要找恰好等于某值
问题转化为前缀和差的问题

前缀积的高级应用

除自身以外数组的乘积

def productExceptSelf(nums): n = len(nums) answer = [1] * n for i in range(1, n): answer[i] = answer[i - 1] * nums[i - 1] product = 1 for i in range(n - 2, -1, -1): product *= nums[i + 1] answer[i] *= product return answer

累加和与累乘积的结合

在某些问题中，可能需要同时考虑累加和累乘。核心思想类似，只是需要处理乘法的特殊性（如零的处理）。

差分的扩展应用

航班预订问题

def corpFlightBookings(bookings, n): diff = [0] * (n + 1) for first, last, seats in bookings: diff[first - 1] += seats diff[last] -= seats result = [0] * n result[0] = diff[0] for i in range(1, n): result[i] = result[i - 1] + diff[i] return result

拼车问题

def carPooling(trips, capacity): diff = [0] * 1001 for num, start, end in trips: diff[start] += num diff[end] -= num current = 0 for i in range(1001): current += diff[i] if current > capacity: return False return True