跳至主要內容

前缀和算法详解

SyYhunfhds2026/4/17大约 9 分钟

前缀和算法详解

1. 前缀和算法概述

前缀和是一种简单而强大的算法技巧，主要用于快速计算数组中连续子数组的和。它通过预处理数组，将原数组转换为前缀和数组，从而将区间查询的时间复杂度从O(n)降低到O(1)。

1.1 基本概念

前缀和数组：对于原数组 nums，其前缀和数组 prefix 定义为：

prefix[0] = 0
prefix[1] = nums[0]
prefix[2] = nums[0] + nums[1]
prefix[3] = nums[0] + nums[1] + nums[2]
...
prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

1.2 核心思想

前缀和的核心思想是空间换时间：通过预先计算并存储前缀和，使得后续的区间和查询可以在常数时间内完成。

2. 一维前缀和

2.1 实现方法

# 计算前缀和数组
def calculate_prefix_sum(nums):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i-1] + nums[i-1]
    return prefix

# 查询区间 [left, right] 的和
def range_sum(prefix, left, right):
    return prefix[right + 1] - prefix[left]

2.2 时间复杂度分析

  • 预处理时间：O(n)，其中n是数组长度
  • 查询时间：O(1)，每次查询都是常数时间
  • 空间复杂度：O(n)，需要额外存储前缀和数组

2.3 示例

原数组：[1, 2, 3, 4, 5]

前缀和数组：[0, 1, 3, 6, 10, 15]

查询区间 [1, 3] 的和：prefix[4] - prefix[1] = 10 - 1 = 9，即 2 + 3 + 4 = 9

3. 二维前缀和

3.1 实现方法

二维前缀和用于快速计算二维矩阵中任意子矩阵的和。

# 计算二维前缀和矩阵
def calculate_2d_prefix_sum(matrix):
    m, n = len(matrix), len(matrix[0])
    prefix = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
    
    return prefix

# 查询子矩阵 (x1, y1) 到 (x2, y2) 的和
def range_sum_2d(prefix, x1, y1, x2, y2):
    return prefix[x2+1][y2+1] - prefix[x1][y2+1] - prefix[x2+1][y1] + prefix[x1][y1]

3.2 时间复杂度分析

  • 预处理时间：O(m*n)，其中m和n是矩阵的行数和列数
  • 查询时间：O(1)，每次查询都是常数时间
  • 空间复杂度：O(m*n)，需要额外存储前缀和矩阵

3.3 示例

原矩阵：

[1, 2, 3]
[4, 5, 6]
[7, 8, 9]

前缀和矩阵：

[0, 0, 0, 0]
[0, 1, 3, 6]
[0, 5, 12, 21]
[0, 12, 27, 45]

查询子矩阵 (0, 0) 到 (1, 1) 的和：prefix[2][2] - prefix[0][2] - prefix[2][0] + prefix[0][0] = 12 - 0 - 0 + 0 = 12，即 1 + 2 + 4 + 5 = 12

4. 前缀和的变体

4.1 差分数组

差分数组是前缀和的逆运算，用于高效处理区间更新操作。

# 计算差分数组
def calculate_difference_array(nums):
    n = len(nums)
    diff = [0] * n
    diff[0] = nums[0]
    for i in range(1, n):
        diff[i] = nums[i] - nums[i-1]
    return diff

# 应用区间更新 [left, right] 增加 val
def apply_update(diff, left, right, val):
    diff[left] += val
    if right + 1 < len(diff):
        diff[right + 1] -= val

# 从差分数组恢复原数组
def restore_array(diff):
    n = len(diff)
    nums = [0] * n
    nums[0] = diff[0]
    for i in range(1, n):
        nums[i] = nums[i-1] + diff[i]
    return nums

4.2 前缀异或和

前缀异或和用于快速计算数组中连续子数组的异或值。

# 计算前缀异或和数组
def calculate_prefix_xor(nums):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i-1] ^ nums[i-1]
    return prefix

# 查询区间 [left, right] 的异或和
def range_xor(prefix, left, right):
    return prefix[right + 1] ^ prefix[left]

4.3 前缀乘积

前缀乘积用于快速计算数组中连续子数组的乘积。

# 计算前缀乘积数组
def calculate_prefix_product(nums):
    n = len(nums)
    prefix = [1] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i-1] * nums[i-1]
    return prefix

# 查询区间 [left, right] 的乘积
def range_product(prefix, left, right):
    return prefix[right + 1] // prefix[left]

5. 前缀和的应用场景

5.1 区间和查询

问题描述：多次查询数组中某个区间的和。

解决方案：使用前缀和数组，每次查询时间复杂度O(1)。

示例：

  • 频繁查询学生成绩区间和
  • 计算股票价格区间变化

5.2 子数组和问题

问题描述：找到和为目标值的子数组。

解决方案：使用前缀和 + 哈希表，时间复杂度O(n)。

示例：

def subarray_sum(nums, k):
    prefix_sum = 0
    count = 0
    sum_map = {0: 1}  # 前缀和为0的情况出现一次
    
    for num in nums:
        prefix_sum += num
        # 检查是否存在前缀和为 prefix_sum - k 的情况
        if prefix_sum - k in sum_map:
            count += sum_map[prefix_sum - k]
        # 更新哈希表
        sum_map[prefix_sum] = sum_map.get(prefix_sum, 0) + 1
    
    return count

5.3 二维区域和查询

问题描述：多次查询二维矩阵中某个子矩阵的和。

解决方案：使用二维前缀和矩阵，每次查询时间复杂度O(1)。

