前阵子把前缀和相关的题又系统过了一遍绕来绕去发现这套东西表面看着简单真正上手写的时候索引偏移、二维边界、差分还原顺序每一个都能让人debug一晚上。前缀和Prefix Sum在Python里的实现往往只有几行但它背后解决的是算法里非常典型的一类问题频繁的区间查询。如果你经常被子数组、子矩阵、区间求和这类题卡住或者在实际业务里需要对连续时间段的数据做累计统计这篇总结应该能帮你把前缀和彻底吃透。这篇文章面向的是已经会基础Python语法、但还没系统整理过前缀和技巧的读者。我会从暴力解法为什么慢开始讲然后给出一维、二维前缀和的完整实现再讲差分数组这个前缀和的逆运算最后用几道经典题走一遍从读题到AC的完整过程。1. 从一道超时的题说起前缀和的动机与本质1.1 一个真实的暴力超时场景假设你现在拿到这样一个需求有一个长度为n的数组比如[3, 1, 4, 1, 5, 9, 2, 6]然后有m次查询每次问你某个区间[l, r]内的所有元素之和是多少。最直观的写法就是一个循环def range_sum(nums, queries): res [] for l, r in queries: total 0 for i in range(l, r 1): total nums[i] res.append(total) return res这个写法没毛病逻辑完全正确。但问题是假设n和m都是10的5次方量级每次查询都要遍历一遍区间最坏情况下总的时间复杂度是O(n*m)也就是10的10次方次操作。在Python里跑这个规模基本等于等死这就是典型的能跑但跑不动的代码。我第一次在笔试里遇到这类题的时候就是老老实实写了上面的暴力解法结果不出意外地超时了。那时候我才意识到面试官考察的根本不是你会不会写循环求和而是你有没有预处理的思维——把频繁重复计算的东西提前算好。1.2 前缀和的数学本质前缀和的核心思想特别朴素我先准备一个数组pre里面存的是从数组开头到当前位置的所有元素之和。比如对于上面的数组pre[0] 0一个方便计算的位置pre[1] 3pre[2] 3 1 4pre[3] 3 1 4 8...那么任意区间[l, r]的和可以直接用两个前缀和相减得到pre[r1] - pre[l]。为什么是r1而不是r因为pre[i]的语义是前i个元素的和pre[l]意味着下标0到l-1这些元素的和pre[r1]意味着下标0到r这些元素的和两者一减剩下的正好是下标l到r的元素。这个过程就是前缀和的核心数学本质区间和 两个前缀和的差。预处理的时间是O(n)每次查询的时间是O(1)总复杂度从O(n*m)降到了O(nm)。我自己的体会是前缀和本质上是在用空间换时间但换得非常划算——它只需要一个长度等于n1的额外数组省下的却是巨大量的重复求和运算。2. 一维前缀和公式、代码与最容易踩的索引坑2.1 两种常见的实现写法一维前缀和的Python实现非常简单常见的写法有两种。第一种是预先分配好长度的写法def build_prefix(nums): n len(nums) pre [0] * (n 1) for i in range(1, n 1): pre[i] pre[i - 1] nums[i - 1] return pre第二种是直接用append动态构建def build_prefix(nums): pre [0] for x in nums: pre.append(pre[-1] x) return pre我推荐第二种写法原因有两点第一它在代码上天然强调了pre[0] 0这个边界第二它不容易出现下标错位的问题因为你不需要在脑子里换算nums[i-1]还是nums[i]直接遍历原始数组的每个元素就行。这里要强调一个关键的索引约定pre[i]表示的是前i个元素的和而不是下标i之前的和。这个约定贯穿所有前缀和的推导只要你在写代码时始终记得pre的长度是n1pre[i]对应nums[0..i-1]的和后面很多坑都能绕开。2.2 区间查询的O(1)操作有了pre数组之后查询区间[l, r]的和就变成了一行代码def query(pre, l, r): return pre[r 1] - pre[l]比如查询上面数组的[2, 5]区间对应的元素是4, 1, 5, 9和是19。用pre算pre[6] - pre[2]pre[6]是前6个元素31415923pre[2]是前2个元素314相减正好是19。这个操作没有任何循环也不涉及任何乘法就是一个减法。在实际刷题的时候这种查询之间互相独立、查询次数又多的场景前缀和几乎是唯一的最优解。我还见过有人把pre数组本身当作结果输出然后查询的时候写pre[r] - pre[l-1]。这也能用但属于另一种约定——pre[i]表示前i1个元素的和。不建议混用否则代码里一会儿减一一会儿不减一非常容易出现思维混乱。2.3 索引偏移的经典错误与规避我当初学前缀和的时候写过一段让我极其痛苦的代码pre [0] * n for i in range(1, n): pre[i] pre[i - 1] nums[i]这段代码的问题是pre[0]一直等于0pre[1]等于nums[1]但nums[1]其实是数组的第二个元素。这样一来所有从那个位置取值的区间和都会错位一位。更隐蔽的是如果数组元素恰好有正有负某些查询看起来结果又碰巧是对的导致我复盘的时候完全找不到问题在哪。规避这种索引坑的方法其实很简单严格遵循偏移1位的约定让pre[i]对应前i个元素的和。具体来说就是构建时pre[i] pre[i-1] nums[i-1]查询时区间[l, r]的和 pre[r1] - pre[l]只要记住pre比nums长一位开头多一个0你就再也不会被索引困扰了。另外如果你用的是append写法几乎天然就符合这个约定这也是我强烈推荐它的原因。3. 二维前缀和矩阵问题里的容斥原理3.1 从一维到二维的推广一维前缀和解决的是数组区间问题二维前缀和解决的是矩阵子矩阵问题。思路是一样的预处理一个和矩阵同形的二维数组每个位置存的是从左上角到当前位置这个矩形区域内的所有元素之和。假设原始矩阵是matrix行数和列数分别是m和n那么二维前缀和S可以这样构建这里同样采用偏移1位的写法def build_2d_prefix(matrix): m len(matrix) n len(matrix[0]) S [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): row_sum 0 for j in range(1, n 1): row_sum matrix[i - 1][j - 1] S[i][j] S[i - 1][j] row_sum return S我这里用了每行滚动累加的方式实际计算每个位置时S[i][j]等于上面一行同列的前缀和S[i-1][j]再加上本行从开头到当前列的所有元素之和row_sum。这样的写法避免了重复计算整行的和效率会高一点。更常见的递推公式是容斥形式S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] matrix[i-1][j-1]翻译成直觉语言当前位置的值 上方矩形的和 左方矩形的和 - 左上角被重复算了一次的矩形的和 原矩阵当前位置的值。3.2 子矩阵和的查询公式有了二维前缀和矩阵S要查询任意一个左上角为(r1, c1)、右下角为(r2, c2)的子矩阵的元素和用的是下面这个公式def query_2d(S, r1, c1, r2, c2): return S[r2 1][c2 1] - S[r1][c2 1] - S[r2 1][c1] S[r1][c1]原因还是容斥原理S[r21][c21]是整个从左上角到(r2, c2)的矩形和先减去上半部分S[r1][c21]再减去左半部分S[r21][c1]这时候左上角被减了两次所以再加回来一次S[r1][c1]。我建议在理解这个公式时画一个4x4的小矩阵把每个S[i][j]都标注成从左上角开始的一块区域然后实际算一次。这个方法我每次都推荐给入门的同学因为它比死记公式牢靠得多——你一旦画过一遍容斥的加减逻辑就刻在脑子里了。3.3 二维场景的边界与空矩阵处理二维前缀和最容易被忽略的坑是空矩阵的边界判断。如果matrix本身是空的或者matrix[0]是空的len(matrix[0])会直接报错IndexError。所以在构建二维前缀和的入口处一定要记得加判断if not matrix or not matrix[0]: return []另一个坑是查询坐标的合法性。虽然通常题目保证查询坐标合法但如果你写的是供内部使用的工具函数最好自己加一层断言或者防御性处理。我之前在线笔试的时候有一道题就是因为查询坐标可能越界我没有处理导致好几个case直接RTE。还有一点值得注意二维前缀和矩阵是(m1) * (n1)的形状比原始矩阵多一行一列。如果你习惯用numpy也可以直接用np.cumsum(matrix, axis0)再对行做一次cumsum得到相同效果但纯Python实现时还是老老实实写循环最稳妥因为numpy的计算结果类型是ndarray在普通算法题里反倒要额外转回list不算划算。4. 差分数组前缀和的逆运算4.1 差分的核心思想如果说前缀和解决的核心问题是频繁查询区间和那差分数组解决的核心问题就是频繁对区间进行整体加减操作最后一次查询所有结果。什么叫区间整体加减举个例子有一个数组现在给你一系列操作每个操作说从下标l到下标r的所有元素都加上一个值v。操作次数很多每个操作都去遍历区间那时间复杂度自然又是O(n*m)。差分数组就是为了解决这个问题出现的。差分数组的定义是这样的d [0] * n d[0] nums[0] for i in range(1, n): d[i] nums[i] - nums[i - 1]也就是说差分数组d[i]存的是原数组相邻元素的差。这里最关键的性质是对差分数组求前缀和可以得到原来的数组。这正是差分是前缀和的逆运算这句话的含义。4.2 区间加法的O(1)实现当我们需要对区间[l, r]内的所有元素都加上一个值v时不需要去改原数组只需要在差分数组上操作两个位置d[l] v if r 1 n: d[r 1] - v为什么这样有效因为差分数组的语义是相邻元素的差值。d[l] v会让从l开始的所有元素在原数组上都多出v而d[r1] - v会把超出r这个范围的增量抵消掉。这样一来原数组从l到r的值都会加v而r1及之后的值不变。等所有操作都执行完之后只需要对差分数组求一次前缀和就能还原出最终的原数组for i in range(1, n): d[i] d[i - 1]我看过很多初学者在这里犯迷糊其实可以把这个过程类比成在高铁上给某一段车厢发纪念品你只需要在起点站上车发然后在终点站下车前把发放状态取消掉不需要每站挨个发。差分就是这种状态的记录。4.3 什么时候用差分而不是线段树我经常被问到一个问题区间加法和区间查询都有很多次到底该用差分还是线段树这里有个很实用的判断标准如果操作是先批量修改、后统一查询差分数组就是最优解代码简单时间O(n)。如果操作是修改和查询穿插进行比如改一次查一次再改再查那就需要线段树或者树状数组了。如果每次查询还需要实时返回某个区间的和并且在两次查询之间还有更新这种动态场景前缀和和差分都搞不定。换句话说差分数组和前缀和适合的是静态场景数据在预处理阶段就都定好了之后只是不停地查。如果题目里出现了在线这种词往往就意味着要上数据结构的进阶方案了。5. 前缀和的进阶变体哈希优化、异或前缀与滑动窗口的配合5.1 前缀和 哈希表解决子数组计数问题基本的前缀和能解决求某个区间的和但有一类更刁钻的问题问的是有多少个子数组的和等于K。比如LeetCode 560题就是经典代表。如果还是用普通前缀和你可以先算出pre数组然后枚举所有可能的左右端点检查pre[r1] - pre[l] k这样时间复杂度是O(n^2)。在数据量大的时候依然会挂。优化思路是这样的我们遍历原数组计算当前位置的前缀和cur。对于每个cur我们需要知道的是在它之前有多少个前缀和的值等于cur - k。因为这些前缀和对应的位置正好是能让cur - pre[i] k成立的位置。于是可以用一个哈希表来记录每个前缀和值出现的次数def subarray_sum(nums, k): count {0: 1} cur 0 ans 0 for x in nums: cur x ans count.get(cur - k, 0) count[cur] count.get(cur, 0) 1 return ans这里有个很关键的细节初始化哈希表时要放入{0: 1}这代表一个空前缀和它的意义是如果当前的前缀和本身恰好等于k那么它和空前缀之间就形成了一个合法子数组。我自己第一次写的时候漏了这个初始化结果所有case都少算了一部分答案。5.2 异或前缀和前缀和不止适用于加法对于异或运算同样适用而且性质更好。我们把pre[i]定义成前i个元素的异或结果那么区间[l, r]的异或值就是pre[r1] ^ pre[l]。这里不需要容斥因为异或运算有一个自反性质x ^ x 0。所以两个相同的前缀异或值相遇异或结果就是0中间的部分自然就露出来了。这个技巧在解决找出数组中所有异或和为0的子数组个数这类问题上非常有用。举个例子LeetCode 525题连续数组这道题要找的是最长的连续子数组使得子数组中0和1的数量相同。一个很巧妙的做法是把0看成-1把1看成1用前缀和来记录遍历到当前位置时的累计和。当两个位置的前缀和值相等时说明这一段的0和1数量相同因为它们的差值抵消了。5.3 前缀和与滑动窗口的边界很多人会混淆滑动窗口和前前缀和的适用场景这里我帮你分清楚如果数组元素全为正数要求最短/最长满足某个条件的子数组滑动窗口是最优解因为窗口扩大或缩小的单调性让双指针能在线性时间内移动。如果数组元素有正有负滑动窗口的单调性失效因为窗口变长不一定让和变大这时候前缀和往往配合哈希表或排序才能胜任。我曾经在一道题里先用了滑动窗口结果因为数组里有负数窗口的收缩逻辑陷入了死循环。后来改成前缀和加二分才解决。所以我个人建议遇到子数组和等于/大于/小于某个值这类问题第一时间先判断数组里是否有负数。有负数基本就要往前缀和的方向思考了。6. Python实现中的性能与代码风格建议6.1 用itertools.accumulate精简代码Python标准库里的itertools.accumulate可以直接生成前缀和序列代码会非常简洁from itertools import accumulate nums [3, 1, 4, 1, 5, 9, 2, 6] pre [0] list(accumulate(nums))这个写法的时间复杂度同样是O(n)但代码量几乎降到了最低。我用这个方式在六十几行的代码里实现了一个小的数据统计脚本用于生成每日订单的累计量曲线效果非常理想。不过要注意的是accumulate返回的是一个迭代器如果你需要随机访问某个位置的前缀和必须通过list()转成列表否则没法按下标取值。6.2 大数据量下的Python取舍前缀和本身的时间复杂度是O(n)但Python在大规模数据下会暴露出语言性能的天花板。比如处理10的7次方级别的数据时append循环的速度会比C的同等方式慢很多。我在实际处理千万级流量日志的累计分布时最后是切到了numpy.cumsum速度一下子提升了十几倍import numpy as np arr np.array(nums) pre_arr np.cumsum(arr)所以我的建议是算法刷题场景下用纯Python的append写法就够这样能保持代码的可读性也避免引入numpy后在线评测系统上因库缺失或版本问题报错。但如果是本地处理真实业务数据、数据量大且有numpy环境完全可以放开用np.cumsum。另外Python的整数可以无限大计算前缀和时不会像C那样有int溢出的问题这算是Python一个隐形的福利在累加大量正整数时特别省心。6.3 刷题习惯与边界测试我见过很多人在刷前缀和题目时代码测了几个样例能过就急着交结果一提交就WA。这往往不是因为思路错了而是边界没测到。我总结了一份前缀和必测的边界清单数组长度为0或1的情况查询的l等于0的情况这最考验前缀和pre[0] 0的约定是否准确查询区间覆盖整个数组的情况数组中有大量0或者全是负数的情况差分数组操作中区间右端点恰好等于n-1的情况此时r1正好越界每条边界都可以用几行小样例验证别嫌麻烦。我自己的做法是写一个简单的暴力解法和前缀和解法对照着跑随机数据两边结果不一致时再debug效率高很多。这个方法也推荐给你等于用一个笨办法来给聪明办法兜底。7. 实战验证四道经典题从读题到AC的完整走查7.1 LeetCode 303区域和检索 - 数组不可变这道题几乎是纯前缀和的入门题。题目的要求是构建一个类支持sumRange(left, right)方法返回从left到right的元素和。我的实现思路是直接在初始化时构建好前缀和数组然后sumRange里做一次减法class NumArray: def __init__(self, nums): self.pre [0] for x in nums: self.pre.append(self.pre[-1] x) def sumRange(self, left: int, right: int) - int: return self.pre[right 1] - self.pre[left]这道题我推荐所有人亲手写一遍因为它是所有前缀和题型的骨架。你把它写熟了后面的二维和差分题都会顺畅很多。初始化O(n)查询O(1)这个复杂度就是前缀和的标准表现。7.2 LeetCode 304二维区域和检索 - 矩阵不可变这是303的二维升级版。构建二维前缀和矩阵后查询时用容斥公式逻辑和前面第3章讲的一致class NumMatrix: def __init__(self, matrix): if not matrix or not matrix[0]: self.S [] return m, n len(matrix), len(matrix[0]) S [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): S[i][j] (S[i-1][j] S[i][j-1] - S[i-1][j-1] matrix[i-1][j-1]) self.S S def sumRegion(self, row1, col1, row2, col2): S self.S return (S[row21][col21] - S[row1][col21] - S[row21][col1] S[row1][col1])我在这道题的实现上犯过一个迷糊构建时把S[i][j]的递推关系写成了S[i-1][j-1] matrix[i-1][j-1]漏掉了左方和上方那两个大矩形结果查询小于3x3的矩阵时是对的一旦矩阵变大就全乱了。所以构建二维前缀和时一定要想清楚你算的究竟是整个左上矩形还是某个小矩形别贪图少写一个变量。7.3 LeetCode 1109航班预订统计差分经典题这道题描述是这样的有n个航班用1到n编号现在有bookings[i] [first_i, last_i, seats_i]表示从first_i到last_i的航班每个都预定了seats_i个座位最后返回每个航班的总预定数。这题就是典型的多次区间更新最后一次性查询直接用差分数组class Solution: def corpFlightBookings(self, bookings, n): diff [0] * (n 1) for l, r, seats in bookings: diff[l - 1] seats diff[r] - seats ans [] cur 0 for i in range(n): cur diff[i] ans.append(cur) return ans很多人在这道题里卡住的一个点是题目里的航班编号是1-indexed而数组下标是0-indexed所以first_i要减1再对应到差分数组下标。同时差分数组我开到了n1的长度这样即使r恰好等于n也不会越界。这道题如果用暴力每次预订都要遍历一遍区间复杂度是O(n * bookings)大概率超时。而差分数组的解法只需要O(len(bookings) n)几乎是一边遍历一边就出结果了。我强烈建议你用这道题来检验自己对差分理解的深度因为面试里它出现的频率很高而且换个马甲就是考同一套东西。7.4 LeetCode 560和为 K 的子数组前缀和哈希这道题我在第5节已经给出核心代码这里再补一个完整的走查过程。题目问的是连续子数组中和为k的个数注意这里子数组必须是连续的而且元素可能有负数所以滑动窗口直接出局。我的思路是这样的从左到右遍历数组维护当前前缀和cur同时维护一个哈希表记录每个前缀和值出现的次数。对于当前位置cur - k这个值如果在之前的某个前缀和位置出现过那么就说明那一段到当前这一段的和恰好是k。累加这些次数就是一个合法的答案数。class Solution: def subarraySum(self, nums, k): prefix_count {0: 1} cur 0 ans 0 for x in nums: cur x ans prefix_count.get(cur - k, 0) prefix_count[cur] prefix_count.get(cur, 0) 1 return ans这里最关键的一步是先查答案再更新哈希表。如果先更新哈希表再查就会把当前这个位置自己也算进去导致重复计数。我实际调试这道题时就是因为把这两行顺序写反了答案始终比期望值大了一圈。后来我把中间过程打出来才意识到当前前缀和不能和它自己匹配。这道题吃透之后你再看一些类似的子数组和统计题目会发现套路高度一致哈希表存历史前缀和遍历时做差查表再更新当前前缀和。这就是一法通、万法通的效果。我自己实际用Python跑过这四道题的完整流程从读题到AC基本都在五分钟以内核心的思考时间几乎全部花在确认这道题是前缀和/差分场景还是需要更复杂的数据结构上。等你把前缀和的几个变体都练熟了这种判断就会变成一种直觉——看到区间查询想前缀和看到批量区间更新想差分看到子数组计数想哈希表辅助一秒钟就能定下方向。
