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

前缀和数组一文详解

前缀和数组一文详解

  • 前言
  • 一、前缀和数组的基本概念
    • 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 不越界)。这是前缀和数组的核心优势,将原本需要遍历区间计算和的操作,优化为简单的数组元素相减操作,极大提高了计算效率。
0

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!
觉得有用就点个赞、收进收藏夹吧!关注我,获取更多干货~

http://www.xdnf.cn/news/609067.html

相关文章:

  • Vue3.5 企业级管理系统实战(二十):角色菜单
  • JDK21全景图:关键特性与升级价值
  • AI预测3D新模型百十个定位预测+胆码预测+去和尾2025年5月23日第86弹
  • 如何轻松擦U盘? (3个解决方案)
  • AI Study,学习计划
  • 2024 CKA模拟系统制作 | Step-By-Step | 3、CKA考试系统的技术设置
  • 基于SpringBoot的网上租赁系统设计与实现
  • YOLOv10 系列算法学习笔记一
  • vue开发中常用方法笔记
  • springboot3+vue3融合项目实战-大事件文章管理系统-登录优化redis
  • Vue3和React中插件化设计思想
  • YOLO11解决方案之速度估算探索
  • LaTeX中所有数字都应该在数学环境中吗?
  • Python项目中的文件夹命名和结构设计建议
  • JavaScript的三大核心组成:ECMAScript、DOM与BOM
  • WebGL开发技巧
  • 一些Dify聊天系统组件流程图架构图
  • Idea如果有参数,怎么debug
  • Grafana XSSOpenRedirectSSRF漏洞复现(CVE-2025-4123)
  • 一键生成专业流程图:Draw.io与AI结合的高效绘图指南
  • 生成式 AI:解锁人类创造力的智能引擎
  • 图解深度学习 - 特征工程(DL和ML的核心差异)
  • JavaScript篇:解密ES6的“藏宝图“:Set和Map的奇妙冒险
  • Don’t Shake the Wheel 论文阅读
  • PycharmFlask 学习心得2:路由
  • 中国软件行业 2024 年度分析报告
  • AI时代的弯道超车之第二十章:哪些工作AI是替代不了的
  • AtCoder Beginner Contest 406(ABCD)
  • 大疆制图跑飞马D2000的正射与三维模型
  • 在 Docker 中启动 Jupyter Notebook