提到前缀数组很多人的第一反应是LeetCode入门题里那个prefixSum[i] prefixSum[i-1] nums[i]。但真正把它用明白、用出价值的人其实不多。前缀数组也叫前缀和本质上是一种预处理换查询的思路一次性建表换来任意区间求和从O(n)降到O(1)。这篇文章我想从原理讲到实战再聊到它的软肋——特别是和树状数组的关系用具体的n16的例子把sum(11)、add(3,x)这类操作说透。适合刚学算法的同学建立整体认知也适合写业务代码的工程师在遇到区间聚合统计时多一个顺手的选择。1. 前缀数组的核心价值把O(n)区间查询降成O(1)1.1 一个最常见的场景多次区间求和假设你有一个长度为n的数组现在要回答m次询问每次给一个区间[l, r]求这个区间内所有元素的和。最朴素的做法是每次询问都遍历区间def range_sum(nums, l, r): total 0 for i in range(l, r 1): total nums[i] return total单次询问是O(n)m次询问就是O(n*m)。当n和m都到10^5级别这个复杂度在比赛中基本会被卡死在业务里也就是慢查询。而用前缀数组构建过程是O(n)之后每次查询是O(1)。也就是说把大量时间花在一次性预处理上后续的每次查询都变成两次数组访问加一次减法。用空间换时间这在数据量大的场景下收益非常明显。1.2 前缀这个名字到底指什么前缀就是从数组开头到某个位置这一段。对于原数组a[0], a[1], ..., a[n-1]前缀数组pre[i]表示a[0] a[1] ... a[i]也就是从起点到下标i的所有元素之和。举个例子。原数组下标01234a25183对应的前缀数组下标01234pre2781619可以看到pre[3] 2 5 1 8 16就是从开头到下标3的累加结果。每一个pre[i]都是一路从头加过来的部分和这就是前缀二字的由来。1.3 核心公式区间和等于前缀数组两项相减这是整个前缀数组的灵魂$$\text{sum}(l, r) pre[r] - pre[l-1]$$为什么成立因为pre[r]是a[0]到a[r]的和pre[l-1]是a[0]到a[l-1]的和两者相减正好把a[0]到a[l-1]的部分抵消掉剩下的就是a[l]到a[r]。如果l 0那pre[l-1]就是pre[-1]为了避免处理负索引要么单独判断要么在建表时把前缀数组做成n1的长度让pre[i1]表示前i个元素的和。后一种做法更干净后面我会详细讲。注意区间求和不是前缀数组唯一能干的事前缀是一种思维方式可以推广到异或、乘积、计数统计等场景后面有专门一节展开。2. 建表与查询最小可运行的代码与边界细节2.1 递推建表的一行核心代码前缀数组的构建非常自然就是递推# 原数组 a [2, 5, 1, 8, 3] n len(a) # 前缀数组pre[i] 表示 a[0] 到 a[i-1] 的和 pre [0] * (n 1) for i in range(1, n 1): pre[i] pre[i - 1] a[i - 1]这里pre的长度是n1pre[0] 0是哨兵。为什么要在前面垫一个0因为这样pre[i]就可以统一表示前i个元素的和查询区间[l, r]时用pre[r1] - pre[l]不需要单独处理l0的情况。这个递推式的意思很直白前i个元素的和 前i-1个元素的和 第i个元素下标i-1。它不是什么高深的数学结论就是一个累加过程的缓存。2.2 查询区间的下标换算用上面的pre结构查询[l, r]区间和是def range_sum(pre, l, r): # l 和 r 是原数组下标0-based return pre[r 1] - pre[l]对应例子里查[1, 3]元素为5 1 8 14range_sum(pre, 1, 3) # pre[4] - pre[1] 19 - 2 17? 等一下哎这里我算一下。例子里a [2, 5, 1, 8, 3]pre长度6i012345pre[i]02781619查[1, 3]就是pre[4] - pre[1] 16 - 2 14正确。因为前4个元素是251816前1个元素是2相减得51814。这里最常见的坑就是下标差一。我的习惯是建表时pre[i]表示前i个元素的和查询时统一用pre[r1] - pre[l]。只要代码里到处都遵守这一个约定就不会混乱。最怕的是有时候用前i个有时候用到下标i为止很容易出错。2.3 一种常见的偏移约定1-based竞赛圈习惯直接把原数组也改成1-based即下标从1开始读入时存到a[1]到a[n]。这样前缀数组pre[i] pre[i-1] a[i]查询[l, r]用pre[r] - pre[l-1]。两种写法本质是一样的选哪种取决于你后续要混合什么操作。如果只是单纯给数组做前缀和用 Python 的 0-based 加n1长度就很清晰如果后面要接树状数组、差分数组之类的进阶结构1-based 往往更顺手因为树状数组的下标从1开始是刻在骨子里的。我自己在比赛里更常用1-based在写业务脚本处理数据时更常用0-based。选择标准就一条和你要搭配的其他代码保持同一个约定。3. 不只是求和前缀思想的高频扩展用法3.1 二维前缀和子矩阵求和一维前缀和解决的是线段求和二维前缀和解决的是矩形求和。核心思路一样只是变成二维递推# grid 是 m 行 n 列的矩阵 prefix [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): prefix[i][j] (prefix[i-1][j] prefix[i][j-1] - prefix[i-1][j-1] grid[i-1][j-1])查询左上角(r1, c1)到右下角(r2, c2)的子矩阵和total (prefix[r21][c21] - prefix[r1][c21] - prefix[r21][c1] prefix[r1][c1])这个公式的来源是容斥原理prefix[r21][c21]是大矩形的和减掉上面的长条减掉左边的长条但左上角那块被减了两次所以要加回来一次。面试里考察二维前缀和的题不算少LeetCode 304 就是典型的例子。3.2 前缀异或和区间异或与子数组性质求和可以前缀异或同样可以前缀。因为异或运算自带自反性x ^ x 0所以区间异或结果可以直接用两个前缀异或值相异或得到。# 前缀异或 px [0] * (n 1) for i in range(1, n 1): px[i] px[i - 1] ^ a[i - 1] # 区间 [l, r] 的异或和 xor_result px[r 1] ^ px[l]这个技巧在处理找出数组中哪两个数的异或最大之类的问题时很关键配合字典树可以做很多经典题目。它的本质还是前缀思想把区间查询转化为两个前缀结构的运算。3.3 差分数组前缀数组的逆运算如果说前缀数组是由原数组生成累积数组那么差分数组就是由原数组生成相邻差值数组是前缀的逆操作。# 差分数组 diff [0] * n diff[0] a[0] for i in range(1, n): diff[i] a[i] - a[i-1]差分数组的价值在于区间修改如果要对[l, r]统一加上x只需要diff[l] x; diff[r1] - x然后再求一次前缀和就能还原出修改后的数组。我在实际工程里用它处理过一段时间内给一批订单批量改价再统计汇总的场景把区间修改转成两个端点的标记最后一次性前缀求和得到每个元素被加了多少。这种思路在数据量大的时候能省掉大量循环。4. 前缀数组的短板静态是主场动态是软肋4.1 单点修改之后麻烦来了前缀数组最大的硬伤一旦原数组发生修改前缀数组就需要大范围更新。具体来说如果修改了a[k]的值那么所有包含a[k]的前缀和也就是pre[k1], pre[k2], ..., pre[n]全部要重新计算。一次修改的代价是O(n)。如果业务场景是查询很多、修改很少那前缀数组非常理想但如果修改和查询一样频繁每次都重建前缀数组总体复杂度又回到O(n*m)和不用它没什么区别。我之前处理过一个监控指标存储的需求每分钟上来一批数值查询端要看任意时间窗口的总量同时数据本身会有延迟修正也就是会修改已有位置的数值。这种情况下纯前缀数组就撑不住了每来一个修正都要更新后面的所有位置性能瓶颈非常明显。4.2 动态场景的替代从朴素更新到树状数组要支持单点修改和区间查询同时频繁发生有几种常见的进阶结构结构单点修改区间查询适用场景朴素数组O(1)O(n)查询少前缀数组O(n)O(1)修改极少树状数组Fenwick TreeO(log n)O(log n)动态且要求实现简单线段树O(log n)O(log n)动态且需要区间更新/复杂查询树状数组关键的设计是利用lowbit把一个位置的信息分散存储在若干管辖区间里让每次修改只需要向上更新O(log n)个节点每次查询只需要向下累加O(log n)个节点。它和前缀数组是同一个思想家族只是加上了动态维护能力。4.3 什么地方仍然该选前缀数组看到动态场景要换结构别急着否定前缀数组。很多实际场景里数据是只读的或者修改频率极低前缀数组就是最优解。比如数据分析里的累计报表统计每日新增用户数最后生成截至任意日期的总用户数这种数据一旦落库就不再变直接构建前缀数组之后无论多少查询都是O(1)。再比如离线算法题输入全部给定没有修改操作那前缀数组就是最简单的满分方案。我个人选型习惯是先问一个问题数据在查询过程中会不会变不会变用前缀数组会变但修改很少可以在修改时局部更新或定期重建修改很频繁再上树状数组或线段树。5. 前缀数组和树状数组从一份 n16 的序列说起5.1 同一个前缀思想两种维护方式为了说清楚区别我拿一份具体的序列来演示。设n 16数组下标从1到16我们要支持两个操作查询sum(11)求下标1到11的和。单点修改add(3, x)给下标3的值加上x。如果用前缀数组构建时维护一个长度n1的pre查询sum(11)就是直接取pre[11]O(1)。但一旦执行add(3, x)下标3的值变了那pre[3]到pre[16]全部要加上x一共14个位置要更新。如果用树状数组维护一个同样长度n1的树状数组bit先通过add操作把原数组每个位置的值构建进去for i in 1..n: tree.add(i, a[i])然后add(3, x)从下标3开始i lowbit(i)逐层向上更新。下标变化是 3 - 4 - 8 - 16一共4个位置。在n16的情况下是4次更新在更大的n下就是O(log n)次。sum(11)从下标11开始i - lowbit(i)逐层累加。下标变化是 11 - 10 - 8 - 0共3个位置返回的就是前11项之和。这就是树状数组的精髓单个元素的信息被折叠进一棵二进制索引树里查询和修改都只需要沿着二进制位的路径走而不是从头走到尾。5.2 树状数组的代码怎么落地树状数组核心就两个函数其他都是围绕它们转class FenwickTree: def __init__(self, n): self.n n self.bit [0] * (n 1) def add(self, idx, delta): # 单点修改更新 idx 及其所有祖先 while idx self.n: self.bit[idx] delta idx idx -idx # idx -idx 就是 lowbit def prefix_sum(self, idx): # 前缀和查询累加 idx 及其所有左兄弟 res 0 while idx 0: res self.bit[idx] idx - idx -idx return res def range_sum(self, l, r): return self.prefix_sum(r) - self.prefix_sum(l - 1)idx -idx取的是idx二进制最低位的1所代表的值也就是lowbit。不理解二进制也没关系记住它等于idx能被2整除的最多次数对应的2的幂即可。具体看n16的例子。查sum(11)idx 11, lowbit(11) 1, 累加 bit[11] idx 10, lowbit(10) 2, 累加 bit[10] idx 8, lowbit(8) 8, 累加 bit[8] idx 0, 停止总共访问3个节点。手动验证时bit的每个节点覆盖的区间长度恰好是它的lowbitbit[8]覆盖[1..8]bit[10]覆盖[9..10]bit[11]覆盖[11..11]。三段合起来正好是[1..11]一个不多一个不少。这种区间划分方式是理解树状数组的关键。5.3 两者取舍为什么不能无脑用其中一个前缀数组的优点是简单、常数极小、支持O(1)查询。缺点是修改代价高。树状数组的优点是把修改和查询都平衡到O(log n)缺点是代码稍复杂常数也比直接取前缀数组大。如果是一场比赛出题人确保没有修改、只有查询那写前缀数组拿满分不需要考虑树状数组。如果修改和查询都在10^5级别树状数组是首选因为O(n)的修改完全不可接受。如果还要支持区间加、区间乘之类的复合更新树状数组可以通过维护多个辅助树实现或者直接上线段树。从凡是前缀和的题都往树状数组上套不是一个好习惯。能用前缀数组解决的问题用树状数组是杀鸡用牛刀反过来强行用前缀数组处理动态问题则是拿冷兵器去防空。6. 实操中容易踩的坑与我的使用习惯6.1 建表时最常见的三类错误第一类是数组长度的边界搞错。很多人写pre [0] * n然后循环for i in range(1, n)最后查询pre[r] - pre[l-1]时下标越界或是结果少了一个元素。我建议直接统一成n1长度宁多一个哨兵位也不要让代码里出现if l 0这种特殊情况。第二类是修改操作之后忘记同步。在用前缀数组时如果中间做了一次单点修改很多人只改了原数组忘了改pre结果后续查询全部错误。这个问题排查起来特别隐蔽因为改完数据跑一遍错得毫无规律。我的做法是封装一个更新函数禁止在业务代码里直接改原数组。第三类是区间定义不一致。有人用闭区间[l, r]有人用左闭右开[l, r)在写前缀和查询时混用就会差一。我自己的规矩是代码里所有区间统一写成闭区间配合n1长度的pre查询用pre[r1] - pre[l]注释里标清楚闭区间三个字。注释真的能救命尤其是过两周自己回来看代码时。6.2 数值溢出要注意前缀和是把大量元素累加在一起如果原数组是int且数值范围较大前缀和很容易超过单元素的范围。在 C 里int很容易溢出要用long long。在 Python 里整数没有溢出问题但在数值特别大的时候性能会下降而且如果面向的是某些强类型语言比如用 Java 写 LeetCode也要注意用long。判断是否可能溢出的经验法则是看sum(nums)的数量级。所有元素都是正数且数据范围接近10^9、长度接近10^5那和就到10^14了int肯定不够用。直接无脑用64位类型别在这上面省。6.3 我的三个使用习惯第一凡是需要多次区间查询的场景我第一反应永远是先画一个修改频率 vs 查询频率的草图。查询占绝对多数直接前缀数组修改占比超过10%考虑树状数组。第二代码里把前缀数组的构建封装成一个函数比如build_prefix(arr)不直接写在主逻辑里。这样语义清晰也方便日后替换成树状数组或线段树的实现而不动查询代码。第三调试时我会打印出pre数组的值手工算几个小区间的和去比对。比对了两个案例没问题我才会继续往下写。看似多花了几十秒实际上省的是后面定位问题的一两个小时。前缀数组本身不难但它背后的预处理换性能思想以及它和树状数组之间的关系值得静下心理顺。把这层关系理清了后面再看线段树、看各种高级数据结构都会轻松很多。