示例：

  • 图像处理中的区域亮度计算
  • 地理信息系统中的区域数据统计

5.4 差分数组应用

问题描述：对数组的多个区间进行更新操作，最后求数组的最终状态。

解决方案：使用差分数组，时间复杂度O(n + m)，其中m是更新操作的次数。

示例：

  • 航班预订统计
  • 区间加法问题

5.5 前缀异或和应用

问题描述：找到异或和为目标值的子数组。

解决方案：使用前缀异或和 + 哈希表，时间复杂度O(n)。

示例：

  • 寻找异或和为0的子数组
  • 数组中异或和的区间查询

6. 经典算法题解析

6.1 一维前缀和应用

LeetCode 303. 区域和检索 - 数组不可变

问题描述：给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。

解决方案：

class NumArray:
    def __init__(self, nums):
        self.prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.prefix[i+1] = self.prefix[i] + nums[i]
    
    def sumRange(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

6.2 二维前缀和应用

LeetCode 304. 二维区域和检索 - 矩阵不可变

问题描述：给定一个二维矩阵 matrix，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

解决方案：

class NumMatrix:
    def __init__(self, matrix):
        if not matrix or not matrix[0]:
            self.prefix = None
            return
        
        m, n = len(matrix), len(matrix[0])
        self.prefix = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                self.prefix[i][j] = matrix[i-1][j-1] + self.prefix[i-1][j] + self.prefix[i][j-1] - self.prefix[i-1][j-1]
    
    def sumRegion(self, row1, col1, row2, col2):
        if not self.prefix:
            return 0
        return self.prefix[row2+1][col2+1] - self.prefix[row1][col2+1] - self.prefix[row2+1][col1] + self.prefix[row1][col1]

6.3 前缀和 + 哈希表应用

LeetCode 560. 和为K的子数组

问题描述：给定一个整数数组和一个整数 k，找到该数组中和为 k 的连续子数组的个数。

解决方案：

def subarraySum(nums, k):
    count = 0
    prefix_sum = 0
    sum_map = {0: 1}  # 初始前缀和为0的情况
    
    for num in nums:
        prefix_sum += num
        # 检查是否存在前缀和为 prefix_sum - k 的情况
        if prefix_sum - k in sum_map:
            count += sum_map[prefix_sum - k]
        # 更新哈希表
        sum_map[prefix_sum] = sum_map.get(prefix_sum, 0) + 1
    
    return count

6.4 差分数组应用

LeetCode 1109. 航班预订统计

问题描述：这里有 n 个航班，它们分别从 1 到 n 进行编号。我们有一份航班预订表 bookings，表中第 i 条预订记录 bookings[i] = [first, last, seats] 意味着在从 first 到 last（包含 first 和 last）的每个航班上预订了 seats 个座位。请你返回一个长度为 n 的数组 answer，其中 answer[i] 是航班 i + 1 的预订座位总数。

解决方案：

def corpFlightBookings(bookings, n):
    # 初始化差分数组
    diff = [0] * (n + 2)  # 多留两个位置，避免越界
    
    # 应用所有预订
    for first, last, seats in bookings:
        diff[first] += seats
        diff[last + 1] -= seats
    
    # 计算前缀和得到最终结果
    answer = [0] * n
    current = 0
    for i in range(1, n + 1):
        current += diff[i]
        answer[i - 1] = current
    
    return answer

7. 前缀和算法的优化技巧

7.1 空间优化

对于一些场景，可以不需要存储完整的前缀和数组，而是使用一个变量实时计算前缀和。

示例：在计算子数组和为k的问题中，只需要维护当前前缀和和哈希表，不需要存储所有前缀和。

7.2 处理负数

当前缀和可能为负数时，哈希表仍然可以正常工作，因为Python的字典可以处理负数键。

7.3 处理大数

当前缀和可能很大时，需要注意数据类型的溢出问题。在Python中，整数的大小没有限制，所以不需要担心溢出。

7.4 多维前缀和的优化

对于高维前缀和，可以使用类似二维前缀和的方法，但需要注意维度的处理顺序和边界条件。

8. 总结

前缀和算法是一种简单而强大的算法技巧，通过空间换时间的思想，将区间查询的时间复杂度从O(n)降低到O(1)。它不仅适用于一维数组，还可以扩展到二维甚至更高维的情况。

前缀和的主要应用场景包括：

  • 频繁的区间和查询
  • 子数组和问题
  • 二维区域和查询
  • 区间更新操作（差分数组）
  • 异或和相关问题

通过掌握前缀和算法及其变体，我们可以更高效地解决许多与区间操作相关的问题，提高算法的时间效率。

提示

前缀和算法的关键在于理解其核心思想：通过预处理计算前缀和，将区间查询转化为两个前缀和的差，从而实现常数时间的查询。

9. 练习题目

  1. LeetCode 303. 区域和检索 - 数组不可变
  2. LeetCode 304. 二维区域和检索 - 矩阵不可变
  3. LeetCode 560. 和为K的子数组
  4. LeetCode 1109. 航班预订统计
  5. LeetCode 523. 连续的子数组和
  6. LeetCode 974. 和可被 K 整除的子数组
  7. LeetCode 1248. 统计「优美子数组」
  8. LeetCode 1310. 子数组异或查询

通过这些练习，你可以更好地掌握前缀和算法的应用技巧，提高解决相关问题的能力。

编辑此页
最近更新
贡献者: SyYhunfhds
Trae编辑
Copyright © 2026 SyYhunfhds