前缀数组详解：从区间求和到O(1)查询的必备数据结构

讲个真实经历。去年做性能优化时，有个接口响应特别慢，点开日志一看，里面有个循环在反复计算某段时间范围内的订单总额，数据量一上来，单次查询就是几万次加法，接口直接被打爆。看了半天代码，我第一反应不是去缓存，而是想到了一句话：这种情况就该上前缀数组。后来我把那段逻辑换成前缀和预处理，整个查询从 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[r+1] - pre[l]即可。

从复杂度上看，预处理需要扫描一遍原数组，时间 O(n)，之后每次查询都只做一次减法，时间 O(1)。代价是多花了一份数组的内存空间。这是一种非常经典的“空间换时间”策略，也是很多高效数据结构共通的底层思想。它不炫技，但极其实用。

1.3 我要给它的定位：不是高级算法，而是基础组件

很多人有个误区，觉得前缀数组太简单，不值一提。但我的经验是，真正难缠的业务问题往往不是缺什么高级算法，而是把这种基础组件用错地方或者在关键时刻想不起来。前缀数组就像工具箱里的螺丝刀，看起来很普通，但你在拧螺丝的时候，手边有没有它，效率是完全不一样的。

在算法题里，它经常作为中间步骤出现：先构造前缀数组，再配合哈希表、二分查找、双指针去解决更复杂的子数组问题。在实际项目中，它适合处理那些数据相对静态、查询极其频繁的场景，比如报表系统的区间汇总。当然它也有局限，比如原数组频繁增删改时，维护前缀数组本身也要付出额外成本。这个取舍后面细说。

2. 前缀数组的构建与基础实现：索引约定是灵魂

2.1 标准构建流程与两种索引约定

构建前缀数组本身不复杂，但索引约定这个问题，我见过太多人在这里翻车。市面上存在两种常见写法，它们的区别只在于数组下标从哪里开始。

第一种是“长度语义”写法，也是最推荐的写法。定义pre[i]表示原数组前i个元素之和，所以pre[0]恒等于 0，pre[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, initial=0)) # 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，所以要自己处理：

vector<int> arr = {2, 4, 6, 8}; vector<int> 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[r+1] - 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[r+1]存的是从开头加到下标r的累计值，pre[l]存的是从开头加到下标l-1的累计值，两者相减，中间的公共部分抵消掉，剩下的正好是下标l到r这一段。这就是前缀思想最妙的地方：用两个“从头到某个位置”的已知结果，间接算出任意区间的结果。

实际业务中，比如你要统计“某个用户在某个时间段内总共消费了多少次、多少钱”，如果数据按时间顺序存好，那每次请求就是一个区间查询。把前缀数组提前算好，映射层直接返回减法结果，性能非常好。如果数据更新不是特别频繁，甚至可以考虑做一个定时重建的缓存，进一步降低计算成本。

3.2 配合哈希表解决“和为 K 的子数组”数量统计

这个场景在算法面试里出现频率极高，而且它把前缀数组从“区间查询工具”升级成了“数据统计工具”。问题描述一般是：给定数组，统计有多少个连续子数组的元素和刚好等于K。

暴力解法是双重循环枚举所有起点和终点，复杂度 O(n²)。而用前缀数组加哈希表，可以做到 O(n)。

核心逻辑要转一个弯：任意子数组[l, r]的和可以写成pre[r+1] - pre[l]。我们要找的是有多少对(l, r)满足pre[r+1] - pre[l] == K。移项一下就是pre[l] == pre[r+1] - K。也就是说，我们遍历每个位置当作右端点时，只需要知道在它之前出现过多少个“等于pre[r+1] - 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[r2+1][c2+1] - S[r1][c2+1] - S[r2+1][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] += v，diff[r+1] -= v。全部更新完成后，对差分数组做一次前缀和，就能还原出最终数组。

为什么这样做是对的？因为差分数组记录了相邻元素之间的变化量，区间内统一加值不改变内部相邻差值，只有区间起点和终点之后的位置会发生变化。把“区间修改”从 O(n) 降到了 O(2)，这是非常典型的一个优化思路。不过要注意，差分数组做的事情和前缀数组并不是同一类，两者经常搭配使用。理解它们的区别，比记住套路更重要。

3.5 前缀思想的进一步延伸：前缀积、异或前缀、前缀最值

很多人只知道前缀和，却没意识到“前缀”这个思想本身是通用的。只要是满足一定可结合性的运算，几乎都能做前缀预处理。比如前缀积，可以快速求某一段连续元素的乘积；异或前缀，可以快速求某一段异或结果，这在处理某些位运算题目时尤其好用；前缀最大值、前缀最小值，则能帮你快速回答“从开头到当前位置的最大值”这类问题。

但这里有一个关键区别必须强调：前缀和查询时用的是一次“减法”，也就是必须存在逆运算。前缀积做查询时用的是除法，前缀异或的逆运算恰好还是异或自己。所以前缀值的类型决定了查询公式。比如要查询区间[l, r]的异或值，只需要算xor_pre[r+1] ^ xor_pre[l]。理解了这点，你就不用死记硬背每个公式，而是知道“我存储的是什么，我用什么操作来还原”就够了。

4. 我在实操中踩过的坑：边界、溢出和性能取舍

4.1 一份常见错误速查表，建议直接收藏

我在面试同学和带着团队做代码评审时，总结了一份高频错误清单，全部都是真实发生过的案例。这里列成表格，方便你对照自查。

我特别想强调最后一条。用 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[r+1] - pre[l] + M) % M或者直接((pre[r+1] - pre[l]) % M + M) % M，避免负数出现。

第三，我习惯在进行任何一种前缀数组扩展时，先手工在纸上推一个小例子。比如用[1, 3, 5, 7]计算前缀和，然后手算几个区间，再用代码验证。整个过程可能只有五分钟，却能拦住绝大多数低级错误。这个习惯救过我太多次了，真的建议你也试试。

第四，在项目里用前缀数组时，别忘了它是在“牺牲内存换时间”。如果查询频率本身不高，比如一天只有几十次，那直接跑循环反而更简单，代码可读性也更高。优化追求的不是“用到极致”，而是“在合适的位置用合适的方法”。写代码写久了你会明白，可维护性往往比那几微秒更重要。

总的来说，前缀数组是我心中最值得熟练掌握的基础数据结构之一。它的原理不复杂，代码量也小，但它的思想可以延伸到太多场景：从一维区间求和到二维矩阵统计，从配合哈希表数子数组到和差分数组打组合拳，每一步都围绕“预计算 + 快速还原”这个核心。吃透它，你在很多算法题和业务性能问题面前，都会多一份底气。