前缀和算法

前缀和算法 是一种通过预处理数组，快速计算任意区间和的技巧。它能在 O(1) 时间复杂度内回答区间和的查询，适用于需要频繁计算子数组/子区间和的问题。以下是其核心应用场景、实现方法及经典例题：

一、适用场景

频繁查询区间和
- 多次计算数组的某一子区间 [L, R] 的和。
统计满足条件的子数组数量
- 例如“和为k的子数组数量”、“和为偶数的子数组数量”等。
处理环形数组或二维矩阵
- 环形数组通过复制数组处理，二维矩阵扩展为二维前缀和。
结合哈希表优化查找
- 寻找满足 preSum[j] - preSum[i] = target 的索引组合。

二、实现步骤

预处理前缀和数组
- 定义 preSum[i] 表示数组前 i 项的和（索引通常从1开始）。
- 递推公式：preSum[i] = preSum[i-1] + nums[i-1]。
计算区间和
- 区间 [L, R] 的和为 preSum[R+1] - preSum[L]（左闭右闭区间）。
结合哈希表优化
- 遍历时记录前缀和出现次数，快速统计满足条件的子数组。

三、经典例题与代码

1. 一维前缀和（区间和查询）

class PrefixSum:def __init__(self, nums):n = len(nums)self.preSum = [0] * (n + 1)for i in range(1, n+1):self.preSum[i] = self.preSum[i-1] + nums[i-1]def query(self, L, R):  # 闭区间 [L, R]return self.preSum[R+1] - self.preSum[L]# 示例
nums = [1, 2, 3, 4]
ps = PrefixSum(nums)
print(ps.query(1, 2))  # 输出 2+3=5

2. 统计和为k的子数组数量（哈希优化）

def subarraySum(nums, k):preSum = {0: 1}  # 初始前缀和为0出现1次current_sum = 0count = 0for num in nums:current_sum += num# 若 current_sum - target 存在，则存在子数组和为kcount += preSum.get(current_sum - k, 0)preSum[current_sum] = preSum.get(current_sum, 0) + 1return count# 示例
nums = [1, 1, 1]
print(subarraySum(nums, 2))  # 输出 2

3. 二维前缀和（矩阵区域和）

class MatrixPrefixSum:def __init__(self, matrix):m, n = len(matrix), len(matrix[0])self.preSum = [[0]*(n+1) for _ in range(m+1)]for i in range(1, m+1):for j in range(1, n+1):self.preSum[i][j] = matrix[i-1][j-1] + self.preSum[i-1][j] + self.preSum[i][j-1] - self.preSum[i-1][j-1]def query(self, x1, y1, x2, y2):  # 左上角(x1,y1)，右下角(x2,y2)return self.preSum[x2+1][y2+1] - self.preSum[x1][y2+1] - self.preSum[x2+1][y1] + self.preSum[x1][y1]# 示例
matrix = [[1, 2, 3],[4, 5, 6],[7, 8, 9]
]
mps = MatrixPrefixSum(matrix)
print(mps.query(1, 1, 2, 2))  # 输出 5+6+8+9=28