1. 从比那名居的桃子说起前缀和到底在算什么第一次看到比那名居的桃子这个标题很多人会以为是什么游戏同人或者二次元周边项目。实际上这是一道非常经典的算法题核心考点就一个——前缀和。题目背景大致是这样的有一排桃子每颗桃子有甜度值需要频繁查询某个区间内桃子的甜度总和或者找出满足某种条件的连续区间。如果每次查询都老老实实从区间起点加到终点数据量一大就会超时而前缀和这个技巧能把区间求和从 O(n) 降到 O(1)。我最早接触前缀和是在做数组类题目的时候当时觉得不就是多开一个数组存累加值吗后来才发现这个思路的延展性极强——二维前缀和、差分数组、前缀异或和、前缀积甚至结合哈希表解决子数组求和问题都是从这个朴素想法长出来的。这篇文章我会围绕比那名居的桃子这道题把前缀和的原理、推导、代码实现、常见变体、踩坑经验完整讲一遍。不管你是刚学算法的新手还是想复习一下基础技巧的老手应该都能从中拿到点东西。先明确一下适用人群如果你已经能熟练写循环、知道数组下标从0开始那这篇文章完全能看懂如果你正在准备算法面试或者刷题前缀和是必须掌握的基础工具之一值得花时间吃透。下面我按为什么需要它→怎么推导→怎么写代码→怎么应对变体→怎么避坑的顺序展开。2. 暴力求和为什么会超时前缀和要解决的真实痛点2.1 一个具体的场景查询次数一多暴力就崩了假设桃子排成一排共 n 颗第 i 颗的甜度是 a[i]。现在有 m 次询问每次问第 L 颗到第 R 颗桃子的甜度总和是多少。最直接的做法是写一个循环def query(a, L, R): total 0 for i in range(L, R 1): total a[i] return total单次查询的复杂度是 O(n)m 次查询就是 O(n×m)。如果 n 和 m 都是 10^5 级别那就是 10^10 次运算现代计算机一秒大概能跑 10^8 次简单操作这个量级妥妥超时。这就是暴力求和的死穴每次查询都在重复计算之前已经算过的部分。你可以这样理解问第1到第5颗的总和你从第1颗加到第5颗下一次问第1到第6颗你又从第1颗重新加一遍。前面那5颗的累加结果明明没变却被白白浪费了。前缀和的核心思想就是——把从开头到当前位置的累加结果提前存下来用的时候直接相减。2.2 前缀和的定义用一个数组记住所有历史定义前缀和数组pre其中pre[i]表示前 i 个元素的和注意下标约定不同写法略有差异后面会专门讲。常见的一种定义是pre[0] 0前0个元素的和为0pre[i] pre[i-1] a[i-1]表示前 i 个元素的和这样定义之后区间 [L, R]假设用1-based描述即第L个到第R个的和就等于pre[R] - pre[L-1]。为什么因为pre[R]是前 R 个的和pre[L-1]是前 L-1 个的和两者相减正好把前 L-1 个元素抵消掉剩下的就是第 L 到第 R 个的和。这个推导看起来简单但它是整个前缀和体系的基石。我建议你在纸上画一条数轴把 pre 数组的每个值标出来然后自己推一遍相减的过程比死记公式管用得多。2.3 复杂度对比从 O(n×m) 到 O(nm)方案预处理单次查询m次查询总复杂度暴力求和无O(n)O(n×m)前缀和O(n)O(1)O(nm)预处理只需要遍历一遍数组花 O(n)之后每次查询两次数组访问加一次减法O(1)。当 m 很大时这个优化是数量级的。这也是为什么几乎所有涉及区间求和的题目第一反应都应该是前缀和。提示前缀和不是万能的。如果数组元素会被频繁修改比如单点更新那前缀和每次更新后都要重新预处理反而变慢。这种带修改的区间查询要用树状数组或线段树。前缀和的适用前提是数组静态不变只有查询。3. 手把手推导从定义到代码的完整链路3.1 下标约定0-based 和 1-based 的坑这是新手最容易翻车的地方。前缀和有两种常见写法混用就会出错。写法一pre 长度 n1pre[0]0pre[i] 表示前 i 个元素的和1-based 语义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-based闭区间的和 # 对应前 r1 个元素减去前 l 个元素 def query(l, r): return pre[r 1] - pre[l]写法二pre 长度 npre[i] 表示 a[0] 到 a[i] 的和含自身n len(a) pre [0] * n pre[0] a[0] for i in range(1, n): pre[i] pre[i - 1] a[i] def query(l, r): if l 0: return pre[r] return pre[r] - pre[l - 1]写法一多开一个位置但查询时不用特判 l0代码更干净我个人更推荐。写法二省一个空间但每次查询都要判断边界容易漏。关键是一套代码里只用一种约定别混着来。3.2 完整代码实现与逐行注释以比那名居的桃子这类区间求和题为例完整解法如下def solve(a, queries): n len(a) # 构建前缀和pre[i] 表示前 i 个桃子的甜度总和 pre [0] * (n 1) for i in range(1, n 1): pre[i] pre[i - 1] a[i - 1] res [] for L, R in queries: # 题目若给的是1-based下标直接用 pre[R] - pre[L-1] # 若给的是0-based下标用 pre[R1] - pre[L] res.append(pre[R] - pre[L - 1]) return res这段代码里pre[i] pre[i-1] a[i-1]是核心。注意a[i-1]这个下标因为 pre 是1-based语义而原数组是0-based所以要用 i-1 去取原数组的值。这个错位是初学者最常写错的地方我当年也是debug了半天才发现。3.3 用具体数字走一遍确认逻辑无误假设桃子甜度a [3, 1, 4, 1, 5]构建 prepre[0] 0pre[1] pre[0] a[0] 3pre[2] pre[1] a[1] 4pre[3] pre[2] a[2] 8pre[4] pre[3] a[3] 9pre[5] pre[4] a[4] 14查询第2到第4颗1-based的和即 a[1]a[2]a[3] 141 6。用公式pre[4] - pre[1] 9 - 3 6正确。查询第1到第5颗pre[5] - pre[0] 14 - 0 14也正确。手动走一遍的价值在于当你写代码出错时能快速定位是 pre 构建错了还是查询公式错了。我习惯在本地测试时先打印整个 pre 数组肉眼核对前几个值往往一眼就能看出问题。4. 前缀和的家族成员不止区间求和这一种玩法4.1 二维前缀和矩阵区域求和一维玩明白了二维就是自然的推广。给定一个矩阵多次查询某个子矩形的元素和。定义pre[i][j]表示从 (0,0) 到 (i-1,j-1) 这个矩形内所有元素的和同样用多开一行一列的写法。构建公式pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] a[i-1][j-1]查询左上角 (r1,c1) 到右下角 (r2,c2) 的子矩形和sum pre[r21][c21] - pre[r1][c21] - pre[r21][c1] pre[r1][c1]那个减两次加一次的容斥原理是二维前缀和的灵魂。我第一次看的时候也绕后来画了个矩形图把重叠部分标出来就明白了pre[i-1][j]和pre[i][j-1]都把pre[i-1][j-1]那块算了两遍所以要减掉一次。4.2 差分数组前缀和的逆运算如果题目变成多次对区间 [L,R] 的每个元素加上 v最后问整个数组变成什么样这时候用差分数组。定义diff[i] a[i] - a[i-1]那么对区间 [L,R] 加 v只需要diff[L] v和diff[R1] - v最后对 diff 求前缀和就还原出结果。差分和前缀和是一对互逆操作前缀和是累加差分是记录变化量。理解这一点很多区间修改的题目就能秒杀。比如比那名居的桃子如果加一个条件——每次操作给一段区间的桃子增加甜度最后统一查询——那就得用差分。4.3 前缀和 哈希表解决子数组求和问题这是前缀和最经典的进阶用法。题目找出数组中和为 k 的连续子数组个数。暴力枚举是 O(n²)用前缀和加哈希表能降到 O(n)。思路子数组 [i1, j] 的和等于pre[j] - pre[i]要它等于 k就是pre[j] - pre[i] k即pre[i] pre[j] - k。遍历 j 的时候看哈希表里有多少个pre[j] - k就说明有多少个子数组以 j 结尾且和为 k。def subarray_sum(nums, k): count 0 pre 0 seen {0: 1} # 前缀和为0出现1次空前缀 for num in nums: pre num if pre - k in seen: count seen[pre - k] seen[pre] seen.get(pre, 0) 1 return count注意seen {0: 1}这个初始化它代表空前缀的和为0。如果漏了它那些从数组开头就开始的子数组会被漏掉。这个细节我踩过坑当时怎么都对不上答案后来才发现是初始化的问题。4.4 前缀异或和把加法换成异或异或也有类似前缀和的性质因为异或满足x ^ x 0所以区间异或和[L,R] pre[R] ^ pre[L-1]。这个性质在找出异或和为某值的子数组这类题里非常好用配合哈希表或者字典树还能解决最大异或对问题。5. 实战中的坑与经验这些细节文档不会告诉你5.1 数据范围与溢出别让答案在最后一步崩掉前缀和最容易忽略的问题是数值溢出。如果数组元素是 int 范围n 又很大累加和可能超出 int 上限。比如 n10^5每个元素接近 10^9总和就是 10^14早就爆 int 了。Python 不用担心但 C/Java 里必须用 long long。我的习惯是只要涉及累加先估算最大可能和超过 2×10^9 就无脑上 long long。这个判断花不了几秒但能省掉一次 WA。5.2 下标越界R1 和 L-1 的边界处理用pre[R1] - pre[L]这种写法时如果 R 是数组最后一个下标R1 正好等于 pre 的长度不会越界因为 pre 多开了一位。但如果用pre[R] - pre[L-1]且 L0L-1 就是 -1Python 里会取到最后一个元素C 里直接越界。这就是为什么我推荐多开一位的写法——用空间换掉边界判断减少出错概率。5.3 前缀和不是万能钥匙什么时候不该用前面提过带修改的区间查询不适合前缀和。还有一种情况如果查询的是区间最大值/最小值前缀和也无能为力因为减法对 max/min 不成立max(a,b) - max(c,d)没有意义。这类问题要用稀疏表、线段树或单调队列。前缀和只对满足可减性的运算有效比如加法、异或但不适用于最大值、最小值、乘法除法有精度问题。5.4 调试技巧打印前缀和数组肉眼核对我调试前缀和代码的标准流程是先用一个 5 到 6 个元素的小数组手动算出 pre 数组然后打印程序里的 pre逐个对比。如果 pre 对了但答案错了那就是查询公式的问题如果 pre 就错了那就是构建逻辑的问题。这个二分定位法能省下大量时间。注意有些题目给的下标是 1-based有些是 0-based读题时一定要看清楚。我见过太多人代码逻辑全对就因为下标约定没对齐而 WA 的。6. 从这道题延伸出去前缀和思维的实际价值比那名居的桃子这道题本身不难但它背后的前缀和思维在真实工程里到处都是影子。比如统计系统里某段时间内的累计请求量日志分析里某个区间的事件计数财务系统里某段日期的流水汇总——本质上都是区间求和都能用前缀和把重复计算消掉。再往深了说前缀和体现的是一种**预处理换查询效率**的通用思路。类似的还有提前建索引加速数据库查询、缓存计算结果避免重复运算、预计算特征加速模型推理。这些工程手段和前缀和是同一个哲学——把贵的操作提前做一次之后用便宜的操作反复取用。我自己在做数据处理时经常先用一次遍历算出各种前缀统计量前缀和、前缀计数、前缀最值后面无论怎么切区间查询都是 O(1)。这个习惯让我在处理大规模数据时省了很多时间。所以别小看这道桃子题它训练的是你识别重复计算并消除它的能力这个能力比记住一个公式值钱得多。如果你想把前缀和练到条件反射我的建议是先把一维区间求和写熟再练二维矩阵求和然后做几道前缀和哈希表的子数组题最后试试差分数组。这四步走完前缀和这一块基本就通了。刷题的时候别只求 AC多想想这题为什么能用前缀和换成别的运算还成立吗想清楚这些下次遇到新题才能自己推出来。 
长河君 · 2026/10/20 3:22:54 · 阅读 1.2k 前缀和算法详解：从比那名居的桃子到区间求和优化
1. 从比那名居的桃子说起前缀和到底在算什么第一次看到比那名居的桃子这个标题很多人会以为是什么游戏同人或者二次元周边项目。实际上这是一道非常经典的算法题核心考点就一个——前缀和。题目背景大致是这样的有一排桃子每颗桃子有甜度值需要频繁查询某个区间内桃子的甜度总和或者找出满足某种条件的连续区间。如果每次查询都老老实实从区间起点加到终点数据量一大就会超时而前缀和这个技巧能把区间求和从 O(n) 降到 O(1)。我最早接触前缀和是在做数组类题目的时候当时觉得不就是多开一个数组存累加值吗后来才发现这个思路的延展性极强——二维前缀和、差分数组、前缀异或和、前缀积甚至结合哈希表解决子数组求和问题都是从这个朴素想法长出来的。这篇文章我会围绕比那名居的桃子这道题把前缀和的原理、推导、代码实现、常见变体、踩坑经验完整讲一遍。不管你是刚学算法的新手还是想复习一下基础技巧的老手应该都能从中拿到点东西。先明确一下适用人群如果你已经能熟练写循环、知道数组下标从0开始那这篇文章完全能看懂如果你正在准备算法面试或者刷题前缀和是必须掌握的基础工具之一值得花时间吃透。下面我按为什么需要它→怎么推导→怎么写代码→怎么应对变体→怎么避坑的顺序展开。2. 暴力求和为什么会超时前缀和要解决的真实痛点2.1 一个具体的场景查询次数一多暴力就崩了假设桃子排成一排共 n 颗第 i 颗的甜度是 a[i]。现在有 m 次询问每次问第 L 颗到第 R 颗桃子的甜度总和是多少。最直接的做法是写一个循环def query(a, L, R): total 0 for i in range(L, R 1): total a[i] return total单次查询的复杂度是 O(n)m 次查询就是 O(n×m)。如果 n 和 m 都是 10^5 级别那就是 10^10 次运算现代计算机一秒大概能跑 10^8 次简单操作这个量级妥妥超时。这就是暴力求和的死穴每次查询都在重复计算之前已经算过的部分。你可以这样理解问第1到第5颗的总和你从第1颗加到第5颗下一次问第1到第6颗你又从第1颗重新加一遍。前面那5颗的累加结果明明没变却被白白浪费了。前缀和的核心思想就是——把从开头到当前位置的累加结果提前存下来用的时候直接相减。2.2 前缀和的定义用一个数组记住所有历史定义前缀和数组pre其中pre[i]表示前 i 个元素的和注意下标约定不同写法略有差异后面会专门讲。常见的一种定义是pre[0] 0前0个元素的和为0pre[i] pre[i-1] a[i-1]表示前 i 个元素的和这样定义之后区间 [L, R]假设用1-based描述即第L个到第R个的和就等于pre[R] - pre[L-1]。为什么因为pre[R]是前 R 个的和pre[L-1]是前 L-1 个的和两者相减正好把前 L-1 个元素抵消掉剩下的就是第 L 到第 R 个的和。这个推导看起来简单但它是整个前缀和体系的基石。我建议你在纸上画一条数轴把 pre 数组的每个值标出来然后自己推一遍相减的过程比死记公式管用得多。2.3 复杂度对比从 O(n×m) 到 O(nm)方案预处理单次查询m次查询总复杂度暴力求和无O(n)O(n×m)前缀和O(n)O(1)O(nm)预处理只需要遍历一遍数组花 O(n)之后每次查询两次数组访问加一次减法O(1)。当 m 很大时这个优化是数量级的。这也是为什么几乎所有涉及区间求和的题目第一反应都应该是前缀和。提示前缀和不是万能的。如果数组元素会被频繁修改比如单点更新那前缀和每次更新后都要重新预处理反而变慢。这种带修改的区间查询要用树状数组或线段树。前缀和的适用前提是数组静态不变只有查询。3. 手把手推导从定义到代码的完整链路3.1 下标约定0-based 和 1-based 的坑这是新手最容易翻车的地方。前缀和有两种常见写法混用就会出错。写法一pre 长度 n1pre[0]0pre[i] 表示前 i 个元素的和1-based 语义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-based闭区间的和 # 对应前 r1 个元素减去前 l 个元素 def query(l, r): return pre[r 1] - pre[l]写法二pre 长度 npre[i] 表示 a[0] 到 a[i] 的和含自身n len(a) pre [0] * n pre[0] a[0] for i in range(1, n): pre[i] pre[i - 1] a[i] def query(l, r): if l 0: return pre[r] return pre[r] - pre[l - 1]写法一多开一个位置但查询时不用特判 l0代码更干净我个人更推荐。写法二省一个空间但每次查询都要判断边界容易漏。关键是一套代码里只用一种约定别混着来。3.2 完整代码实现与逐行注释以比那名居的桃子这类区间求和题为例完整解法如下def solve(a, queries): n len(a) # 构建前缀和pre[i] 表示前 i 个桃子的甜度总和 pre [0] * (n 1) for i in range(1, n 1): pre[i] pre[i - 1] a[i - 1] res [] for L, R in queries: # 题目若给的是1-based下标直接用 pre[R] - pre[L-1] # 若给的是0-based下标用 pre[R1] - pre[L] res.append(pre[R] - pre[L - 1]) return res这段代码里pre[i] pre[i-1] a[i-1]是核心。注意a[i-1]这个下标因为 pre 是1-based语义而原数组是0-based所以要用 i-1 去取原数组的值。这个错位是初学者最常写错的地方我当年也是debug了半天才发现。3.3 用具体数字走一遍确认逻辑无误假设桃子甜度a [3, 1, 4, 1, 5]构建 prepre[0] 0pre[1] pre[0] a[0] 3pre[2] pre[1] a[1] 4pre[3] pre[2] a[2] 8pre[4] pre[3] a[3] 9pre[5] pre[4] a[4] 14查询第2到第4颗1-based的和即 a[1]a[2]a[3] 141 6。用公式pre[4] - pre[1] 9 - 3 6正确。查询第1到第5颗pre[5] - pre[0] 14 - 0 14也正确。手动走一遍的价值在于当你写代码出错时能快速定位是 pre 构建错了还是查询公式错了。我习惯在本地测试时先打印整个 pre 数组肉眼核对前几个值往往一眼就能看出问题。4. 前缀和的家族成员不止区间求和这一种玩法4.1 二维前缀和矩阵区域求和一维玩明白了二维就是自然的推广。给定一个矩阵多次查询某个子矩形的元素和。定义pre[i][j]表示从 (0,0) 到 (i-1,j-1) 这个矩形内所有元素的和同样用多开一行一列的写法。构建公式pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] a[i-1][j-1]查询左上角 (r1,c1) 到右下角 (r2,c2) 的子矩形和sum pre[r21][c21] - pre[r1][c21] - pre[r21][c1] pre[r1][c1]那个减两次加一次的容斥原理是二维前缀和的灵魂。我第一次看的时候也绕后来画了个矩形图把重叠部分标出来就明白了pre[i-1][j]和pre[i][j-1]都把pre[i-1][j-1]那块算了两遍所以要减掉一次。4.2 差分数组前缀和的逆运算如果题目变成多次对区间 [L,R] 的每个元素加上 v最后问整个数组变成什么样这时候用差分数组。定义diff[i] a[i] - a[i-1]那么对区间 [L,R] 加 v只需要diff[L] v和diff[R1] - v最后对 diff 求前缀和就还原出结果。差分和前缀和是一对互逆操作前缀和是累加差分是记录变化量。理解这一点很多区间修改的题目就能秒杀。比如比那名居的桃子如果加一个条件——每次操作给一段区间的桃子增加甜度最后统一查询——那就得用差分。4.3 前缀和 哈希表解决子数组求和问题这是前缀和最经典的进阶用法。题目找出数组中和为 k 的连续子数组个数。暴力枚举是 O(n²)用前缀和加哈希表能降到 O(n)。思路子数组 [i1, j] 的和等于pre[j] - pre[i]要它等于 k就是pre[j] - pre[i] k即pre[i] pre[j] - k。遍历 j 的时候看哈希表里有多少个pre[j] - k就说明有多少个子数组以 j 结尾且和为 k。def subarray_sum(nums, k): count 0 pre 0 seen {0: 1} # 前缀和为0出现1次空前缀 for num in nums: pre num if pre - k in seen: count seen[pre - k] seen[pre] seen.get(pre, 0) 1 return count注意seen {0: 1}这个初始化它代表空前缀的和为0。如果漏了它那些从数组开头就开始的子数组会被漏掉。这个细节我踩过坑当时怎么都对不上答案后来才发现是初始化的问题。4.4 前缀异或和把加法换成异或异或也有类似前缀和的性质因为异或满足x ^ x 0所以区间异或和[L,R] pre[R] ^ pre[L-1]。这个性质在找出异或和为某值的子数组这类题里非常好用配合哈希表或者字典树还能解决最大异或对问题。5. 实战中的坑与经验这些细节文档不会告诉你5.1 数据范围与溢出别让答案在最后一步崩掉前缀和最容易忽略的问题是数值溢出。如果数组元素是 int 范围n 又很大累加和可能超出 int 上限。比如 n10^5每个元素接近 10^9总和就是 10^14早就爆 int 了。Python 不用担心但 C/Java 里必须用 long long。我的习惯是只要涉及累加先估算最大可能和超过 2×10^9 就无脑上 long long。这个判断花不了几秒但能省掉一次 WA。5.2 下标越界R1 和 L-1 的边界处理用pre[R1] - pre[L]这种写法时如果 R 是数组最后一个下标R1 正好等于 pre 的长度不会越界因为 pre 多开了一位。但如果用pre[R] - pre[L-1]且 L0L-1 就是 -1Python 里会取到最后一个元素C 里直接越界。这就是为什么我推荐多开一位的写法——用空间换掉边界判断减少出错概率。5.3 前缀和不是万能钥匙什么时候不该用前面提过带修改的区间查询不适合前缀和。还有一种情况如果查询的是区间最大值/最小值前缀和也无能为力因为减法对 max/min 不成立max(a,b) - max(c,d)没有意义。这类问题要用稀疏表、线段树或单调队列。前缀和只对满足可减性的运算有效比如加法、异或但不适用于最大值、最小值、乘法除法有精度问题。5.4 调试技巧打印前缀和数组肉眼核对我调试前缀和代码的标准流程是先用一个 5 到 6 个元素的小数组手动算出 pre 数组然后打印程序里的 pre逐个对比。如果 pre 对了但答案错了那就是查询公式的问题如果 pre 就错了那就是构建逻辑的问题。这个二分定位法能省下大量时间。注意有些题目给的下标是 1-based有些是 0-based读题时一定要看清楚。我见过太多人代码逻辑全对就因为下标约定没对齐而 WA 的。6. 从这道题延伸出去前缀和思维的实际价值比那名居的桃子这道题本身不难但它背后的前缀和思维在真实工程里到处都是影子。比如统计系统里某段时间内的累计请求量日志分析里某个区间的事件计数财务系统里某段日期的流水汇总——本质上都是区间求和都能用前缀和把重复计算消掉。再往深了说前缀和体现的是一种**预处理换查询效率**的通用思路。类似的还有提前建索引加速数据库查询、缓存计算结果避免重复运算、预计算特征加速模型推理。这些工程手段和前缀和是同一个哲学——把贵的操作提前做一次之后用便宜的操作反复取用。我自己在做数据处理时经常先用一次遍历算出各种前缀统计量前缀和、前缀计数、前缀最值后面无论怎么切区间查询都是 O(1)。这个习惯让我在处理大规模数据时省了很多时间。所以别小看这道桃子题它训练的是你识别重复计算并消除它的能力这个能力比记住一个公式值钱得多。如果你想把前缀和练到条件反射我的建议是先把一维区间求和写熟再练二维矩阵求和然后做几道前缀和哈希表的子数组题最后试试差分数组。这四步走完前缀和这一块基本就通了。刷题的时候别只求 AC多想想这题为什么能用前缀和换成别的运算还成立吗想清楚这些下次遇到新题才能自己推出来。