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

前缀和与差分进阶总结 | 技巧归纳与实战应用引言前缀和与差分是数组处理中两种重要且互补的技术。它们看似简单却在 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[r1] - 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 0diff[0] nums[0]。区间更新 [l, r] 加上 val 的操作转化为diff[l] valdiff[r1] - val。差分的核心价值在于将 O(n) 的区间更新转化为 O(1) 的单点更新最后通过一次前缀和计算得到最终结果。二维差分二维差分用于批量更新矩阵中的矩形区域。更新矩形 [(r1, c1), (r2, c2)] 加上 val 的操作转化为四个角落的差分更新diff[r1][c1] valdiff[r1][c21] - valdiff[r21][c1] - valdiff[r21][c21] val然后对差分数组求二维前缀和得到更新后的矩阵。前缀和与哈希表结合核心思想前缀和与哈希表结合是解决子数组统计问题的强大工具。其核心思想是将子数组的某种属性转化为两个前缀和的差然后使用哈希表快速查找满足条件的配对。典型应用LeetCode 560和为 K 的子数组子数组和等于 K 两个前缀和的差等于 Kdef 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 countLeetCode 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 FalseLeetCode 1248统计优美子数组恰好 K 个奇数 两个前缀和奇数计数的差等于 Kdef 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实战问题分类区间求和类区间求和类问题要求在一个数组上进行多次区间查询。如果数组不可变可以使用前缀和如果需要支持更新可以使用树状数组或线段树。典型问题LeetCode 303区域和检索不可变LeetCode 304二维区域和检索不可变LeetCode 307区域和检索可变子数组统计类子数组统计类问题要求统计满足某种条件的子数组数量。通常将问题转化为前缀和的配对问题使用哈希表解决。典型问题LeetCode 560和为 K 的子数组LeetCode 523连续的子数组和K 的倍数LeetCode 930和相同的二元子数组批量更新类批量更新类问题要求对数组进行多次区间更新最后查询最终结果。使用差分数组可以将每次更新优化到 O(1)。典型问题LeetCode 1109航班预订统计LeetCode 1094拼车复杂度分析时间复杂度前缀和构造O(n)差分构造O(n)单次区间查询O(1)前缀和单次区间更新O(1)差分前缀和 哈希表O(n)空间复杂度前缀和O(n)差分O(n)前缀和 哈希表O(n)面试中的常见问题问题1如何处理负数前缀和负数前缀和与正数前缀和没有本质区别。取模运算时需要注意 Python 和 Java 的差异。问题2如何在 O(1) 空间内解决前缀和问题某些问题可以通过数学推导避免使用哈希表。例如寻找和为 0 的最长子数组可以通过记录第一次出现的位置来 O(1) 空间解决。问题3如何处理大数据范围在某些语言中需要考虑整数溢出。可以使用 long 类型或 Python 的自动扩展整数。总结前缀和与差分是数组处理的两种核心技术。前缀和将区间查询优化到 O(1)差分将区间更新优化到 O(1)。两者的结合使用可以高效解决大量区间查询和更新问题。前缀和与哈希表的结合是解决子数组统计问题的强大工具。通过将问题转化为前缀和的配对我们可以在 O(n) 时间内解决看似需要 O(n²) 的问题。希望本文的总结能够帮助读者建立完整的前缀和与差分知识体系在面试和实际工作中游刃有余。