1. 从比那名居的桃子看前缀和的核心思想第一次看到比那名居的桃子这个标题很多人会一头雾水——这到底是个什么项目其实这是一个典型的算法练习题目命名风格用了一个带有东方Project角色元素的趣味名字来包装一道前缀和Prefix Sum的经典题目。核心场景大致是这样的有一排桃子每个桃子有对应的甜度值需要反复查询某个区间内桃子的甜度总和或者找出满足特定甜度条件的连续区间。这类多次区间查询的需求正是前缀和算法最擅长的战场。前缀和这个东西说穿了就一句话用一次预处理把区间求和的复杂度从O(n)降到O(1)。如果你写过暴力解法每次查询都从头遍历一遍区间那查询m次就是O(n×m)数据量一大直接超时。而前缀和的做法是先把数组累加一遍生成一个前缀和数组之后每次查询只需要做一次减法。这个思路简单到几乎不像一个算法但它的应用范围极广从一维数组到二维矩阵从静态查询到配合差分做区间修改都是围绕这个核心思想展开的。这篇文章适合谁看如果你正在学算法基础刚接触前缀和但还不太清楚什么时候该用、怎么用、边界怎么处理那这篇内容就是写给你的。如果你已经会用一维前缀和但遇到二维矩阵或者区间修改区间查询就卡壳那后面几个章节也会帮你把思路理顺。我会从最基础的一维场景讲起逐步扩展到二维、差分配合、以及实际刷题中容易踩的坑尽量把每个为什么这么做都讲透。2. 前缀和的基本原理与适用场景拆解2.1 前缀和到底在做什么先抛开代码用一个生活化的例子来理解。假设你有一本账本记录了从1月到12月每个月的开销。现在有人问你3月到7月一共花了多少钱你可以把3、4、5、6、7五个月的数字加起来这是暴力做法。但如果对方连续问你十个不同的区间你每次都要重新加一遍就很烦。前缀和的做法是你先在账本最前面加一行累计开销记录从1月到当前月的总开销。比如累计到2月是5000累计到7月是12000那3月到7月的开销就是12000减去前2个月的累计假设是5000得到7000。一次减法搞定不需要再逐月累加。用数学语言描述定义prefix[i]表示数组a[0]到a[i-1]的和注意这里用的是左闭右开或者前i个元素的写法不同实现有差异后面会详细讲。那么区间[l, r]的和就等于prefix[r1] - prefix[l]。这个公式是前缀和的灵魂所有的变体都是围绕它展开的。2.2 什么情况下该用前缀和不是所有求和问题都适合前缀和。它的最佳适用场景有几个特征数组内容是静态的或者修改很少、查询次数很多、查询的是连续区间的聚合值。如果数组会被频繁修改那每次修改后都要重新构建前缀和数组反而得不偿失这时候应该考虑树状数组或线段树。具体来说以下几种场景见到就可以直接上前缀和多次查询数组某个区间的和数组不变需要快速判断是否存在某个子数组的和满足条件比如和为零、和等于目标值二维矩阵中多次查询子矩阵的元素和配合差分数组实现区间修改、单点查询或区间修改、区间查询求数组中连续子数组的最大和、最小和等变体问题反过来如果题目要求边修改边查询而且修改和查询的次数都很大那前缀和就不是最优解了。这一点在刷题时要有意识地区分不要看到区间求和四个字就无脑套前缀和。2.3 一维前缀和的构建与查询一维前缀和的实现非常直接。假设原始数组是a长度为n我们创建一个长度为n1的前缀和数组pre其中pre[0] 0pre[i] pre[i-1] a[i-1]。注意这里的下标对应关系pre[i]表示的是原数组前i个元素的和也就是a[0]到a[i-1]。# 一维前缀和构建 a [3, 1, 4, 1, 5, 9, 2, 6] n len(a) pre [0] * (n 1) for i in range(1, n 1): pre[i] pre[i - 1] a[i - 1] # 查询区间 [l, r] 的和0-indexed包含l和r def query(l, r): return pre[r 1] - pre[l]为什么前缀和数组要多开一位、pre[0]设为0这是为了让区间查询的公式统一不需要对l0的情况做特殊判断。如果pre[0]不是0而是a[0]那查询从下标0开始的区间时就要额外处理代码会变得不优雅。这个多开一位、首位为0的技巧在前缀和、差分、动态规划中都非常常见值得养成习惯。查询区间[l, r]时用pre[r1] - pre[l]这里的r1是因为pre的下标比原数组向右偏移了一位。你可以这样记pre[i]代表原数组前i个元素的和所以前r1个元素的和减去前l个元素的和剩下的正好是下标l到r这一段。3. 从一维到二维前缀和的进阶玩法3.1 二维前缀和的构建逻辑一维前缀和解决的是线段上的区间求和二维前缀和解决的是矩阵中的子矩阵求和。思路是一样的只是累加的方向从一个变成了两个。定义pre[i][j]表示从矩阵左上角(0,0)到(i-1, j-1)这个矩形区域内所有元素的和。注意这里同样采用了多开一行一列的做法pre的大小是(m1) × (n1)第一行和第一列都是0。构建公式是pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] matrix[i-1][j-1]。这个公式的含义是当前位置的前缀和等于上方的前缀和加上左方的前缀和减去左上方被重复计算的部分再加上当前格子的值。用面积来类比你要算一个矩形区域的总和可以把它拆成上面一块加左边一块但左上角那块被加了两次所以要减掉一次。# 二维前缀和构建 matrix [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] m, n len(matrix), len(matrix[0]) pre [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] matrix[i-1][j-1]这段代码看着简单但第一次写的时候很容易把下标搞混。我的建议是在纸上画一个3×3的矩阵手动把pre数组填一遍填完之后再对照代码看理解会深刻很多。纯看代码不动手很容易产生我懂了的错觉一到自己写就出错。3.2 二维子矩阵查询的公式推导构建好二维前缀和之后查询子矩阵(r1, c1)到(r2, c2)包含边界的和公式是pre[r21][c21] - pre[r1][c21] - pre[r21][c1] pre[r1][c1]。这个公式同样可以用面积来理解。大矩形是从左上角到(r2, c2)的总和减去上方不需要的部分从左上角到(r1-1, c2)再减去左方不需要的部分从左上角到(r2, c1-1)但左上角那块被减了两次所以要加回来一次从左上角到(r1-1, c1-1)。# 查询子矩阵 (r1, c1) 到 (r2, c2) 的和 def query_matrix(r1, c1, r2, c2): return (pre[r21][c21] - pre[r1][c21] - pre[r21][c1] pre[r1][c1])我见过很多人在这个公式上翻车最常见的问题是符号搞反或者下标偏移量搞错。一个实用的记忆方法是把四个角想象成大减小、减上加也就是总面积减去两个不需要的条带再加回被多减的角落。每次写的时候默念一遍这个口诀基本不会错。3.3 二维前缀和的典型应用场景二维前缀和在图像处理中有一个非常直观的应用计算图像中某个矩形区域的像素平均值。比如你有一张灰度图想对每个像素做局部均值滤波就可以用二维前缀和快速求出任意窗口内的像素和再除以窗口面积得到均值。这比每次遍历窗口内的像素要快得多尤其是在窗口较大的时候。另一个常见场景是统计矩阵中满足某种条件的子矩阵数量。比如给定一个01矩阵问有多少个子矩阵的和等于k。暴力枚举所有子矩阵是O(m²n²)配合二维前缀和可以把查询降到O(1)整体复杂度降到O(m²n²)的枚举部分虽然枚举本身还是四重循环但至少每次查询不用再遍历了。如果进一步优化枚举方式比如固定上下边界把问题转化为一维可以做到O(m²n)甚至更好。4. 差分数组前缀和的逆运算4.1 差分的基本概念如果说前缀和是累加那差分就是作差两者互为逆运算。差分数组diff[i] a[i] - a[i-1]记录的是相邻元素之间的变化量。对差分数组求前缀和就能还原出原数组。差分最大的价值在于快速实现区间修改。假设你要把数组a中下标[l, r]范围内的所有元素都加上v暴力做法是遍历一遍O(n)时间。但用差分数组只需要做两次操作diff[l] v和diff[r1] - vO(1)时间。最后对差分数组求一次前缀和就得到了修改后的数组。# 差分数组实现区间修改 a [1, 2, 3, 4, 5] n len(a) diff [0] * (n 1) diff[0] a[0] for i in range(1, n): diff[i] a[i] - a[i-1] # 把区间 [1, 3] 的元素都加上10 diff[1] 10 diff[4] - 10 # r1 4 # 还原数组 result [0] * n result[0] diff[0] for i in range(1, n): result[i] result[i-1] diff[i] # result [1, 12, 13, 14, 5]这个技巧在多次区间修改、最后统一查询的场景下极其高效。如果修改和查询交替进行那就需要配合树状数组或线段树来维护差分数组的前缀和这就是更高级的话题了。4.2 差分与前缀和的配合使用差分和前缀和经常成对出现。一个典型的模式是先用差分做多次区间修改再对最终的差分数组求前缀和得到结果数组最后再用前缀和做多次区间查询。整个流程下来修改是O(1)查询是O(1)只有最后还原数组是O(n)整体效率非常高。这种模式在日程安排会议室预订区间覆盖类问题中很常见。比如有一系列活动每个活动占用时间区间[start, end]问哪个时间点被占用的次数最多。用差分数组每个活动做两次操作最后求前缀和扫描一遍找最大值即可。注意差分数组在r1处减v时如果r1等于n也就是区间右端点到了数组末尾那这个减法操作会越界。所以差分数组通常要多开一位大小设为n1这样diff[n]可以安全地承接这个减法。4.3 二维差分简介二维差分是一维差分的扩展用于快速实现子矩阵的批量修改。对矩阵中(r1, c1)到(r2, c2)的区域都加上v需要在差分矩阵的四个位置做操作diff[r1][c1] v、diff[r1][c21] - v、diff[r21][c1] - v、diff[r21][c21] v。最后对差分矩阵做二维前缀和就得到了修改后的矩阵。这个四个角的操作逻辑和二维前缀和查询公式是对应的都是加加减减的容斥原理。如果你理解了二维前缀和的查询公式二维差分的修改操作就是它的逆过程理解起来会顺畅很多。5. 实操中的常见问题与排查技巧5.1 下标越界与边界处理前缀和相关的代码十次报错有八次是下标问题。最常见的情况是前缀和数组开小了、查询时r1越界、差分修改时r1越界。我的经验是只要涉及前缀和或差分数组一律多开一位宁可浪费一个空间也不要为了省那一点内存而引入边界判断的麻烦。另一个容易出错的地方是区间的开闭。有些题目给的区间是左闭右开有些是左闭右闭有些下标从1开始有些从0开始。每次写代码之前先在注释里明确写下本代码中区间为左闭右闭下标从0开始然后严格按照这个约定来写。不要一边写一边改约定那样必出错。5.2 数据类型溢出问题前缀和的一个隐藏陷阱是数值溢出。原数组中的元素可能不大但累加之后的前缀和可能超出int的范围。比如原数组有10^5个元素每个元素最大10^9那前缀和最大可以到10^14这已经超过了32位int的上限约2.1×10^9。所以在写前缀和的时候前缀和数组的类型要比原数组的类型更宽原数组用int前缀和就用long long。这个问题在刷题时特别容易被忽略因为测试用例可能刚好不溢出但提交后在某些边界用例上就挂了。养成习惯看到求和、累加先想一下数据范围估算一下最大可能的值再决定用什么类型。5.3 前缀和与哈希表的组合技巧有一类问题不是直接求区间和而是问是否存在一个子数组的和等于k。这类问题用前缀和配合哈希表可以在O(n)时间内解决。思路是遍历数组维护当前的前缀和cur如果cur - k在哈希表中出现过说明存在一个子数组的和为k。哈希表中存储的是每个前缀和第一次出现的下标或者出现的次数取决于题目要求。# 求和为k的子数组个数 def subarray_sum(nums, k): count 0 cur 0 seen {0: 1} # 前缀和为0出现1次空数组 for num in nums: cur num if cur - k in seen: count seen[cur - k] seen[cur] seen.get(cur, 0) 1 return count这个技巧的关键在于seen {0: 1}这个初始化。它的含义是前缀和为0的情况出现了1次对应的是空数组。如果不加这个初始化当子数组从下标0开始时就会漏算。这个细节很多人第一次写的时候会忽略导致结果偏小。5.4 常见问题速查表问题现象可能原因排查方法查询结果偏大前缀和数组初始化错误pre[0]不是0检查pre[0]是否设为0查询结果偏小区间公式用错漏加了某个边界手动模拟小数组验证公式数组越界前缀和数组没多开一位将数组大小设为n1结果溢出前缀和类型不够宽改用long long或Python的int子数组计数不对哈希表缺少{0:1}初始化检查seen的初始状态二维查询结果错误四个角的符号搞反画图验证容斥公式6. 刷题实战中的经验与避坑指南6.1 什么时候不该用前缀和虽然前缀和很好用但也不是万能的。我踩过的一个坑是有一道题需要频繁修改数组元素同时频繁查询区间和。我第一反应是用前缀和结果每次修改后都要重建前缀和数组时间复杂度反而比暴力还高。后来改用树状数组才通过。所以判断标准很简单看修改操作和查询操作的比例。如果修改很少、查询很多前缀和是首选。如果修改和查询都很多那就该上树状数组或线段树。如果只有修改没有查询差分数组就够了。如果只有查询没有修改前缀和是最优解。这个决策树在刷题时非常实用能帮你快速锁定正确的数据结构。6.2 前缀和的调试技巧前缀和相关的bug往往很隐蔽因为公式看起来都对但结果就是不对。我的调试方法是构造一个长度为3到5的小数组手动计算出前缀和数组和所有可能的查询结果然后和代码输出对比。小数组的好处是你可以完全掌控每一个数字一眼就能看出哪一步算错了。另一个技巧是打印中间结果。在构建完前缀和数组后先把它打印出来确认每个位置的值都符合预期再去写查询逻辑。很多人一上来就把构建和查询一起写完出了错不知道是构建错了还是查询错了排查起来很费劲。分步验证先确保构建正确再验证查询效率会高很多。6.3 前缀和在竞赛中的变体在算法竞赛中前缀和很少以裸题的形式出现更多的是作为解题的一个环节。常见的变体包括前缀和二分求满足条件的最短子数组、前缀和单调栈求子数组的最小和、前缀和哈希表求和为k的子数组、前缀和差分区间修改后查询等。这些组合技巧的核心都是前缀和但需要你对其他数据结构也有一定的理解。我的建议是先把一维和二维的裸前缀和练熟做到不看模板就能写出来然后再去刷组合类型的题目。裸模板都不熟就去搞组合很容易顾此失彼既没理解前缀和也没学会配合的技巧。6.4 一个容易被忽略的优化细节当查询次数非常多的时候即使每次查询是O(1)函数调用的开销也可能成为瓶颈。在Python中如果查询是在一个循环里反复调用函数可以考虑把查询逻辑内联到循环中减少函数调用的开销。虽然单次调用的开销很小但查询次数到了10^6级别累积起来就很可观了。另外如果查询的区间有规律比如每次查询的左右端点都在递增可以利用双指针或者滑动窗口来避免重复计算进一步优化。不过这种优化比较依赖具体题目不是所有场景都适用知道有这么个思路就行。7. 从桃子题目看前缀和的完整解题流程回到比那名居的桃子这个题目本身虽然我没有看到具体的题面但根据标题和前缀和这个关键词可以推测出大致的解题流程。假设题目是这样的有一排桃子每个桃子有一个甜度值需要回答多次查询每次查询某个区间内桃子的总甜度或者找出甜度之和最大的连续区间。解题的第一步是识别问题类型。看到多次查询区间求和这两个关键词基本可以确定用前缀和。第二步是确定数据范围看看数组长度和查询次数估算时间复杂度是否允许O(n)预处理加O(1)查询。第三步是处理输入输出把数据读进来构建前缀和数组。第四步是实现查询逻辑按照公式pre[r1] - pre[l]来计算。最后是验证边界情况比如查询整个数组、查询单个元素、查询空区间等。如果是求甜度之和最大的连续区间那就需要在前缀和的基础上再加一层逻辑遍历所有可能的右端点维护一个最小前缀和用当前前缀和减去最小前缀和就得到了以当前点为右端点的最大区间和。这个技巧叫做前缀和维护最小值是最大子数组和问题的一种解法。整个流程走下来核心代码可能只有十几行但背后的思考过程和对边界情况的处理才是真正考验功力的地方。前缀和这个工具本身不难难的是在合适的场景下想到它、用对它、处理好所有边界。这也是为什么我建议大家在刷题时不要只追求AC而是要把每道题的思路和坑点都记录下来形成自己的经验库。下次遇到类似的题目就能快速反应出该用什么方法而不是从头开始想。 
长河君 · 2026/10/20 1:42:20 · 阅读 1.2k 前缀和算法详解：从一维到二维、差分与刷题实战
1. 从比那名居的桃子看前缀和的核心思想第一次看到比那名居的桃子这个标题很多人会一头雾水——这到底是个什么项目其实这是一个典型的算法练习题目命名风格用了一个带有东方Project角色元素的趣味名字来包装一道前缀和Prefix Sum的经典题目。核心场景大致是这样的有一排桃子每个桃子有对应的甜度值需要反复查询某个区间内桃子的甜度总和或者找出满足特定甜度条件的连续区间。这类多次区间查询的需求正是前缀和算法最擅长的战场。前缀和这个东西说穿了就一句话用一次预处理把区间求和的复杂度从O(n)降到O(1)。如果你写过暴力解法每次查询都从头遍历一遍区间那查询m次就是O(n×m)数据量一大直接超时。而前缀和的做法是先把数组累加一遍生成一个前缀和数组之后每次查询只需要做一次减法。这个思路简单到几乎不像一个算法但它的应用范围极广从一维数组到二维矩阵从静态查询到配合差分做区间修改都是围绕这个核心思想展开的。这篇文章适合谁看如果你正在学算法基础刚接触前缀和但还不太清楚什么时候该用、怎么用、边界怎么处理那这篇内容就是写给你的。如果你已经会用一维前缀和但遇到二维矩阵或者区间修改区间查询就卡壳那后面几个章节也会帮你把思路理顺。我会从最基础的一维场景讲起逐步扩展到二维、差分配合、以及实际刷题中容易踩的坑尽量把每个为什么这么做都讲透。2. 前缀和的基本原理与适用场景拆解2.1 前缀和到底在做什么先抛开代码用一个生活化的例子来理解。假设你有一本账本记录了从1月到12月每个月的开销。现在有人问你3月到7月一共花了多少钱你可以把3、4、5、6、7五个月的数字加起来这是暴力做法。但如果对方连续问你十个不同的区间你每次都要重新加一遍就很烦。前缀和的做法是你先在账本最前面加一行累计开销记录从1月到当前月的总开销。比如累计到2月是5000累计到7月是12000那3月到7月的开销就是12000减去前2个月的累计假设是5000得到7000。一次减法搞定不需要再逐月累加。用数学语言描述定义prefix[i]表示数组a[0]到a[i-1]的和注意这里用的是左闭右开或者前i个元素的写法不同实现有差异后面会详细讲。那么区间[l, r]的和就等于prefix[r1] - prefix[l]。这个公式是前缀和的灵魂所有的变体都是围绕它展开的。2.2 什么情况下该用前缀和不是所有求和问题都适合前缀和。它的最佳适用场景有几个特征数组内容是静态的或者修改很少、查询次数很多、查询的是连续区间的聚合值。如果数组会被频繁修改那每次修改后都要重新构建前缀和数组反而得不偿失这时候应该考虑树状数组或线段树。具体来说以下几种场景见到就可以直接上前缀和多次查询数组某个区间的和数组不变需要快速判断是否存在某个子数组的和满足条件比如和为零、和等于目标值二维矩阵中多次查询子矩阵的元素和配合差分数组实现区间修改、单点查询或区间修改、区间查询求数组中连续子数组的最大和、最小和等变体问题反过来如果题目要求边修改边查询而且修改和查询的次数都很大那前缀和就不是最优解了。这一点在刷题时要有意识地区分不要看到区间求和四个字就无脑套前缀和。2.3 一维前缀和的构建与查询一维前缀和的实现非常直接。假设原始数组是a长度为n我们创建一个长度为n1的前缀和数组pre其中pre[0] 0pre[i] pre[i-1] a[i-1]。注意这里的下标对应关系pre[i]表示的是原数组前i个元素的和也就是a[0]到a[i-1]。# 一维前缀和构建 a [3, 1, 4, 1, 5, 9, 2, 6] n len(a) pre [0] * (n 1) for i in range(1, n 1): pre[i] pre[i - 1] a[i - 1] # 查询区间 [l, r] 的和0-indexed包含l和r def query(l, r): return pre[r 1] - pre[l]为什么前缀和数组要多开一位、pre[0]设为0这是为了让区间查询的公式统一不需要对l0的情况做特殊判断。如果pre[0]不是0而是a[0]那查询从下标0开始的区间时就要额外处理代码会变得不优雅。这个多开一位、首位为0的技巧在前缀和、差分、动态规划中都非常常见值得养成习惯。查询区间[l, r]时用pre[r1] - pre[l]这里的r1是因为pre的下标比原数组向右偏移了一位。你可以这样记pre[i]代表原数组前i个元素的和所以前r1个元素的和减去前l个元素的和剩下的正好是下标l到r这一段。3. 从一维到二维前缀和的进阶玩法3.1 二维前缀和的构建逻辑一维前缀和解决的是线段上的区间求和二维前缀和解决的是矩阵中的子矩阵求和。思路是一样的只是累加的方向从一个变成了两个。定义pre[i][j]表示从矩阵左上角(0,0)到(i-1, j-1)这个矩形区域内所有元素的和。注意这里同样采用了多开一行一列的做法pre的大小是(m1) × (n1)第一行和第一列都是0。构建公式是pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] matrix[i-1][j-1]。这个公式的含义是当前位置的前缀和等于上方的前缀和加上左方的前缀和减去左上方被重复计算的部分再加上当前格子的值。用面积来类比你要算一个矩形区域的总和可以把它拆成上面一块加左边一块但左上角那块被加了两次所以要减掉一次。# 二维前缀和构建 matrix [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] m, n len(matrix), len(matrix[0]) pre [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] matrix[i-1][j-1]这段代码看着简单但第一次写的时候很容易把下标搞混。我的建议是在纸上画一个3×3的矩阵手动把pre数组填一遍填完之后再对照代码看理解会深刻很多。纯看代码不动手很容易产生我懂了的错觉一到自己写就出错。3.2 二维子矩阵查询的公式推导构建好二维前缀和之后查询子矩阵(r1, c1)到(r2, c2)包含边界的和公式是pre[r21][c21] - pre[r1][c21] - pre[r21][c1] pre[r1][c1]。这个公式同样可以用面积来理解。大矩形是从左上角到(r2, c2)的总和减去上方不需要的部分从左上角到(r1-1, c2)再减去左方不需要的部分从左上角到(r2, c1-1)但左上角那块被减了两次所以要加回来一次从左上角到(r1-1, c1-1)。# 查询子矩阵 (r1, c1) 到 (r2, c2) 的和 def query_matrix(r1, c1, r2, c2): return (pre[r21][c21] - pre[r1][c21] - pre[r21][c1] pre[r1][c1])我见过很多人在这个公式上翻车最常见的问题是符号搞反或者下标偏移量搞错。一个实用的记忆方法是把四个角想象成大减小、减上加也就是总面积减去两个不需要的条带再加回被多减的角落。每次写的时候默念一遍这个口诀基本不会错。3.3 二维前缀和的典型应用场景二维前缀和在图像处理中有一个非常直观的应用计算图像中某个矩形区域的像素平均值。比如你有一张灰度图想对每个像素做局部均值滤波就可以用二维前缀和快速求出任意窗口内的像素和再除以窗口面积得到均值。这比每次遍历窗口内的像素要快得多尤其是在窗口较大的时候。另一个常见场景是统计矩阵中满足某种条件的子矩阵数量。比如给定一个01矩阵问有多少个子矩阵的和等于k。暴力枚举所有子矩阵是O(m²n²)配合二维前缀和可以把查询降到O(1)整体复杂度降到O(m²n²)的枚举部分虽然枚举本身还是四重循环但至少每次查询不用再遍历了。如果进一步优化枚举方式比如固定上下边界把问题转化为一维可以做到O(m²n)甚至更好。4. 差分数组前缀和的逆运算4.1 差分的基本概念如果说前缀和是累加那差分就是作差两者互为逆运算。差分数组diff[i] a[i] - a[i-1]记录的是相邻元素之间的变化量。对差分数组求前缀和就能还原出原数组。差分最大的价值在于快速实现区间修改。假设你要把数组a中下标[l, r]范围内的所有元素都加上v暴力做法是遍历一遍O(n)时间。但用差分数组只需要做两次操作diff[l] v和diff[r1] - vO(1)时间。最后对差分数组求一次前缀和就得到了修改后的数组。# 差分数组实现区间修改 a [1, 2, 3, 4, 5] n len(a) diff [0] * (n 1) diff[0] a[0] for i in range(1, n): diff[i] a[i] - a[i-1] # 把区间 [1, 3] 的元素都加上10 diff[1] 10 diff[4] - 10 # r1 4 # 还原数组 result [0] * n result[0] diff[0] for i in range(1, n): result[i] result[i-1] diff[i] # result [1, 12, 13, 14, 5]这个技巧在多次区间修改、最后统一查询的场景下极其高效。如果修改和查询交替进行那就需要配合树状数组或线段树来维护差分数组的前缀和这就是更高级的话题了。4.2 差分与前缀和的配合使用差分和前缀和经常成对出现。一个典型的模式是先用差分做多次区间修改再对最终的差分数组求前缀和得到结果数组最后再用前缀和做多次区间查询。整个流程下来修改是O(1)查询是O(1)只有最后还原数组是O(n)整体效率非常高。这种模式在日程安排会议室预订区间覆盖类问题中很常见。比如有一系列活动每个活动占用时间区间[start, end]问哪个时间点被占用的次数最多。用差分数组每个活动做两次操作最后求前缀和扫描一遍找最大值即可。注意差分数组在r1处减v时如果r1等于n也就是区间右端点到了数组末尾那这个减法操作会越界。所以差分数组通常要多开一位大小设为n1这样diff[n]可以安全地承接这个减法。4.3 二维差分简介二维差分是一维差分的扩展用于快速实现子矩阵的批量修改。对矩阵中(r1, c1)到(r2, c2)的区域都加上v需要在差分矩阵的四个位置做操作diff[r1][c1] v、diff[r1][c21] - v、diff[r21][c1] - v、diff[r21][c21] v。最后对差分矩阵做二维前缀和就得到了修改后的矩阵。这个四个角的操作逻辑和二维前缀和查询公式是对应的都是加加减减的容斥原理。如果你理解了二维前缀和的查询公式二维差分的修改操作就是它的逆过程理解起来会顺畅很多。5. 实操中的常见问题与排查技巧5.1 下标越界与边界处理前缀和相关的代码十次报错有八次是下标问题。最常见的情况是前缀和数组开小了、查询时r1越界、差分修改时r1越界。我的经验是只要涉及前缀和或差分数组一律多开一位宁可浪费一个空间也不要为了省那一点内存而引入边界判断的麻烦。另一个容易出错的地方是区间的开闭。有些题目给的区间是左闭右开有些是左闭右闭有些下标从1开始有些从0开始。每次写代码之前先在注释里明确写下本代码中区间为左闭右闭下标从0开始然后严格按照这个约定来写。不要一边写一边改约定那样必出错。5.2 数据类型溢出问题前缀和的一个隐藏陷阱是数值溢出。原数组中的元素可能不大但累加之后的前缀和可能超出int的范围。比如原数组有10^5个元素每个元素最大10^9那前缀和最大可以到10^14这已经超过了32位int的上限约2.1×10^9。所以在写前缀和的时候前缀和数组的类型要比原数组的类型更宽原数组用int前缀和就用long long。这个问题在刷题时特别容易被忽略因为测试用例可能刚好不溢出但提交后在某些边界用例上就挂了。养成习惯看到求和、累加先想一下数据范围估算一下最大可能的值再决定用什么类型。5.3 前缀和与哈希表的组合技巧有一类问题不是直接求区间和而是问是否存在一个子数组的和等于k。这类问题用前缀和配合哈希表可以在O(n)时间内解决。思路是遍历数组维护当前的前缀和cur如果cur - k在哈希表中出现过说明存在一个子数组的和为k。哈希表中存储的是每个前缀和第一次出现的下标或者出现的次数取决于题目要求。# 求和为k的子数组个数 def subarray_sum(nums, k): count 0 cur 0 seen {0: 1} # 前缀和为0出现1次空数组 for num in nums: cur num if cur - k in seen: count seen[cur - k] seen[cur] seen.get(cur, 0) 1 return count这个技巧的关键在于seen {0: 1}这个初始化。它的含义是前缀和为0的情况出现了1次对应的是空数组。如果不加这个初始化当子数组从下标0开始时就会漏算。这个细节很多人第一次写的时候会忽略导致结果偏小。5.4 常见问题速查表问题现象可能原因排查方法查询结果偏大前缀和数组初始化错误pre[0]不是0检查pre[0]是否设为0查询结果偏小区间公式用错漏加了某个边界手动模拟小数组验证公式数组越界前缀和数组没多开一位将数组大小设为n1结果溢出前缀和类型不够宽改用long long或Python的int子数组计数不对哈希表缺少{0:1}初始化检查seen的初始状态二维查询结果错误四个角的符号搞反画图验证容斥公式6. 刷题实战中的经验与避坑指南6.1 什么时候不该用前缀和虽然前缀和很好用但也不是万能的。我踩过的一个坑是有一道题需要频繁修改数组元素同时频繁查询区间和。我第一反应是用前缀和结果每次修改后都要重建前缀和数组时间复杂度反而比暴力还高。后来改用树状数组才通过。所以判断标准很简单看修改操作和查询操作的比例。如果修改很少、查询很多前缀和是首选。如果修改和查询都很多那就该上树状数组或线段树。如果只有修改没有查询差分数组就够了。如果只有查询没有修改前缀和是最优解。这个决策树在刷题时非常实用能帮你快速锁定正确的数据结构。6.2 前缀和的调试技巧前缀和相关的bug往往很隐蔽因为公式看起来都对但结果就是不对。我的调试方法是构造一个长度为3到5的小数组手动计算出前缀和数组和所有可能的查询结果然后和代码输出对比。小数组的好处是你可以完全掌控每一个数字一眼就能看出哪一步算错了。另一个技巧是打印中间结果。在构建完前缀和数组后先把它打印出来确认每个位置的值都符合预期再去写查询逻辑。很多人一上来就把构建和查询一起写完出了错不知道是构建错了还是查询错了排查起来很费劲。分步验证先确保构建正确再验证查询效率会高很多。6.3 前缀和在竞赛中的变体在算法竞赛中前缀和很少以裸题的形式出现更多的是作为解题的一个环节。常见的变体包括前缀和二分求满足条件的最短子数组、前缀和单调栈求子数组的最小和、前缀和哈希表求和为k的子数组、前缀和差分区间修改后查询等。这些组合技巧的核心都是前缀和但需要你对其他数据结构也有一定的理解。我的建议是先把一维和二维的裸前缀和练熟做到不看模板就能写出来然后再去刷组合类型的题目。裸模板都不熟就去搞组合很容易顾此失彼既没理解前缀和也没学会配合的技巧。6.4 一个容易被忽略的优化细节当查询次数非常多的时候即使每次查询是O(1)函数调用的开销也可能成为瓶颈。在Python中如果查询是在一个循环里反复调用函数可以考虑把查询逻辑内联到循环中减少函数调用的开销。虽然单次调用的开销很小但查询次数到了10^6级别累积起来就很可观了。另外如果查询的区间有规律比如每次查询的左右端点都在递增可以利用双指针或者滑动窗口来避免重复计算进一步优化。不过这种优化比较依赖具体题目不是所有场景都适用知道有这么个思路就行。7. 从桃子题目看前缀和的完整解题流程回到比那名居的桃子这个题目本身虽然我没有看到具体的题面但根据标题和前缀和这个关键词可以推测出大致的解题流程。假设题目是这样的有一排桃子每个桃子有一个甜度值需要回答多次查询每次查询某个区间内桃子的总甜度或者找出甜度之和最大的连续区间。解题的第一步是识别问题类型。看到多次查询区间求和这两个关键词基本可以确定用前缀和。第二步是确定数据范围看看数组长度和查询次数估算时间复杂度是否允许O(n)预处理加O(1)查询。第三步是处理输入输出把数据读进来构建前缀和数组。第四步是实现查询逻辑按照公式pre[r1] - pre[l]来计算。最后是验证边界情况比如查询整个数组、查询单个元素、查询空区间等。如果是求甜度之和最大的连续区间那就需要在前缀和的基础上再加一层逻辑遍历所有可能的右端点维护一个最小前缀和用当前前缀和减去最小前缀和就得到了以当前点为右端点的最大区间和。这个技巧叫做前缀和维护最小值是最大子数组和问题的一种解法。整个流程走下来核心代码可能只有十几行但背后的思考过程和对边界情况的处理才是真正考验功力的地方。前缀和这个工具本身不难难的是在合适的场景下想到它、用对它、处理好所有边界。这也是为什么我建议大家在刷题时不要只追求AC而是要把每道题的思路和坑点都记录下来形成自己的经验库。下次遇到类似的题目就能快速反应出该用什么方法而不是从头开始想。