讲个真实经历。去年做性能优化时有个接口响应特别慢点开日志一看里面有个循环在反复计算某段时间范围内的订单总额数据量一上来单次查询就是几万次加法接口直接被打爆。看了半天代码我第一反应不是去缓存而是想到了一句话这种情况就该上前缀数组。后来我把那段逻辑换成前缀和预处理整个查询从 O(n) 降到了 O(1)接口时延从原来的一百多毫秒降到了个位数。今天就把这个我几乎天天用的数据结构从头到尾聊透名字就叫前缀数组也叫前缀和数组。先说说它解决什么问题。如果你有一个数组需要反复询问某一段区间里的总和、乘积、异或值最笨的做法是每次现算数据小没事数据大了就是灾难。前缀数组的思想特别朴素提前把所有“从开头到某个位置”的结果算好存起来查询区间时用两个预计算值做个减法就行。适合三类人一是在准备算法面试的前缀数组是高频考点二是打竞赛的它是基础工具三是写业务代码的凡是涉及频繁区间统计的场景它都能帮你省下大把时间。下面我用一个记账本的类比把原理讲清楚。1. 从区间求和的痛点说起前缀数组到底解决了什么问题1.1 最直观的暴力解法与它的瓶颈假设你在管理一个门店的每日销售额数组arr存了某个月每天的营业额现在要反复询问“从第 3 天到第 7 天一共赚了多少”。新手时期我写这种代码第一反应都是直接循环def range_sum(arr, l, r): total 0 for i in range(l, r 1): total arr[i] return total这段代码逻辑没错但它的时间消耗和区间长度成正比。如果一个月 30 天一次查询最多做 30 次加法感觉不到什么。可如果数组长度是十万而且有十万次查询呢十万乘十万那就是百亿次操作再快的机器也扛不住。我见过不少线上服务就是这么被拖垮的查的字段越多、区间越大慢得越明显。这里的关键问题在于每次查询都重复计算了大量已经算过的中间结果。第 3 天到第 7 天的和和第 3 天到第 8 天的和明明共享了前面 5 天的数据暴力循环却把它们当成完全独立的计算白白浪费了算力。这种重复劳动在工程上叫冗余计算在算法里就叫“没有利用重叠子结构”。1.2 前缀数组的核心思想空间换时间的预计算前缀数组的思路特别像记账。你想想如果要求你快速回答“本月 5 号到 15 号的总支出是多少”你不会傻到把每天的账本翻出来逐行相加。聪明做法是维护一张表记录“从 1 号到任意一天为止的累计支出”比如记下“到 5 号累计花了 3000 元”“到 15 号累计花了 8000 元”。那么 5 号到 15 号的支出就是 8000 减去 3000等于 5000瞬间得到答案。前缀数组就是这个思路的代码化表达。具体来说对长度为n的数组arr我们构造一个新的数组pre其中pre[i]表示原数组前i个元素也就是下标 0 到 i-1的总和习惯上让pre[0] 0。构造完pre之后要查询下标l到r含两端的区间和直接算pre[r1] - pre[l]即可。从复杂度上看预处理需要扫描一遍原数组时间 O(n)之后每次查询都只做一次减法时间 O(1)。代价是多花了一份数组的内存空间。这是一种非常经典的“空间换时间”策略也是很多高效数据结构共通的底层思想。它不炫技但极其实用。1.3 我要给它的定位不是高级算法而是基础组件很多人有个误区觉得前缀数组太简单不值一提。但我的经验是真正难缠的业务问题往往不是缺什么高级算法而是把这种基础组件用错地方或者在关键时刻想不起来。前缀数组就像工具箱里的螺丝刀看起来很普通但你在拧螺丝的时候手边有没有它效率是完全不一样的。在算法题里它经常作为中间步骤出现先构造前缀数组再配合哈希表、二分查找、双指针去解决更复杂的子数组问题。在实际项目中它适合处理那些数据相对静态、查询极其频繁的场景比如报表系统的区间汇总。当然它也有局限比如原数组频繁增删改时维护前缀数组本身也要付出额外成本。这个取舍后面细说。2. 前缀数组的构建与基础实现索引约定是灵魂2.1 标准构建流程与两种索引约定构建前缀数组本身不复杂但索引约定这个问题我见过太多人在这里翻车。市面上存在两种常见写法它们的区别只在于数组下标从哪里开始。第一种是“长度语义”写法也是最推荐的写法。定义pre[i]表示原数组前i个元素之和所以pre[0]恒等于 0pre[1]等于arr[0]pre[n]等于整个数组之和。这样构造出来的pre长度是n 1。每次构建时def build_prefix(arr): n len(arr) pre [0] * (n 1) for i in range(1, n 1): pre[i] pre[i - 1] arr[i - 1] return pre第二种是“下标语义”写法定义pre[i]表示原数组从 0 到i的元素之和pre长度等于n。这种写法在某些语言里看起来更直观但查询区间时要写成pre[r] - (pre[l-1] if l 0 else 0)边界情况特别容易忘记处理。我个人的建议非常明确统一使用第一种写法。虽然多开一个位置但它让“前 i 个元素”这个语义清晰无歧义查询时无论什么区间都只需要固定的公式不需要判断l是否等于 0。这个习惯一旦养成几乎不会写错边界。2.2 三种主流语言的实现对比用 Python 写最舒服因为列表切片和自带函数让整个人感觉很清爽。基础版本就是我上面那段代码。如果你想压缩一点可以用itertools.accumulate它会直接生成累计和序列from itertools import accumulate arr [2, 4, 6, 8] pre list(accumulate(arr, initial0)) # pre [0, 2, 6, 12, 20]Java 版本更啰嗦一点但也非常直观public int[] buildPrefix(int[] arr) { int n arr.length; int[] pre new int[n 1]; for (int i 1; i n; i) { pre[i] pre[i - 1] arr[i - 1]; } return pre; }C 用 STL 的partial_sum注意默认不含初始 0所以要自己处理vectorint arr {2, 4, 6, 8}; vectorint pre(arr.size() 1, 0); for (int i 1; i arr.size(); i) { pre[i] pre[i - 1] arr[i - 1]; }不管用什么语言核心就一句话当前值等于前一个累计值加上原数组当前元素。这份代码要写到条件反射闭着眼都能敲出来因为后面所有高级玩法都是在这基础上叠加。2.3 关于索引和边界最常见的翻车点大盘点先说第一个坑构造长度搞错。普通数组长度是n前缀数组长度必须是n 1。如果你开了n的长度又想保留pre[0] 0那最后一个位置的累计和就存不下了查询最大区间时会直接数组越界。第二个坑原数组下标与前缀数组下标的换算。给一个原数组下标i它在pre里面对应的累计和位置是i 1。很多人写循环时顺着从 0 开始遍历结果pre[i]存的是前面几个数的和整个就全错位了。解决办法是构建时让循环变量代表“已经累加了几个数”而不是“当前数的下标”。第三个坑查询区间“含端”还是“不含端”。不同题目描述不一样有的是左闭右开[l, r)有的是闭区间[l, r]。如果题目给的是原数组下标闭区间用pre[r1] - pre[l]左闭右开用pre[r] - pre[l]。我建议在代码注释里写明区间定义防止自己下次看的时候犯迷糊。3. 前缀数组的经典场景与扩展玩法3.1 区间和查询从 O(n) 到 O(1)这是最基础也最经典的应用。你有一个数组接下来有大量查询每个查询给一对下标要求返回这段的和。用前缀数组的话查询代码就一句话def range_sum(pre, l, r): # 闭区间 [l, r] return pre[r 1] - pre[l]这里我多说一句“为什么是减法”。pre[r1]存的是从开头加到下标r的累计值pre[l]存的是从开头加到下标l-1的累计值两者相减中间的公共部分抵消掉剩下的正好是下标l到r这一段。这就是前缀思想最妙的地方用两个“从头到某个位置”的已知结果间接算出任意区间的结果。实际业务中比如你要统计“某个用户在某个时间段内总共消费了多少次、多少钱”如果数据按时间顺序存好那每次请求就是一个区间查询。把前缀数组提前算好映射层直接返回减法结果性能非常好。如果数据更新不是特别频繁甚至可以考虑做一个定时重建的缓存进一步降低计算成本。3.2 配合哈希表解决“和为 K 的子数组”数量统计这个场景在算法面试里出现频率极高而且它把前缀数组从“区间查询工具”升级成了“数据统计工具”。问题描述一般是给定数组统计有多少个连续子数组的元素和刚好等于K。暴力解法是双重循环枚举所有起点和终点复杂度 O(n²)。而用前缀数组加哈希表可以做到 O(n)。核心逻辑要转一个弯任意子数组[l, r]的和可以写成pre[r1] - pre[l]。我们要找的是有多少对(l, r)满足pre[r1] - pre[l] K。移项一下就是pre[l] pre[r1] - K。也就是说我们遍历每个位置当作右端点时只需要知道在它之前出现过多少个“等于pre[r1] - K”的前缀值。def subarray_sum_equal_k(arr, K): from collections import defaultdict pre 0 count 0 freq defaultdict(int) freq[0] 1 # 空区间的前缀和为0 for x in arr: pre x count freq[pre - K] freq[pre] 1 return count这里注意freq[0] 1这一行它表示“一个元素都没取的时候前缀和是 0”。考虑K 5且数组开头就是 5 的情况如果没有初始这个 1你会漏算第一个元素单独成段的情况。这也是初始化最容易遗漏的细节。3.3 二维前缀和解决矩阵区域求和问题前缀数组从一维扩展到二维就成了二维前缀和专门用来快速求矩阵中某个子矩形的元素总和。它的构建思路是容斥原理非常巧妙。设二维前缀数组S[i][j]表示从矩阵左上角(0,0)到(i-1,j-1)这个矩形区域的总和。递推公式为S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] arr[i-1][j-1]为什么要减去S[i-1][j-1]因为S[i-1][j]和S[i][j-1]都各自包含了左上角那块重叠区域加两次就重复了必须减去一次。这个逻辑就像你在统计两个重叠的面积时不能简单把两个面积相加得扣掉重叠部分。查询时如果想求左上角(r1, c1)到右下角(r2, c2)的矩形和公式是result S[r21][c21] - S[r1][c21] - S[r21][c1] S[r1][c1]同样的容斥原理加回被重复减掉的小块。实际使用时我建议把二维前缀数组的尺寸在原矩阵基础上每条边多扩一格全部置 0这样可以避免在处理第一行、第一列时写一堆条件判断代码会干净很多。这种“边界补零”的初始化手法在一维前缀数组里用pre[0]0也是一回事。3.4 和差分数组配合高效处理区间批量更新前缀数组还有个好搭档叫差分数组。如果说前缀数组解决的是“多次查询数据不变”的问题差分数组解决的则是“多次更新某段区间最后再统一查询”的问题。差分数组diff的定义也很简单diff[i] arr[i] - arr[i-1]其中arr[0]的差分就是它本身。如果要对原数组的[l, r]区间统一加上一个值v不需要真的遍历原数组去更新只需要在差分数组上做两次操作diff[l] vdiff[r1] - v。全部更新完成后对差分数组做一次前缀和就能还原出最终数组。为什么这样做是对的因为差分数组记录了相邻元素之间的变化量区间内统一加值不改变内部相邻差值只有区间起点和终点之后的位置会发生变化。把“区间修改”从 O(n) 降到了 O(2)这是非常典型的一个优化思路。不过要注意差分数组做的事情和前缀数组并不是同一类两者经常搭配使用。理解它们的区别比记住套路更重要。3.5 前缀思想的进一步延伸前缀积、异或前缀、前缀最值很多人只知道前缀和却没意识到“前缀”这个思想本身是通用的。只要是满足一定可结合性的运算几乎都能做前缀预处理。比如前缀积可以快速求某一段连续元素的乘积异或前缀可以快速求某一段异或结果这在处理某些位运算题目时尤其好用前缀最大值、前缀最小值则能帮你快速回答“从开头到当前位置的最大值”这类问题。但这里有一个关键区别必须强调前缀和查询时用的是一次“减法”也就是必须存在逆运算。前缀积做查询时用的是除法前缀异或的逆运算恰好还是异或自己。所以前缀值的类型决定了查询公式。比如要查询区间[l, r]的异或值只需要算xor_pre[r1] ^ xor_pre[l]。理解了这点你就不用死记硬背每个公式而是知道“我存储的是什么我用什么操作来还原”就够了。4. 我在实操中踩过的坑边界、溢出和性能取舍4.1 一份常见错误速查表建议直接收藏我在面试同学和带着团队做代码评审时总结了一份高频错误清单全部都是真实发生过的案例。这里列成表格方便你对照自查。错误类型典型表现根因解决方案前缀数组长度算错查询pre[n]越界忘记pre长度应为n1构造时统一[0] * (n 1)查询区间公式写错结果总是差一个边界值混淆闭区间和左闭右开在注释里写明查询前算一遍小样例多维前缀行首处理冗余第一行第一列结果不对没有预留全 0 边界二维前缀扩展一圈再处理更新场景误用前缀和数据频繁修改查询结果过期忽略了前缀数组静态性数据变动频繁时改用树状数组或分块大数溢出计算出负数或错误大数pre累加超出语言整数范围使用大整数类型或对模运算版本做处理我特别想强调最后一条。用 Python 写的时候由于有无限大整数一般不太会有溢出问题但用 Java、C 时前缀和的值很容易超出int范围。比如数组元素平均 10 万长度 10 万总和就是 10 的 10 次方已经超过 32 位整数的上限了。所以我一般直接用long或int64存前缀数组避免线上突然炸出个溢出 bug。4.2 复杂度与内存的权衡什么时候该用它什么时候该换方案前缀数组的优势我已经讲了不少但它不是万能的。如果把数据结构比作工具它更像一把专门拧固定螺丝的扳手而不是万能螺丝刀。我梳理一下适用边界能帮你减少很多不必要的麻烦。适合用前缀数组的场景有三个特征数据基本不变、查询极其频繁、区间操作可结合。比如报表统计、离线数据处理、静态榜单查询。不适合用的场景也很明显原数组元素频繁被修改因为每次修改都需要更新pre中所有受影响的位置最坏情况下得从头重算反而比暴力循环还慢还有数据规模极大比如上亿条内存吃紧时前缀数组额外翻倍的空间就可能成为瓶颈这时考虑线段树、树状数组或者干脆用稀疏表、分块算法。另外还有一个容易被忽略的点就是前缀数组只解决“查询”问题不解决“修改”问题。如果你看到题目里既有区间查询又有单点修改并且数量级都很大那就不是前缀数组的管辖范围应该转向树状数组或者线段树。选择算法前先问自己一句数据会不会变会变到什么频率想清楚这个方向就不会跑偏。4.3 几条实战经验用多了才知道的细节最后再分享几个我实际用下来的感受和技巧。第一初始化pre[0] 0这个习惯看似多余实际在大量场景中省去了特判。尤其是在配合哈希表统计子数组时这个 0 作为“空区间”的基准值会让边界处理变得极其干净。哪怕你用的是下标从 1 开始存储原数组也建议保留一个 0 位置。第二遇到模运算的题目前缀数组同样适用因为模运算对加减法是封闭的。只需要在累加时每次取模查询时对减法结果再做一次“补模”也就是加一个模数再取模保证结果非负。例如模数是M查询公式变成(pre[r1] - pre[l] M) % M或者直接((pre[r1] - pre[l]) % M M) % M避免负数出现。第三我习惯在进行任何一种前缀数组扩展时先手工在纸上推一个小例子。比如用[1, 3, 5, 7]计算前缀和然后手算几个区间再用代码验证。整个过程可能只有五分钟却能拦住绝大多数低级错误。这个习惯救过我太多次了真的建议你也试试。第四在项目里用前缀数组时别忘了它是在“牺牲内存换时间”。如果查询频率本身不高比如一天只有几十次那直接跑循环反而更简单代码可读性也更高。优化追求的不是“用到极致”而是“在合适的位置用合适的方法”。写代码写久了你会明白可维护性往往比那几微秒更重要。总的来说前缀数组是我心中最值得熟练掌握的基础数据结构之一。它的原理不复杂代码量也小但它的思想可以延伸到太多场景从一维区间求和到二维矩阵统计从配合哈希表数子数组到和差分数组打组合拳每一步都围绕“预计算 快速还原”这个核心。吃透它你在很多算法题和业务性能问题面前都会多一份底气。