提到区间查询、子数组统计这类问题很多算法题解里都会带一笔“可以用前缀和优化”但到底为什么能优化、优化在哪一步不少人其实是一知半解的。我自己刚开始刷题那阵子也这样——看答案觉得前缀和特别巧妙真到自己写的时候又总是差那么临门一脚要么边界算错要么空间开得莫名其妙。这篇文章就把我近两年实际用前缀和的经验从头到尾捋一遍从一维到二维从求和到异或再到差分把所有真正高频的用法和踩过的坑一次说清楚。1. 为什么所有区间求和问题都可以从这里开始先聊个最基本的场景你手里有一个长度为 n 的数组要频繁回答“从第 l 个元素到第 r 个元素加起来是多少”。最直接的办法是每次遍历一遍从 l 加到 r时间复杂度 O(n)。如果只查一次这完全没问题可一旦查询次数达到 m 次总复杂度就变成 O(m·n)。当 n 和 m 都是 10^5 级别的数据量这个复杂度直接就把程序拖垮了。前缀和的核心思路是预处理。在正式回答任何问题之前先把数组从头到尾扫一遍生成一个前缀和数组之后每次查询都只看这个预处理后的结果把单次查询的时间压到 O(1)。打个比方你是一家公司的行政三天两头有人问你“1号到30号这几个人的工龄加起来多少年”。笨办法是每次拿到名单逐个翻档案聪明办法是入职那天就把工龄从第一个人开始逐年累加记成一张表。以后不管问哪一段拿表上两个数字相减就完了——你要查 9 号到 17 号就用“到 17 号为止的累计值”减去“到 8 号为止的累计值”。本质上是把“重复的加法”提前做完把查询变成减法这就是整个算法最核心的朴素思想。从另一个角度理解前缀和的价值是重塑了信息的组织方式。原数组回答的是“某个位置是什么”前缀和数组回答的是“从起点到某个位置的整体状态是什么”。数据结构上有个通用原则——当你需要频繁回答某个固定模式的查询时就应该提前把那个模式的答案尽可能多地算好。前缀和就是这个原则在区间求和上的具体体现。所以只要你的问题能转化为“区间内某种可累加信息的统计”前缀和基本就是第一梯队该考虑的方案。这也是为什么它总和差分数组、树状数组、线段树并列在“区间问题基础工具集”里。接下来从最标准的一维前缀和说起把原理和代码一次盘清楚。2. 一维前缀和从暴力到 O(1) 查询的完整推导2.1 数组定义与递推公式的由来假设原始数组为 a下标从 1 开始这是 C/C 竞赛和很多算法模板里默认的习惯Python 里我通常也人为在开头补一个 0让逻辑统一。前缀和数组 pre 的定义是pre[0] 0pre[i] a[1] a[2] ... a[i]i 从 1 到 n构造过程是一个标准的递推pre[i] pre[i-1] a[i]这一步的时间复杂度是 O(n)空间复杂度是 O(n)一次性预处理之后任意区间 [l, r] 的和用公式sum(l, r) pre[r] - pre[l-1]注意这里的 l-1很多人第一次就是在这里写错。为什么不是 pre[r] - pre[l]因为 pre[l] 里已经包含了 a[l] 本身减掉的话就把左端点弄丢了。减法之前要看清楚“我到底想保留哪些元素”——保留从 l 到 r那就要减掉 1 到 l-1 的累计所以下标是 l-1。这个细节我至少见过十几个初学者反复踩每次调试才恍然大悟。如果你习惯用 0 下标这个公式一样成立只是写法变成 pre[r1] - pre[l]因为此时 pre[k] 表示前 k 个元素之和a[0] 到 a[k-1]。两种都行但一定要选一种并坚持到底最怕一会儿用 1 下标一会儿用 0 下标查错查到怀疑人生。2.2 代码实现与复杂度分析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 def range_sum(pre, l, r): # 输入 l, r 是原数组的 0 下标闭区间 return pre[r1] - pre[l]如果换成 C核心逻辑完全一样只是下标和数组类型需要留意vectorlong long pre(n 1, 0); for (int i 1; i n; i) { pre[i] pre[i-1] nums[i-1]; } // 查询 [l, r]0 下标 long long ans pre[r1] - pre[l];这里一个很容易被忽略的工程细节是数据类型。如果原始数组元素范围很大区间又很长累加结果可能超过 int 范围。我第一次在项目里写前缀和时有一个数组存的是用户行为计数单个值看起来不大可几万次累加后直接溢出查了半天才发现是 int 不够用。竞赛模板里通常直接上 long long实际工程里建议先估算一下上界别在这上面冒险。构造 O(n) 查询 O(1) 的组合已经是这个场景下的理论最优了。每次查询的常数极小就是一次数组访问和一次减法这也正是它能PK掉线段树的原因——线段树虽然也能 O(log n) 查区间和但常数和实现复杂度都高不少。如果你的需求只是静态数组的区间求和没有任何修改操作前缀和是最优先的选择没有之一。2.3 一个重要教训前缀和数组的起点为什么必须是 0之前提到预处理时人为地让 pre[0] 0很多新手觉得这只是规避边界的小技巧其实它是保证算法正确性的关键。如果没有这个“空集之和为 0”的定义当查询区间从第一个元素开始时l 0pre[l-1] 就变成了 pre[-1]直接下标越界。有了 pre[0] 0计算 sum(0, r) 时就是 pre[r1] - 0顺理成章。从数学上看pre[0] 0 对应的是“前 0 个元素的和”也就是空集的累加结果必须等于加法单位元 0。这个约定让递推 base case 成立也让所有查询公式在全定义域内无死角。很多算法的高级版本——比如后面要讲到的二维前缀和和差分数组——也都是建立在这个约定之上的。所以别看 pre[0] 0 只有一行它背后是整个公式体系自洽性的基石。3. 把同样的思路搬到矩阵二维前缀和的容斥原理一维玩明白之后二维就是顺理成章的扩展。面试和竞赛里二维前缀和的出场率不低尤其是涉及图像处理、矩阵区域统计的场景。它的思想没有变只是从“一条线上的累计”变成了“一块矩形区域内的累计”。3.1 前缀和矩阵的构造方式设原矩阵为 matrix行数 m、列数 n。二维前缀和矩阵 P 的定义是P[i][j] 从 (0,0) 到 (i-1,j-1) 这个左上角矩形区域内所有元素之和为了方便边界处理P 的尺寸是 (m1) × (n1)P[0][...] 整行和 P[...][0] 整列都置 0。构造时不能用双重循环直接累加每个小矩形那样复杂度会变成 O(m²n²)正确做法是基于如下递推P[i][j] P[i-1][j] P[i][j-1] - P[i-1][j-1] matrix[i-1][j-1]这个公式的意思是要算到当前位置的累计矩形先拿上方的累计矩形和左边的累计矩形相加但这两个矩形都包含了左上角那块重叠区域加了两遍所以减掉左上角那一块最后再加上当前格子的值本身。整个过程很像集合的容斥原理——两个集合的并集大小等于各自大小之和减去交集大小。这也是为什么我一直说二维前缀和的关键就四个字容斥原理。代码实现def build_prefix_2d(matrix): if not matrix or not matrix[0]: return [] m, n len(matrix), len(matrix[0]) P [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): P[i][j] (P[i-1][j] P[i][j-1] - P[i-1][j-1] matrix[i-1][j-1]) return P3.2 子矩阵和的查询公式如果我想查询原始矩阵中左上角 (r1, c1)、右下角 (r2, c2)均为闭区间的矩形区域内所有元素之和公式是sum P[r21][c21] - P[r1][c21] - P[r21][c1] P[r1][c1]依然是对容斥原理的直接应用。先取大矩形到 r2、c2 的累计作为基准然后减掉上方超出查询区域的部分再减掉左方超出的部分但上方和左方两者重叠的左上角区域被减了两次所以再加回来一次。这里我用一个简化的例子来验证。假设矩阵是[[1, 2], [3, 4]]对应的 P 矩阵尺寸 3×3为[[0, 0, 0], [0, 1, 3], [0, 4, 10]]现在查询原始矩阵中从 (0,0) 到 (1,1) 的整个 2×2 区域之和代入公式P[2][2] - P[0][2] - P[2][0] P[0][0] 10 - 0 - 0 0 10和 1234 10 一致。再查从 (1,0) 到 (1,1) 的区域也就是原矩阵最后一行 34P[2][2] - P[1][2] - P[2][0] P[1][0] 10 - 3 - 0 0 7正确。构造二维前缀和的时间复杂度是 O(m·n)之后每次查询也是 O(1)。空间复杂度同样是 O(m·n)如果原矩阵很大可以考虑原地修改或者用完即弃但大多数场景下多开一个矩阵是最稳妥的。3.3 二维边界为什么最容易写错二维前缀和的边界错误是我见过的bug重灾区主要集中在两个方面。索引偏移不一致有些模板用原始坐标直接映射有些用加1后的坐标两种混着用就会出问题。比如构造时用的是 P[i][j] 对应 matrix[i-1][j-1]查询时忘了这层偏移传参时少加 1结果一查就错。我的习惯是所有跟 P 打交道的下标一律理解成“矩阵左上角的前缀范围”在查询函数里统一完成从原始坐标到 P 坐标的转换不把偏移逻辑散落到各处。减项符号搞混查询公式里四个项的符号是 - - 很多人背不下来。我从来不背这个每次写都用“先整体减上边减左边加回左上角重叠”的口诀现场推推完再举个小例子验证像上面 2×2 矩阵那样心算两步。这个小习惯帮我省下了不知道多少调试时间。和树状数组处理二维问题相比二维前缀和更适合纯静态矩阵的矩形求和。树状数组支持单点修改后的动态查询但如果完全没修改没必要引入 log² n 的复杂度二维前缀和的 O(1) 查询是压倒性优势。4. 前缀和不止求和差分数组与前缀异或的降维打击如果你以为前缀和只能用来算和那格局就小了。围绕“前缀”这两个字的延伸还有两套非常实用的变体差分数组和前缀异或。它们在很多问题上比纯求和前缀和更巧妙值得单独拆开讲。4.1 差分数组就是前缀和的逆向操作一维前缀和是从原数组构造累计数组而差分数组是反过来——从一个“目标整体变化”的视角出发快速还原原数组的最终状态。定义差分数组 diff其中 diff[i] a[i] - a[i-1]同样用 1 下标约定a[0] 视为 0。那么有 a[i] diff[1] diff[2] ... diff[i]也就是说原数组是差分数组的前缀和。这是一个非常重要的对偶关系前缀和是求累计差分是求相邻变化量。差分数组的经典应用场景是对一个数组的多个区间做批量增减操作。比如给 [l, r] 区间内所有元素都加上 v朴素做法是遍历区间逐个加复杂度 O(len)。但如果用差分数组只需要 diff[l] v 和 diff[r1] - v最后对 diff 做一次前缀和还原就把 O(len) 的操作压到了 O(1)。这个原理可以用“水位标记”来理解diff[l] v 表示从第 l 天开始水位涨了 vdiff[r1] - v 表示第 r1 天开始水位回落 v中间每一天的高度变化通过前缀和自动传递下去。最终整个区间的整体抬升只用了两次数组操作不管区间多长。之前做过一道典型的区间调度问题给了几十万次对数组的区间加操作最后问每个位置的最终值。如果老老实实按区间遍历复杂度直接爆炸用差分数组处理所有操作 O(1) 记录最后一次性前缀和还原几秒跑完。这就是为什么我说“差分数组是前缀和的影子”两者经常成对出现一个负责构造成本低一个负责查询成本低。4.2 前缀异或碰上区间奇偶统计异或的运算性质里有一个非常有用的特点一个数异或自己等于 0。利用这一点可以构造前缀异或数组快速回答区间异或值xor(l, r) px[r] ^ px[l-1]。原理很简单px[r] 是 0 到 r 的异或累计把它和 0 到 l-1 的异或累计再做一次异或l 到 r 这部分因为出现了两次而抵消剩下的正好是区间内的异或结果。类似的思路还可以扩展到前缀积、前缀最大值等只要运算满足“可消去”或者“可逆”的性质就能用前缀结构做区间查询。我在实际项目里遇到过这样一个需求给定一个二进制数组需要快速判断某个子区间内 1 的个数是奇数还是偶数。最直接的做法是区间内逐个统计更聪明的做法是构造前缀奇偶标志然后通过异或判断前后状态是否一致——这就是把“前缀异或”的思想套在奇偶性统计上一次查询 O(1)优雅且高效。更进阶的玩法是前缀异或配合哈希表统计连续子数组的异或值等于 k 的个数这个我放到下面单独用一节实战案例展开因为它是前缀和从“区间查询工具”升级成“子数组计数利器”的关键一步。4.3 前缀思想的一通百通什么时候该想到它从求和、异或再到差分你会发现“前缀”这两个字的本质是把原始数据转换成“从起点到当前位置的累计状态”。只要一个操作满足结合律甚至不需要可逆就可以考虑前缀化。比如有些题目要求区间内是否所有元素都大于某个阈值可以构造前缀“小于等于阈值的个数”再用差值是否大于 0 来判断。判断的核心标准就两个是否需要用“区间”的视角反复查询查询的信息能否从“前缀状态”快速推导出“区间状态”如果两个答案都是肯定的前缀和一定在候选方案里。相比之下线段树和树状数组的适用范围更广因为它们能处理动态修改但它们的常数和实现复杂度也更高。工程上我的决策顺序是静态 可逆统计 → 前缀和动态 点修改 → 树状数组动态 区间修改/复杂统计 → 线段树或分块。先想清楚这个优先级大部分技术选型题都能省很多事。5. 实战套路当前缀和开始“组合”哈希表前缀和最常见的进阶玩法是和哈希表组合起来解决“连续子数组统计”类的问题。这里拿一个高频题来剖析给定一个整数数组和一个目标值 k统计有多少个连续子数组的和恰好等于 k。我第一次做这道题时只会 O(n²) 的暴力枚举直到把前缀和 哈希表这套组合拳理解透才真正体会到前缀和作为“结构”的巨大威力。5.1 从暴力到优化的思考路径暴力思路很直接枚举所有起点和终点用前缀和 O(1) 算出每个子数组的和但枚举本身仍然是 O(n²)。当 n 到 10^5 或者更大时这个复杂度依然无法接受。优化思路的关键在于换一个视角我们想知道有多少对 (i, j) 满足 pre[j] - pre[i-1] k。稍微变形一下就是 pre[i-1] pre[j] - k。也就是说当我们站在 j 这个位置时我们想找的是“之前有多少个位置的前缀和恰好等于 pre[j] - k”。这时哈希表就登场了它可以在 O(1) 时间内告诉我们“之前这类前缀和出现了多少次”。于是算法变成用一个字典记录“某个前缀和值出现的次数”从左到右扫描数组边构造当前前缀和边在字典中查找 pre - k 出现的次数累加到答案里然后把当前前缀和也记入字典注意先查后记避免把当前这个前缀和自己算进去。Python 实现如下def subarray_sum(nums, k): count 0 pre 0 hash_map {0: 1} for num in nums: pre num if pre - k in hash_map: count hash_map[pre - k] hash_map[pre] hash_map.get(pre, 0) 1 return count这里初始化{0: 1}也是“pre[0] 0”思想的延续表示一个元素都没有时前缀和为 0 的出现过一次。它处理的是“从数组开头到当前位置整段的和正好等于 k”的情形。如果没有这行初始化这类子数组会被漏掉。5.2 这套组合还能解决哪些问题学会了“前缀和 哈希表”的套路可以扩展到不少变体。统计连续子数组和为 k 的个数就是上面的代码核心是找 pre - k。统计连续子数组和能被 k 整除的个数在遍历过程中哈希表记录的是当前前缀和模 k 的余数两个子区间余数相同就说明它们的差能被 k 整除。找和为 k 的最长子数组长度遍历时记录每个前缀和第一次出现的最小下标之后遇到相同前缀和就用当前下标减最早下标更新最大长度。求解连续子数组异或和等于 k 的个数把加法换成异或查表时找 pre ^ k。这些变体的共同模式是把对子数组的枚举转化为对“两个前缀状态关系”的枚举再用哈希表把查找时间复杂度降下来。我在准备算法面试时把这个套路总结成一句话看到“连续子数组”和“等于某个目标”同时出现优先想前缀和能不能配合哈希表。九成的这类题都能在这个框架里找到解法路径。5.3 容易踩的三个隐性坑这套组合虽然威力大但坑也不少我逐一说明。哈希表的更新顺序必须先查询 pre - k再把当前 pre 存入哈希表。如果先存后查当 k 0 时当前这个前缀会被自己匹配到凭空多出一个不存在的子数组。这是 k 0 测试用例最容易暴露的bug。负数元素的影响前缀和并不是单调递增的所以不能中途发现 pre 超过某个阈值就 break必须完整扫描。很多人在处理正数数组时养成剪枝习惯换到负数数组就出错。模运算后负余数的处理统计“和能被 k 整除”时Python 的%对负数会返回非负余数行为跟 C 不同。如果要严谨地统一结果可以在取模后加 k 再取模(pre % k k) % k避免跨语言实现时结果不一致。这些坑在 LeetCode 的经典题“和为 K 的子数组”里都出现过网上也有不少人因为 k 0 和负数数组的原因反复提交失败。把这三个点刻进脑子里实战会少很多返工。6. 现场踩过最多的坑与调试经验前面每个部分我都穿插了一些容易出错的地方这里集中归档一份“前缀和避坑清单”都是我真实写代码过程中踩过、并且帮别人排查过的经典问题。6.1 预处理数组越界和下标错位最常见的问题出在“构建前缀和时数组长度多开了一位访问原数组时却忘了对齐”。我用一个具体例子说明原数组长度 n构建出的 pre 长度 n1。在循环里计算 pre[i] pre[i-1] nums[i-1] 时nums 的取数下标是 i-1。如果写成 nums[i]在 i n 时就会越界访问原数组最后一个元素之外的位置。Python 虽然经常不报错因为负索引会把 nums[-1] 当作最后一个元素但结果是灾难性的——数据错乱而无任何异常提示排查起来极其痛苦。调试建议在构造后立刻打印 pre 的前几个值和最后几个值人工验证几组简单数据的前缀和是否与手算一致。一旦发现第一个不一致的位置基本就能锁定是下标偏移还是边界处理的问题。6.2 区间查询时左边界到底是 l 还是 l-1这可能是所有前缀和问题里出现频率最高的“差一错误”。0 下标约定下查询 [l, r] 的和是用 pre[r1] - pre[l]1 下标约定下是 pre[r] - pre[l-1]。两种写法核心含义一样但如果你在 A 题用第一种、在 B 题用第二种中间混一次就会出错。我的习惯是所有和前缀和相关的函数开头统一做一次“区间转换”。比如传入原始数组的 0 下标 l 和 r函数内部直接算出对应的 pre 下标不让错误下标有机会扩散到后续逻辑。代码写多了你会发现绝大多数“区间查询结果差一个元素”的bug都来自下标约定混乱而不是算法思路问题。6.3 累加溢出的工程级隐患之前提过 int 溢出这里再补充两种工程上容易被忽略的情况。前缀和本身在合理范围内但中间某个差值溢出比如 pre[r] 和 pre[l-1] 都是合法 int但两者相差很大减法结果超出 int 范围。这种情况在 C/C 里尤其隐蔽因为溢出后无异常数值直接变负数。二维前缀和累加时溢出矩阵维度大、元素值大的时候P[i-1][j] P[i][j-1] 可能先溢出再做减法也不会回到正确值。所以二维前缀和的存储类型通常直接选 long long别等到线上数据量大了再改。通用对策是预估一下数据范围如果单元素最大可能值 × 数组长度接近或超过 int 上限就直接用更大的整型。预防性的类型选择比事后排查便宜得多——毕竟排查溢出的成本往往远高于多占的那几个字节。6.4 实战项目中的“空间换时间”取舍前缀和的代价是额外的 O(n) 或 O(m·n) 空间。在小数据集上这根本不是问题但在内存敏感的嵌入式环境或者超大矩阵场景下需要做取舍。一种折中方案是现场计算分段前缀和把数组分成若干块只保存块级别的累计和块内临时累加。这样单次查询复杂度介于 O(1) 和 O(block) 之间但内存可以从 O(n) 降到 O(n/block)。本质上是分块思想对前缀和的一种改造在面试里讲出来会显得你对性能的理解比较全面。另一些情况下可以复用原数组空间覆盖存储前缀和——但要注意后续再需要原数组时必须提前备份否则数据就被破坏了。这个在我们处理图像灰度图时经常用到原像素值用完后不再需要可以直接原地改成积分图省掉一整块额外分配。6.5 一个可靠的调试顺序最后分享一个我自己验证前缀和代码的“三层测试法”基本能覆盖绝大部分问题第一层手动小例子数组长度不超过 5用笔算几组区间结果和程序输出对照第二层边界用例查询整个数组、查询第一个元素、查询最后一个元素、查询空区间如果业务允许第三层随机大样本对拍写一个朴素 O(n²) 的暴力版本生成随机数组和随机查询逐个比较前缀和答案是否一致。这是所有算法题调试里最通用、也最有效的一招只要对拍拍上几百组没错正确性基本就稳了。这三层走完该过的测试用例基本都能过。尤其是第三层“对拍”我强烈建议每个刷算法的人养成习惯——它能瞬间把你代码里的隐形 bug 暴露出来比反复用人眼审查代码高效太多。7. 几个一眼就能套用的模板速查写这部分是因为我发现自己即便写了多年每次用到前缀和时还是下意识想翻一下手边的模板确保边界条件没写错。这里把一维、二维、差分、哈希表组合四个最常用的模板浓缩成速查方便直接复制改造。7.1 一维前缀和模板def build_prefix(nums): n len(nums) pre [0] * (n 1) for i, x in enumerate(nums): pre[i1] pre[i] x return pre # 查询原数组 [l, r] 之和 # 返回 pre[r1] - pre[l]7.2 二维前缀和模板def build_prefix_2d(matrix): m, n len(matrix), len(matrix[0]) P [[0] * (n1) for _ in range(m1)] for i in range(1, m1): row matrix[i-1] for j in range(1, n1): P[i][j] P[i-1][j] P[i][j-1] - P[i-1][j-1] row[j-1] return P def query(P, r1, c1, r2, c2): # 原始矩阵闭区间 (r1,c1) 到 (r2,c2) return P[r21][c21] - P[r1][c21] - P[r21][c1] P[r1][c1]7.3 差分数组模板def range_add(nums, ops): # ops: 三元组 (l, r, v)都是 0 下标表示 [l, r] 区间每个元素加 v n len(nums) diff [0] * (n 1) for l, r, v in ops: diff[l] v diff[r1] - v # 前缀和还原 cur 0 for i in range(n): cur diff[i] nums[i] cur7.4 前缀和 哈希表模板from collections import defaultdict def count_subarray_sum(nums, k): ans 0 pre 0 cnt defaultdict(int) cnt[0] 1 for x in nums: pre x ans cnt[pre - k] cnt[pre] 1 return ans这些模板互相独立但思想一脉相承。建议不要只是 copy 到编辑器里而是自己手写一遍把每个下标怎么偏移都过一遍脑子。只有亲手推过面试或者实战中遇到题目变形时才不会被下标绕晕。8. 写在最后前缀和这类基础算法的学习价值很多人刷算法时追求奇技淫巧觉得前缀和太“基础”了不够酷。但实际工作里前缀和思想四处可见——比如数据库里保存累计指标、图像处理里的积分图、统计报表中的滚动汇总本质上都是前缀思想的工程化应用。基础并不等于简单恰恰是这种最朴素的结构反而最需要吃透。我再分享一个小技巧日常刷题时把每道题的最优解和自己第一时间的暴力解做对比问自己“最优解到底优化掉了哪一步重复计算”。如果答案是“把多次遍历改成了预处理查询”那多半就是前缀和相关思路在起作用。带着这个角度去刷题你会发现自己对“预处理”这个词的理解会深刻很多而不只是会套模板。这套工具远没有到天花板。把一维、二维、差分、哈希表组合四个模板都亲手验证一遍再把上面的坑挨个踩一遍或者提前记下来避开你就已经超过了绝大多数“听说过前缀和”的人。后面不管遇到区间统计、子数组计数还是图像块状统计你都会很自然地想到这套方法论并且能快速判断它适不适合当前场景。
前缀和算法全攻略：从一维到二维、差分与哈希表组合技巧
提到区间查询、子数组统计这类问题很多算法题解里都会带一笔“可以用前缀和优化”但到底为什么能优化、优化在哪一步不少人其实是一知半解的。我自己刚开始刷题那阵子也这样——看答案觉得前缀和特别巧妙真到自己写的时候又总是差那么临门一脚要么边界算错要么空间开得莫名其妙。这篇文章就把我近两年实际用前缀和的经验从头到尾捋一遍从一维到二维从求和到异或再到差分把所有真正高频的用法和踩过的坑一次说清楚。1. 为什么所有区间求和问题都可以从这里开始先聊个最基本的场景你手里有一个长度为 n 的数组要频繁回答“从第 l 个元素到第 r 个元素加起来是多少”。最直接的办法是每次遍历一遍从 l 加到 r时间复杂度 O(n)。如果只查一次这完全没问题可一旦查询次数达到 m 次总复杂度就变成 O(m·n)。当 n 和 m 都是 10^5 级别的数据量这个复杂度直接就把程序拖垮了。前缀和的核心思路是预处理。在正式回答任何问题之前先把数组从头到尾扫一遍生成一个前缀和数组之后每次查询都只看这个预处理后的结果把单次查询的时间压到 O(1)。打个比方你是一家公司的行政三天两头有人问你“1号到30号这几个人的工龄加起来多少年”。笨办法是每次拿到名单逐个翻档案聪明办法是入职那天就把工龄从第一个人开始逐年累加记成一张表。以后不管问哪一段拿表上两个数字相减就完了——你要查 9 号到 17 号就用“到 17 号为止的累计值”减去“到 8 号为止的累计值”。本质上是把“重复的加法”提前做完把查询变成减法这就是整个算法最核心的朴素思想。从另一个角度理解前缀和的价值是重塑了信息的组织方式。原数组回答的是“某个位置是什么”前缀和数组回答的是“从起点到某个位置的整体状态是什么”。数据结构上有个通用原则——当你需要频繁回答某个固定模式的查询时就应该提前把那个模式的答案尽可能多地算好。前缀和就是这个原则在区间求和上的具体体现。所以只要你的问题能转化为“区间内某种可累加信息的统计”前缀和基本就是第一梯队该考虑的方案。这也是为什么它总和差分数组、树状数组、线段树并列在“区间问题基础工具集”里。接下来从最标准的一维前缀和说起把原理和代码一次盘清楚。2. 一维前缀和从暴力到 O(1) 查询的完整推导2.1 数组定义与递推公式的由来假设原始数组为 a下标从 1 开始这是 C/C 竞赛和很多算法模板里默认的习惯Python 里我通常也人为在开头补一个 0让逻辑统一。前缀和数组 pre 的定义是pre[0] 0pre[i] a[1] a[2] ... a[i]i 从 1 到 n构造过程是一个标准的递推pre[i] pre[i-1] a[i]这一步的时间复杂度是 O(n)空间复杂度是 O(n)一次性预处理之后任意区间 [l, r] 的和用公式sum(l, r) pre[r] - pre[l-1]注意这里的 l-1很多人第一次就是在这里写错。为什么不是 pre[r] - pre[l]因为 pre[l] 里已经包含了 a[l] 本身减掉的话就把左端点弄丢了。减法之前要看清楚“我到底想保留哪些元素”——保留从 l 到 r那就要减掉 1 到 l-1 的累计所以下标是 l-1。这个细节我至少见过十几个初学者反复踩每次调试才恍然大悟。如果你习惯用 0 下标这个公式一样成立只是写法变成 pre[r1] - pre[l]因为此时 pre[k] 表示前 k 个元素之和a[0] 到 a[k-1]。两种都行但一定要选一种并坚持到底最怕一会儿用 1 下标一会儿用 0 下标查错查到怀疑人生。2.2 代码实现与复杂度分析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 def range_sum(pre, l, r): # 输入 l, r 是原数组的 0 下标闭区间 return pre[r1] - pre[l]如果换成 C核心逻辑完全一样只是下标和数组类型需要留意vectorlong long pre(n 1, 0); for (int i 1; i n; i) { pre[i] pre[i-1] nums[i-1]; } // 查询 [l, r]0 下标 long long ans pre[r1] - pre[l];这里一个很容易被忽略的工程细节是数据类型。如果原始数组元素范围很大区间又很长累加结果可能超过 int 范围。我第一次在项目里写前缀和时有一个数组存的是用户行为计数单个值看起来不大可几万次累加后直接溢出查了半天才发现是 int 不够用。竞赛模板里通常直接上 long long实际工程里建议先估算一下上界别在这上面冒险。构造 O(n) 查询 O(1) 的组合已经是这个场景下的理论最优了。每次查询的常数极小就是一次数组访问和一次减法这也正是它能PK掉线段树的原因——线段树虽然也能 O(log n) 查区间和但常数和实现复杂度都高不少。如果你的需求只是静态数组的区间求和没有任何修改操作前缀和是最优先的选择没有之一。2.3 一个重要教训前缀和数组的起点为什么必须是 0之前提到预处理时人为地让 pre[0] 0很多新手觉得这只是规避边界的小技巧其实它是保证算法正确性的关键。如果没有这个“空集之和为 0”的定义当查询区间从第一个元素开始时l 0pre[l-1] 就变成了 pre[-1]直接下标越界。有了 pre[0] 0计算 sum(0, r) 时就是 pre[r1] - 0顺理成章。从数学上看pre[0] 0 对应的是“前 0 个元素的和”也就是空集的累加结果必须等于加法单位元 0。这个约定让递推 base case 成立也让所有查询公式在全定义域内无死角。很多算法的高级版本——比如后面要讲到的二维前缀和和差分数组——也都是建立在这个约定之上的。所以别看 pre[0] 0 只有一行它背后是整个公式体系自洽性的基石。3. 把同样的思路搬到矩阵二维前缀和的容斥原理一维玩明白之后二维就是顺理成章的扩展。面试和竞赛里二维前缀和的出场率不低尤其是涉及图像处理、矩阵区域统计的场景。它的思想没有变只是从“一条线上的累计”变成了“一块矩形区域内的累计”。3.1 前缀和矩阵的构造方式设原矩阵为 matrix行数 m、列数 n。二维前缀和矩阵 P 的定义是P[i][j] 从 (0,0) 到 (i-1,j-1) 这个左上角矩形区域内所有元素之和为了方便边界处理P 的尺寸是 (m1) × (n1)P[0][...] 整行和 P[...][0] 整列都置 0。构造时不能用双重循环直接累加每个小矩形那样复杂度会变成 O(m²n²)正确做法是基于如下递推P[i][j] P[i-1][j] P[i][j-1] - P[i-1][j-1] matrix[i-1][j-1]这个公式的意思是要算到当前位置的累计矩形先拿上方的累计矩形和左边的累计矩形相加但这两个矩形都包含了左上角那块重叠区域加了两遍所以减掉左上角那一块最后再加上当前格子的值本身。整个过程很像集合的容斥原理——两个集合的并集大小等于各自大小之和减去交集大小。这也是为什么我一直说二维前缀和的关键就四个字容斥原理。代码实现def build_prefix_2d(matrix): if not matrix or not matrix[0]: return [] m, n len(matrix), len(matrix[0]) P [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): P[i][j] (P[i-1][j] P[i][j-1] - P[i-1][j-1] matrix[i-1][j-1]) return P3.2 子矩阵和的查询公式如果我想查询原始矩阵中左上角 (r1, c1)、右下角 (r2, c2)均为闭区间的矩形区域内所有元素之和公式是sum P[r21][c21] - P[r1][c21] - P[r21][c1] P[r1][c1]依然是对容斥原理的直接应用。先取大矩形到 r2、c2 的累计作为基准然后减掉上方超出查询区域的部分再减掉左方超出的部分但上方和左方两者重叠的左上角区域被减了两次所以再加回来一次。这里我用一个简化的例子来验证。假设矩阵是[[1, 2], [3, 4]]对应的 P 矩阵尺寸 3×3为[[0, 0, 0], [0, 1, 3], [0, 4, 10]]现在查询原始矩阵中从 (0,0) 到 (1,1) 的整个 2×2 区域之和代入公式P[2][2] - P[0][2] - P[2][0] P[0][0] 10 - 0 - 0 0 10和 1234 10 一致。再查从 (1,0) 到 (1,1) 的区域也就是原矩阵最后一行 34P[2][2] - P[1][2] - P[2][0] P[1][0] 10 - 3 - 0 0 7正确。构造二维前缀和的时间复杂度是 O(m·n)之后每次查询也是 O(1)。空间复杂度同样是 O(m·n)如果原矩阵很大可以考虑原地修改或者用完即弃但大多数场景下多开一个矩阵是最稳妥的。3.3 二维边界为什么最容易写错二维前缀和的边界错误是我见过的bug重灾区主要集中在两个方面。索引偏移不一致有些模板用原始坐标直接映射有些用加1后的坐标两种混着用就会出问题。比如构造时用的是 P[i][j] 对应 matrix[i-1][j-1]查询时忘了这层偏移传参时少加 1结果一查就错。我的习惯是所有跟 P 打交道的下标一律理解成“矩阵左上角的前缀范围”在查询函数里统一完成从原始坐标到 P 坐标的转换不把偏移逻辑散落到各处。减项符号搞混查询公式里四个项的符号是 - - 很多人背不下来。我从来不背这个每次写都用“先整体减上边减左边加回左上角重叠”的口诀现场推推完再举个小例子验证像上面 2×2 矩阵那样心算两步。这个小习惯帮我省下了不知道多少调试时间。和树状数组处理二维问题相比二维前缀和更适合纯静态矩阵的矩形求和。树状数组支持单点修改后的动态查询但如果完全没修改没必要引入 log² n 的复杂度二维前缀和的 O(1) 查询是压倒性优势。4. 前缀和不止求和差分数组与前缀异或的降维打击如果你以为前缀和只能用来算和那格局就小了。围绕“前缀”这两个字的延伸还有两套非常实用的变体差分数组和前缀异或。它们在很多问题上比纯求和前缀和更巧妙值得单独拆开讲。4.1 差分数组就是前缀和的逆向操作一维前缀和是从原数组构造累计数组而差分数组是反过来——从一个“目标整体变化”的视角出发快速还原原数组的最终状态。定义差分数组 diff其中 diff[i] a[i] - a[i-1]同样用 1 下标约定a[0] 视为 0。那么有 a[i] diff[1] diff[2] ... diff[i]也就是说原数组是差分数组的前缀和。这是一个非常重要的对偶关系前缀和是求累计差分是求相邻变化量。差分数组的经典应用场景是对一个数组的多个区间做批量增减操作。比如给 [l, r] 区间内所有元素都加上 v朴素做法是遍历区间逐个加复杂度 O(len)。但如果用差分数组只需要 diff[l] v 和 diff[r1] - v最后对 diff 做一次前缀和还原就把 O(len) 的操作压到了 O(1)。这个原理可以用“水位标记”来理解diff[l] v 表示从第 l 天开始水位涨了 vdiff[r1] - v 表示第 r1 天开始水位回落 v中间每一天的高度变化通过前缀和自动传递下去。最终整个区间的整体抬升只用了两次数组操作不管区间多长。之前做过一道典型的区间调度问题给了几十万次对数组的区间加操作最后问每个位置的最终值。如果老老实实按区间遍历复杂度直接爆炸用差分数组处理所有操作 O(1) 记录最后一次性前缀和还原几秒跑完。这就是为什么我说“差分数组是前缀和的影子”两者经常成对出现一个负责构造成本低一个负责查询成本低。4.2 前缀异或碰上区间奇偶统计异或的运算性质里有一个非常有用的特点一个数异或自己等于 0。利用这一点可以构造前缀异或数组快速回答区间异或值xor(l, r) px[r] ^ px[l-1]。原理很简单px[r] 是 0 到 r 的异或累计把它和 0 到 l-1 的异或累计再做一次异或l 到 r 这部分因为出现了两次而抵消剩下的正好是区间内的异或结果。类似的思路还可以扩展到前缀积、前缀最大值等只要运算满足“可消去”或者“可逆”的性质就能用前缀结构做区间查询。我在实际项目里遇到过这样一个需求给定一个二进制数组需要快速判断某个子区间内 1 的个数是奇数还是偶数。最直接的做法是区间内逐个统计更聪明的做法是构造前缀奇偶标志然后通过异或判断前后状态是否一致——这就是把“前缀异或”的思想套在奇偶性统计上一次查询 O(1)优雅且高效。更进阶的玩法是前缀异或配合哈希表统计连续子数组的异或值等于 k 的个数这个我放到下面单独用一节实战案例展开因为它是前缀和从“区间查询工具”升级成“子数组计数利器”的关键一步。4.3 前缀思想的一通百通什么时候该想到它从求和、异或再到差分你会发现“前缀”这两个字的本质是把原始数据转换成“从起点到当前位置的累计状态”。只要一个操作满足结合律甚至不需要可逆就可以考虑前缀化。比如有些题目要求区间内是否所有元素都大于某个阈值可以构造前缀“小于等于阈值的个数”再用差值是否大于 0 来判断。判断的核心标准就两个是否需要用“区间”的视角反复查询查询的信息能否从“前缀状态”快速推导出“区间状态”如果两个答案都是肯定的前缀和一定在候选方案里。相比之下线段树和树状数组的适用范围更广因为它们能处理动态修改但它们的常数和实现复杂度也更高。工程上我的决策顺序是静态 可逆统计 → 前缀和动态 点修改 → 树状数组动态 区间修改/复杂统计 → 线段树或分块。先想清楚这个优先级大部分技术选型题都能省很多事。5. 实战套路当前缀和开始“组合”哈希表前缀和最常见的进阶玩法是和哈希表组合起来解决“连续子数组统计”类的问题。这里拿一个高频题来剖析给定一个整数数组和一个目标值 k统计有多少个连续子数组的和恰好等于 k。我第一次做这道题时只会 O(n²) 的暴力枚举直到把前缀和 哈希表这套组合拳理解透才真正体会到前缀和作为“结构”的巨大威力。5.1 从暴力到优化的思考路径暴力思路很直接枚举所有起点和终点用前缀和 O(1) 算出每个子数组的和但枚举本身仍然是 O(n²)。当 n 到 10^5 或者更大时这个复杂度依然无法接受。优化思路的关键在于换一个视角我们想知道有多少对 (i, j) 满足 pre[j] - pre[i-1] k。稍微变形一下就是 pre[i-1] pre[j] - k。也就是说当我们站在 j 这个位置时我们想找的是“之前有多少个位置的前缀和恰好等于 pre[j] - k”。这时哈希表就登场了它可以在 O(1) 时间内告诉我们“之前这类前缀和出现了多少次”。于是算法变成用一个字典记录“某个前缀和值出现的次数”从左到右扫描数组边构造当前前缀和边在字典中查找 pre - k 出现的次数累加到答案里然后把当前前缀和也记入字典注意先查后记避免把当前这个前缀和自己算进去。Python 实现如下def subarray_sum(nums, k): count 0 pre 0 hash_map {0: 1} for num in nums: pre num if pre - k in hash_map: count hash_map[pre - k] hash_map[pre] hash_map.get(pre, 0) 1 return count这里初始化{0: 1}也是“pre[0] 0”思想的延续表示一个元素都没有时前缀和为 0 的出现过一次。它处理的是“从数组开头到当前位置整段的和正好等于 k”的情形。如果没有这行初始化这类子数组会被漏掉。5.2 这套组合还能解决哪些问题学会了“前缀和 哈希表”的套路可以扩展到不少变体。统计连续子数组和为 k 的个数就是上面的代码核心是找 pre - k。统计连续子数组和能被 k 整除的个数在遍历过程中哈希表记录的是当前前缀和模 k 的余数两个子区间余数相同就说明它们的差能被 k 整除。找和为 k 的最长子数组长度遍历时记录每个前缀和第一次出现的最小下标之后遇到相同前缀和就用当前下标减最早下标更新最大长度。求解连续子数组异或和等于 k 的个数把加法换成异或查表时找 pre ^ k。这些变体的共同模式是把对子数组的枚举转化为对“两个前缀状态关系”的枚举再用哈希表把查找时间复杂度降下来。我在准备算法面试时把这个套路总结成一句话看到“连续子数组”和“等于某个目标”同时出现优先想前缀和能不能配合哈希表。九成的这类题都能在这个框架里找到解法路径。5.3 容易踩的三个隐性坑这套组合虽然威力大但坑也不少我逐一说明。哈希表的更新顺序必须先查询 pre - k再把当前 pre 存入哈希表。如果先存后查当 k 0 时当前这个前缀会被自己匹配到凭空多出一个不存在的子数组。这是 k 0 测试用例最容易暴露的bug。负数元素的影响前缀和并不是单调递增的所以不能中途发现 pre 超过某个阈值就 break必须完整扫描。很多人在处理正数数组时养成剪枝习惯换到负数数组就出错。模运算后负余数的处理统计“和能被 k 整除”时Python 的%对负数会返回非负余数行为跟 C 不同。如果要严谨地统一结果可以在取模后加 k 再取模(pre % k k) % k避免跨语言实现时结果不一致。这些坑在 LeetCode 的经典题“和为 K 的子数组”里都出现过网上也有不少人因为 k 0 和负数数组的原因反复提交失败。把这三个点刻进脑子里实战会少很多返工。6. 现场踩过最多的坑与调试经验前面每个部分我都穿插了一些容易出错的地方这里集中归档一份“前缀和避坑清单”都是我真实写代码过程中踩过、并且帮别人排查过的经典问题。6.1 预处理数组越界和下标错位最常见的问题出在“构建前缀和时数组长度多开了一位访问原数组时却忘了对齐”。我用一个具体例子说明原数组长度 n构建出的 pre 长度 n1。在循环里计算 pre[i] pre[i-1] nums[i-1] 时nums 的取数下标是 i-1。如果写成 nums[i]在 i n 时就会越界访问原数组最后一个元素之外的位置。Python 虽然经常不报错因为负索引会把 nums[-1] 当作最后一个元素但结果是灾难性的——数据错乱而无任何异常提示排查起来极其痛苦。调试建议在构造后立刻打印 pre 的前几个值和最后几个值人工验证几组简单数据的前缀和是否与手算一致。一旦发现第一个不一致的位置基本就能锁定是下标偏移还是边界处理的问题。6.2 区间查询时左边界到底是 l 还是 l-1这可能是所有前缀和问题里出现频率最高的“差一错误”。0 下标约定下查询 [l, r] 的和是用 pre[r1] - pre[l]1 下标约定下是 pre[r] - pre[l-1]。两种写法核心含义一样但如果你在 A 题用第一种、在 B 题用第二种中间混一次就会出错。我的习惯是所有和前缀和相关的函数开头统一做一次“区间转换”。比如传入原始数组的 0 下标 l 和 r函数内部直接算出对应的 pre 下标不让错误下标有机会扩散到后续逻辑。代码写多了你会发现绝大多数“区间查询结果差一个元素”的bug都来自下标约定混乱而不是算法思路问题。6.3 累加溢出的工程级隐患之前提过 int 溢出这里再补充两种工程上容易被忽略的情况。前缀和本身在合理范围内但中间某个差值溢出比如 pre[r] 和 pre[l-1] 都是合法 int但两者相差很大减法结果超出 int 范围。这种情况在 C/C 里尤其隐蔽因为溢出后无异常数值直接变负数。二维前缀和累加时溢出矩阵维度大、元素值大的时候P[i-1][j] P[i][j-1] 可能先溢出再做减法也不会回到正确值。所以二维前缀和的存储类型通常直接选 long long别等到线上数据量大了再改。通用对策是预估一下数据范围如果单元素最大可能值 × 数组长度接近或超过 int 上限就直接用更大的整型。预防性的类型选择比事后排查便宜得多——毕竟排查溢出的成本往往远高于多占的那几个字节。6.4 实战项目中的“空间换时间”取舍前缀和的代价是额外的 O(n) 或 O(m·n) 空间。在小数据集上这根本不是问题但在内存敏感的嵌入式环境或者超大矩阵场景下需要做取舍。一种折中方案是现场计算分段前缀和把数组分成若干块只保存块级别的累计和块内临时累加。这样单次查询复杂度介于 O(1) 和 O(block) 之间但内存可以从 O(n) 降到 O(n/block)。本质上是分块思想对前缀和的一种改造在面试里讲出来会显得你对性能的理解比较全面。另一些情况下可以复用原数组空间覆盖存储前缀和——但要注意后续再需要原数组时必须提前备份否则数据就被破坏了。这个在我们处理图像灰度图时经常用到原像素值用完后不再需要可以直接原地改成积分图省掉一整块额外分配。6.5 一个可靠的调试顺序最后分享一个我自己验证前缀和代码的“三层测试法”基本能覆盖绝大部分问题第一层手动小例子数组长度不超过 5用笔算几组区间结果和程序输出对照第二层边界用例查询整个数组、查询第一个元素、查询最后一个元素、查询空区间如果业务允许第三层随机大样本对拍写一个朴素 O(n²) 的暴力版本生成随机数组和随机查询逐个比较前缀和答案是否一致。这是所有算法题调试里最通用、也最有效的一招只要对拍拍上几百组没错正确性基本就稳了。这三层走完该过的测试用例基本都能过。尤其是第三层“对拍”我强烈建议每个刷算法的人养成习惯——它能瞬间把你代码里的隐形 bug 暴露出来比反复用人眼审查代码高效太多。7. 几个一眼就能套用的模板速查写这部分是因为我发现自己即便写了多年每次用到前缀和时还是下意识想翻一下手边的模板确保边界条件没写错。这里把一维、二维、差分、哈希表组合四个最常用的模板浓缩成速查方便直接复制改造。7.1 一维前缀和模板def build_prefix(nums): n len(nums) pre [0] * (n 1) for i, x in enumerate(nums): pre[i1] pre[i] x return pre # 查询原数组 [l, r] 之和 # 返回 pre[r1] - pre[l]7.2 二维前缀和模板def build_prefix_2d(matrix): m, n len(matrix), len(matrix[0]) P [[0] * (n1) for _ in range(m1)] for i in range(1, m1): row matrix[i-1] for j in range(1, n1): P[i][j] P[i-1][j] P[i][j-1] - P[i-1][j-1] row[j-1] return P def query(P, r1, c1, r2, c2): # 原始矩阵闭区间 (r1,c1) 到 (r2,c2) return P[r21][c21] - P[r1][c21] - P[r21][c1] P[r1][c1]7.3 差分数组模板def range_add(nums, ops): # ops: 三元组 (l, r, v)都是 0 下标表示 [l, r] 区间每个元素加 v n len(nums) diff [0] * (n 1) for l, r, v in ops: diff[l] v diff[r1] - v # 前缀和还原 cur 0 for i in range(n): cur diff[i] nums[i] cur7.4 前缀和 哈希表模板from collections import defaultdict def count_subarray_sum(nums, k): ans 0 pre 0 cnt defaultdict(int) cnt[0] 1 for x in nums: pre x ans cnt[pre - k] cnt[pre] 1 return ans这些模板互相独立但思想一脉相承。建议不要只是 copy 到编辑器里而是自己手写一遍把每个下标怎么偏移都过一遍脑子。只有亲手推过面试或者实战中遇到题目变形时才不会被下标绕晕。8. 写在最后前缀和这类基础算法的学习价值很多人刷算法时追求奇技淫巧觉得前缀和太“基础”了不够酷。但实际工作里前缀和思想四处可见——比如数据库里保存累计指标、图像处理里的积分图、统计报表中的滚动汇总本质上都是前缀思想的工程化应用。基础并不等于简单恰恰是这种最朴素的结构反而最需要吃透。我再分享一个小技巧日常刷题时把每道题的最优解和自己第一时间的暴力解做对比问自己“最优解到底优化掉了哪一步重复计算”。如果答案是“把多次遍历改成了预处理查询”那多半就是前缀和相关思路在起作用。带着这个角度去刷题你会发现自己对“预处理”这个词的理解会深刻很多而不只是会套模板。这套工具远没有到天花板。把一维、二维、差分、哈希表组合四个模板都亲手验证一遍再把上面的坑挨个踩一遍或者提前记下来避开你就已经超过了绝大多数“听说过前缀和”的人。后面不管遇到区间统计、子数组计数还是图像块状统计你都会很自然地想到这套方法论并且能快速判断它适不适合当前场景。
