每次遇到连续区间求和我第一反应就是“别用双循环”。前缀和算法说白了就是把原数组从一个一个查变成提前算好“从头到每个位置的总和”之后任意区间和只要做一次减法。这听起来简单却是很多性能瓶颈的解药从“每次现算”到“预计算复用”思维一换复杂度直接从O(n*m)降到O(nm)。这篇文章会围绕前缀和展开覆盖一维、二维模板差分数组和哈希表优化再手撕几道经典题。适合刚入门数据结构的同学、准备算法面试的开发者以及所有嫌自己暴力求解太慢的同行。读完你不仅会背模板还能理解每个下标偏移背后的原因直接拿来解LeetCode都不虚。1. 为什么暴力求和不靠谱前缀和的诞生背景1.1 暴力求和的性能瓶颈假设你有一个长度为10万的数组然后要回答10万次“下标2到5的和”。最本能的做法是写个循环int rangeSum(vectorint nums, int l, int r) { int sum 0; for (int i l; i r; i) sum nums[i]; return sum; }没问题结果正确但每次查询都要把区间重新扫一遍。一次查询最坏是O(n)10万次就是O(n*m)算下来10万乘10万电脑直接卡到怀疑人生。我见过有人用暴力跑LeetCode数据稍微大一点就超时最后还以为是平台卡。暴力法的根子在于它从不复用之前的计算结果。你今天查了[0, 100]明天查[50, 200]两个区间大部分重叠结果还是老老实实再算一遍。这就好比一个管家每天把整栋楼翻一遍找钥匙明明昨天已经翻过了还非要今天再来一次。1.2 前缀和的核心思想用空间换时间前缀和思路非常简单先花O(n)时间预处理一个数组prefix让prefix[i]表示原数组前i个元素的和。然后查询区间[l, r]的和直接返回prefix[r1] - prefix[l]。关键点在于这个“r1”和“l”。为什么不是prefix[r] - prefix[l-1]因为我们在定义时让prefix[0] 0prefix[1] nums[0]prefix[2] nums[0]nums[1]以此类推。这样原数组下标i对应的前缀和存在prefix[i1]里查询区间[l, r]就统一变成prefix[r1] - prefix[l]不用再特判l0的情况。打个比方记账时你每天记录“今天花了多少”如果想问“3号到7号一共花了多少”不需要重新翻每一天的账单只需要用“到7号为止的累积支出”减去“到2号为止的累积支出”。前缀和就是这套累积账本。1.3 从暴力到前缀和的直观对比我习惯用一个表格来说服团队里坚持暴力的人方法预处理时间每次查询时间总时间n次查询额外空间暴力遍历0O(区间长度)O(n*m)O(1)前缀和O(n)O(1)O(nm)O(n)这里的n是数组长度m是查询次数。当查询次数很多时前缀和的优势是碾压级的。就算只有一次查询前缀和的预处理开销也完全能接受只是你要判断是否值得。很多人问“什么时候该用前缀和”我的判断标准很简单如果你发现同一个数组要反复做“区间求和”这种查询或者求解“子数组和满足某种条件”的问题那就赶紧告别暴力上前缀和。2. 一维前缀和从模板到实战2.1 模版代码与构造过程前缀和的模板真的没什么花哨关键是把下标定义想清楚。我最推荐的做法是让前缀和数组比原数组多一位下标从1开始。C模板#include vector using namespace std; class PrefixSum { private: vectorint prefix; // prefix[i] 表示原数组前i个元素之和 public: PrefixSum(vectorint nums) { int n nums.size(); prefix.resize(n 1); prefix[0] 0; // 哨兵保证所有查询统一 for (int i 1; i n; i) { prefix[i] prefix[i - 1] nums[i - 1]; } } int rangeSum(int l, int r) { // 原数组下标 l 到 r return prefix[r 1] - prefix[l]; } };Python模板class PrefixSum: def __init__(self, nums): self.prefix [0] for x in nums: self.prefix.append(self.prefix[-1] x) def range_sum(self, l, r): return self.prefix[r 1] - self.prefix[l]注意构造函数里prefix[i] prefix[i-1] nums[i-1]这里nums下标是i-1。因为prefix的下标i代表“前i个元素”原数组第i个元素是nums[i-1]。这个习惯养成了后面二维、三维前缀和都不会乱。2.2 下标偏移的艺术为什么宁可多开一位我见过无数新手在边界上翻车。比如查询[0, 2]有人写成prefix[2] - prefix[0]结果算出来的是前2个元素的和漏了第三个。还有人把prefix[0]直接初始化为nums[0]然后查询时要各种if判断左边界是不是0。多开一位、引入哨兵本质上是在用“空间”换“逻辑对称性”。所有查询都统一成“右边界1减左边界”代码变得极其整洁也不容易出bug。这个经验不仅适用于前缀和很多算法题都可以用哨兵思想简化边界处理。我个人的习惯是写前缀和时心里默念三遍“prefix[i]是前i个元素的和不是第i个元素的和”。念完再动手正确率能提升30%。2.3 复杂度分析与适用场景预处理O(n)查询O(1)空间O(n)。这个复杂度是静态数组场景下的最优解因为你已经把所有可能的区间和都“压缩”进前缀和数组里了。适用场景非常明显反复查询区间和。比如游戏里频繁统计某个分数段玩家数量、数据库中定期计算某时间段的累计指标、图像处理中的积分图等。一句话只要“查询多修改少数组不变”前缀和就是首选。如果数组本身会频繁修改比如隔三差五改一个元素那么静态前缀和就需要重新计算复杂度反而高。这时候应该用树状数组或线段树后面会提到。3. 二维前缀和矩阵区域求和不再重复算3.1 二维构造的容斥原理二维场景是给你一个m行n列的矩阵反复问某个子矩形里的所有元素和。如果对每个查询都遍历子矩形那是O(mn查询次数)数据一大直接炸。二维前缀和pre[i][j]定义为原矩阵从(0,0)到(i-1, j-1)这个矩形内所有元素的和。为了让定义自洽pre[0][]和pre[][0]都设为0。构造递推式是pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] matrix[i-1][j-1]这个式子咋来的你想算左上角到(i,j)的矩形和可以用上面一行的矩形和加上左边一列的矩形和但左上角那块被加了两次所以要减掉一次最后再把当前格子加进来。这其实就是容斥原理的二维版本和集合∪的公式一模一样。用一个具体例子矩阵1 2 3 4要构造pre[2][2]。pre[1][2]是上边一行的前缀和pre[2][1]是左边一列的前缀和pre[1][1]是左上角那个小矩形也就是1。代入公式pre[1][2]pre[2][1]-pre[1][1]matrix[1][1] (12)(13)-14 10正好是整个矩阵的和。3.2 区域查询公式推导有了二维前缀和任意矩形区域左上角(r1,c1)右下角(r2,c2)的和就是sum pre[r21][c21] - pre[r1][c21] - pre[r21][c1] pre[r1][c1]同样用容斥先取包含这个区域的大矩形pre[r21][c21]减去上方多出来的那一条pre[r1][c21]减去左边多出来的那一条pre[r21][c1]但左上角那个小矩形被减了两次要加回来pre[r1][c1]。下图脑补一下其实就是大矩形减去两个多余的矩形再加上重复减掉的部分。模板代码int sumRegion(int r1, int c1, int r2, int c2) { return pre[r2 1][c2 1] - pre[r1][c2 1] - pre[r2 1][c1] pre[r1][c1]; }所有下标都加1的偏移原因和一维一样pre[i][j]对应前i行前j列原坐标需要映射到“前”的语义上。3.3 原地改造与内存优化如果矩阵很大额外开一个(m1)*(n1)的pre数组会吃掉不少内存。有一个常用的优化是在原矩阵上原地计算先每行从左到右累加再每列从上到下累加最后matrix[i][j]就变成原矩阵左上角到(i,j)的二维前缀和。这个做法的坏处是会覆盖原始数据。如果你后续还需要原矩阵就老老实实开新数组如果只是为了多次查询原地改造能省一半内存。我在竞赛中经常因为内存限制被迫这么做实测在10^4级别的矩阵上效果很明显。另外统一把pre定义为(m1)*(n1)且初始化为0查询时就不用判断边界代码干净很多。别小看这点LeetCode上很多二维题超时就是因为每次查询都在做一堆if判断。4. 前缀和的进阶玩法差分数组与哈希表4.1 差分数组区间更新的利器前缀和的反向操作是差分。给定数组nums差分数组diff满足diff[0]nums[0]diff[i]nums[i]-nums[i-1]i1。你会发现对diff做一次前缀和就能还原出原数组nums。差分最大的价值在于“区间更新”。如果要把区间[l, r]上的所有元素加val暴力是遍历区间逐个加O(区间长度)。差分只需要两步diff[l] val; diff[r1] - val;最后对diff做一次前缀和就能得到更新后的数组。复杂度从O(n)降到O(1)的更新这就是从“区间查询”到“区间更新”的对称思维。举个例子一个长度5的数组全为0要给[1,3]加2再给[2,4]加3。用差分数组操作后最后前缀和还原得到的结果是[0,2,5,5,3]仔细算一下完全正确。如果题目是“多次区间加最后问每个位置的值”差分就是标准答案。4.2 前缀和哈希表子数组和问题秒变O(n)前缀和真正上头的地方是在配合哈希表时。比如经典的“和为K的子数组”问题给你一个整数数组nums和一个整数k统计有多少个连续子数组的和等于k。暴力做法是枚举所有起点和终点O(n^2)。但如果用前缀和设前缀和数组presum[i]表示前i个元素之和那么子数组[j,i]的和等于presum[i1] - presum[j]。要找和为k就等价于找一对(i, j)使得presum[i1] - presum[j] k即presum[j] presum[i1] - k。于是问题变成遍历每个前缀和cur看之前有没有出现过“cur - k”这个前缀和值如果有就以这些位置为起点就能凑出k。用一个哈希表统计每个前缀和值出现的次数边遍历边更新答案。C模板int subarraySum(vectorint nums, int k) { unordered_mapint, int freq; freq[0] 1; // 空前缀和为0出现一次 int cur 0, ans 0; for (int x : nums) { cur x; // 之前有多少个前缀和等于 cur-k就有多少个以当前位置结尾的和为k的子数组 ans freq[cur - k]; freq[cur]; } return ans; }这里有个经典坑必须先把freq[0]1放进去。否则当cur恰好等于k时你会想“正是我要的”但cur-k0如果freq[0]不存在你就漏算了“从数组开头到当前位置”的整个子数组。4.3 经典题和为K的子数组手撕LeetCode 560我做这题时第一反应也想过滑动窗口但数组有正有负滑动窗口的单调性没了窗口移动逻辑根本写不对。换了前缀和哈希表代码一跑直接AC。给大家模拟一下过程。数组[1, -1, 0]k0i0x1cur1freq[1-01]不存在ans0freq[1]变成1i1x-1cur0freq[0]1ans1freq[0]变成2i2x0cur0freq[0]2ans3freq[0]变成3最终ans3。手动验证子数组[1,-1]、[0]、[1,-1,0]三个都满足和为0没错。这个模板还有个变种如果问“和为k的最长子数组长度”就把哈希表存“某个前缀和第一次出现的位置”每次遇到cur-k存在就更新长度。核心还是那个等式换汤不换药。5. 经典题目手撕实录从模板到解题思维5.1 LeetCode 303/304区域和检索与矩阵区域和这两道题完全就是模板题没有任何弯弯绕绕。303题给出一个数组反复调用sumRange(l, r)你只要把一维前缀和类写出来主函数就过了。304题给一个矩阵反复调用sumRegion(r1,c1,r2,c2)就是二维前缀和。我建议做这两题时不要直接抄模板而是自己手写一遍构造循环。特别是304题你要在纸上画一个3x3的矩阵把pre数组每个格子的值都算一遍感受那个容斥式的每个项在图上代表哪一块。这个过程一旦完成二维前缀和就再也忘不掉了。5.2 LeetCode 525连续数组题目是找含相同数量的0和1的最长连续子数组。直接数0和1没法用前缀和但我们可以把0看成-11看成1那么“相同数量的0和1”就等价于“子数组和为0”。问题转成找和为0的最长连续子数组。这时用前缀和哈希表记录“某个前缀和值最早出现的位置”。遍历数组计算当前前缀和cur如果cur在哈希表里出现过说明中间这段区间的和为0更新最长长度。如果没出现过就把当前位置存进去。这个题的转化过程最能体现前缀和算法思维的威力把一个看似和求和无关的问题通过映射变换变成标准的前缀和问题。类似的还有把字符映射成数字的套路。5.3 LeetCode 327区间和的个数离散化树状数组扩展这道题是一道更有挑战性的应用给定整数数组nums和区间[lower, upper]计算有多少个子数组的和落入这个区间内。暴力显然超时可以用前缀和加归并排序或树状数组。核心思想是把前缀和数组看成点集你要统计有多少对(i, j)使得presum[i] - presum[j]落在[lower, upper]内等价于presum[j]在[presum[i]-upper, presum[i]-lower]范围内。用树状数组维护值域上每个前缀和出现的次数每次查询区间内的计数。因为值域可能很大要先对前缀和值做离散化。这道题是前缀和、离散化、树状数组的综合应用建议有一定基础后再挑战。它告诉我们前缀和只是起点后续可以迭加数据结构解决更复杂的范围统计问题。6. 高频易错点与性能优化心得6.1 下标偏移的巨坑与统一解法我做了这么多年题看到最多的问题就是下标偏移。最常见错误前缀和数组长度定义成n查询时用r和l-1结果数组越界。构造时写成prefix[i] prefix[i] nums[i]逻辑直接乱掉。二维查询时少加一个加1查出来结果少一块。统一的解法只有一种死记“prefix[i]表示前i个元素”然后所有查询都通过“右边界1”和“左边界”来算。完事。6.2 整数溢出与long long当数组长度为10^5元素范围是10^9时前缀和累加值会轻松超过int的21亿上限。C和Java里必须用long long或long否则会出现玄学的负数结果。我见过一个很典型的场景面试者写int prefix样例过了但隐藏数据一跑就WA对着屏幕发呆一小时。所以开头就把类型写成long long省去所有后顾之忧。Python用户虽然不用考虑溢出但要注意频繁的大整数运算可能影响速度不过一般没问题。6.3 多维前缀和的复杂度与变换二维前缀和构造是O(mn)查询O(1)空间O(mn)。三维前缀和构造是O(n^3)查询也能O(1)但空间涨得厉害一般只在数据规模小时用。高维前缀和还有另一种不常用的但更快的处理方式先对每一维分别做一维前缀和最后再做容斥。这在处理某些特殊查询时能减少运算次数。但面试基本不会考三维把二维掌握牢就够了。另外如果题目要求的是“子矩阵最大值”而不是“和”前缀和就不行了得用其他数据结构比如稀疏表或线段树。前缀和本质上是把“加法”这种可逆运算变成减法对“最大值”这种不可逆运算就不适用。7. 前缀和的变种与扩展从模板到算法体系7.1 树状数组支持修改的前缀和前缀和最大的局限是数组静态。如果用树状数组可以在O(log n)时间内完成单点修改和区间查询。树状数组维护的其实就是动态前缀和本质上继承了前缀和的很多思想但通过二进制位的优化让更新和查询都变成了logn。面试中常见的问题是“设计一个数据结构支持单点更新和区间求和”。如果你只学前缀和会发现在修改一次之后需要O(n)重建整个数组。树状数组就是为了解决这个痛点而生的。所以我把前缀和看作树状数组的入门砖理解了前缀和的下标定义再学lowbit运算就顺理成章。7.2 离散化前缀和大值域小数据还有一种常见场景是值域特别大比如坐标范围到10^9但实际出现的点只有10^5个。如果直接开数组做前缀和内存直接爆炸。这时先把所有用到的坐标排序去重映射成1到M的连续整数再做前缀和。复杂度从O(值域)降到O(点数log点数)。这套方法在扫描线问题、求区间覆盖长度时非常好用。搭配树状数组或线段树还能处理更多动态查询。离散化的核心是把“稀疏的绝对位置”变成“连续的相对位置”和前缀和是天然的好搭档。7.3 怎么判断一道题该用前缀和我把这个思考过程整理成三个问题题目是否涉及连续区间的和/差值运算这个区间和的问题能否通过两个前缀值的差来表示数组是否静态或可以接受预处理如果三个都满足就放心上前缀和。如果数组需要频繁修改就转向树状数组或线段树。如果题目要求的是最大值、最小值、众数这类非可逆信息前缀和无法胜任需要另找思路。我自己在写暴力代码前都会强迫自己先停一下问一句“这个和会不会被反复查询”十次里有八次答案都是“会”于是直接上模板。这个习惯帮我省了大量面试和竞赛时间。最后再分享一个小技巧写前缀和题时无论一维还是二维都习惯把存储数组长度多加一位、下标从1开始让下标0当哨兵。这个习惯用了五年几乎没在边界上翻过车。希望这篇详解也能让你告别暴力求和把预计算思维真正用起来。