前缀和数组一文详解
前缀和数组一文详解
- 前言
- 一、前缀和数组的基本概念
- 1.1 定义与原理
- 1.2 与动态规划的联系
- 二、前缀和数组的构建方法
- 2.1 一维前缀和数组构建
- 2.2 二维前缀和数组构建
- 三、前缀和数组的应用场景
- 3.1 区间和查询
- 3.2 子数组计数问题
- 3.3 二维子矩阵和查询
- 总结
前言
实际编码中,我们经常会遇到需要频繁计算数组区间和、区间最值等问题,前缀和数组作为一种高效解决此类问题的数据结构,通过预先处理数据,将原本时间复杂度较高的区间计算操作进行优化,显著提升程序效率。本文我将详细介绍前缀和数组的基本概念、构建方法、常见应用场景,并结合代码示例,带你深入理解并掌握这一实用的数据结构技巧。
一、前缀和数组的基本概念
1.1 定义与原理
前缀和数组,顾名思义,是记录原数组前缀元素累加和的数组。对于给定的数组 arr = [a1, a2, a3, ..., an]
,其前缀和数组 prefixSum
满足 prefixSum[i]
等于原数组中前 i
个元素的和(从 0 到 i - 1
索引的元素),即 prefixSum[i] = a0 + a1 + ... + a(i - 1)
,其中 prefixSum[0] = 0
(表示空前缀的和) 。
例如,对于数组 arr = [1, 3, 5, 7, 9]
,其前缀和数组 prefixSum = [0, 1, 1 + 3, 1 + 3 + 5, 1 + 3 + 5 + 7, 1 + 3 + 5 + 7 + 9] = [0, 1, 4, 9, 16, 25]
。通过前缀和数组,我们可以在 O ( 1 ) O(1) O(1) 的时间复杂度内计算出原数组任意区间 [left, right]
的元素和,计算公式为 prefixSum[right + 1] - prefixSum[left]
(这里假设前缀和数组的索引从 0 开始,且 right + 1
不越界)。这是前缀和数组的核心优势,将原本需要遍历区间计算和的操作,优化为简单的数组元素相减操作,极大提高了计算效率。
1.2 与动态规划的联系
前缀和数组的构建过程体现了动态规划的思想。动态规划的核心在于将问题分解为子问题,并通过保存子问题的解来避免重复计算。在构建前缀和数组时,prefixSum[i]
的值依赖于 prefixSum[i - 1]
,即 prefixSum[i] = prefixSum[i - 1] + arr[i - 1]
,这是一个典型的递推关系。通过这种递推,我们可以高效地计算出整个前缀和数组,利用了子问题的重叠性质,避免了重复计算数组前缀的和,这与动态规划的思想高度契合 。
二、前缀和数组的构建方法
2.1 一维前缀和数组构建
以 Python 为例构建一维前缀和数组的代码如下:
arr = [1, 3, 5, 7, 9]
prefixSum = [0]
for num in arr:prefixSum.append(prefixSum[-1] + num)
print(prefixSum)
上述代码中,首先初始化一个包含 0 的列表 prefixSum
,表示空前缀的和。然后通过遍历原数组 arr
,将每个元素依次累加到 prefixSum
中,从而得到完整的前缀和数组。
2.2 二维前缀和数组构建
在处理二维数组时,也可以构建二维前缀和数组,用于高效计算二维数组中任意子矩阵的元素和。对于二维数组 matrix
,其二维前缀和数组 prefixSum
满足 prefixSum[i][j]
等于原二维数组中左上角为 (0, 0)
,右下角为 (i - 1, j - 1)
的子矩阵的元素和。
实现二维前缀和数组构建的代码如下:
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
m, n = len(matrix), len(matrix[0])
prefixSum = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):for j in range(1, n + 1):prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + matrix[i - 1][j - 1]
print(prefixSum)
在上述代码中,首先初始化一个大小为 (m + 1) * (n + 1)
的二维列表 prefixSum
,并将其所有元素初始化为 0。然后通过两层循环遍历二维数组 matrix
,根据二维前缀和的递推公式 prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + matrix[i - 1][j - 1]
计算每个位置的前缀和。其中,prefixSum[i - 1][j]
和 prefixSum[i][j - 1]
分别表示上方和左方子矩阵的和,由于这两个和中 prefixSum[i - 1][j - 1]
被重复计算了一次,所以需要减去,再加上当前位置的元素 matrix[i - 1][j - 1]
,从而得到正确的前缀和。
三、前缀和数组的应用场景
3.1 区间和查询
这是前缀和数组最常见的应用场景。给定一个数组,需要频繁查询某个区间内元素的和,使用前缀和数组可以快速实现。例如,在一个存储学生成绩的数组中,要查询某个班级一段时间内学生的总成绩之和,就可以利用前缀和数组高效完成。
arr = [1, 3, 5, 7, 9]
prefixSum = [0]
for num in arr:prefixSum.append(prefixSum[-1] + num)
left, right = 1, 3 # 查询区间 [1, 3] 的和
intervalSum = prefixSum[right + 1] - prefixSum[left]
print(intervalSum) # 输出 15(即 3 + 5 + 7)
3.2 子数组计数问题
在一些问题中,需要统计满足特定条件的子数组数量。例如,统计数组中元素和为目标值 target
的子数组数量。可以通过前缀和数组结合哈希表来解决。思路是遍历前缀和数组,用哈希表记录每个前缀和出现的次数,对于当前前缀和 prefixSum[i]
,如果 prefixSum[i] - target
也在哈希表中,说明存在一个子数组的和为 target
,将其出现次数累加到结果中。
arr = [1, 0, 1]
target = 1
prefixSum = {0: 1} # 初始化哈希表,前缀和为 0 出现 1 次
currentSum = 0
count = 0
for num in arr:currentSum += numif currentSum - target in prefixSum:count += prefixSum[currentSum - target]prefixSum[currentSum] = prefixSum.get(currentSum, 0) + 1
print(count) # 输出 3
3.3 二维子矩阵和查询
在图像处理、地理信息系统等领域,经常需要处理二维数据,计算子矩阵的元素和。利用二维前缀和数组,可以在 O ( 1 ) O(1) O(1) 的时间复杂度内计算出任意子矩阵的元素和。例如,计算二维数组中左上角为 (x1, y1)
,右下角为 (x2, y2)
的子矩阵的和,计算公式为 prefixSum[x2 + 1][y2 + 1] - prefixSum[x1][y2 + 1] - prefixSum[x2 + 1][y1] + prefixSum[x1][y1]
。
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
m, n = len(matrix), len(matrix[0])
prefixSum = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):for j in range(1, n + 1):prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + matrix[i - 1][j - 1]
x1, y1 = 0, 0 # 子矩阵左上角坐标
x2, y2 = 1, 1 # 子矩阵右下角坐标
subMatrixSum = prefixSum[x2 + 1][y2 + 1] - prefixSum[x1][y2 + 1] - prefixSum[x2 + 1][y1] + prefixSum[x1][y1]
print(subMatrixSum) # 输出 12(即 1 + 2 + 4 + 5)
总结
前缀和数组作为一种简单而强大的数据结构,通过预先计算和存储数组的前缀和,为高效解决区间计算、子数组统计等问题提供了有力工具,无论是一维数组还是二维数组,前缀和数组的构建和应用都遵循一定的规律和方法。
That’s all, thanks for reading!
觉得有用就点个赞
、收进收藏
夹吧!关注
我,获取更多干货~