★ FEATURED ARTICLE 1. 前缀和到底解决什么问题1.1 暴力求和的痛点相信很多人刷算法题的时候都有过这样的经历题目一看就会一提交就超时。比如要你反复求数组中某个区间的和第一反应是写个两层循环从l加到r样例测试全部通过结果数据量一上来比如n 10^5再配上一万个查询TLE 直接教你做人。我见过不少刚开始刷题的朋友把这类问题归咎于“语言太慢”“编译器优化不够”其实根本原因在于每次查询都做了大量重复计算。区间[2, 5]的和算了一次区间[2, 6]的和又要从头开始加中间完全没有利用已有的计算结果。这种重复劳动在算法竞赛和面试题里就是最典型的优化靶子。前缀和算法就是针对“多次区间求和”这类场景最基础、最有效的预处理手段。它的核心思想只有一句话把“每次现算”变成“提前算好随时取用”。听起来很简单但它的变体——二维前缀和、差分数组、前缀和配合哈希表——几乎贯穿整个算法刷题生涯从 LeetCode 简单题一直用到竞赛里的数据结构优化。1.2 前缀和的核心思路与数学原理一维前缀和的定义非常直白。给定一个长度为n的数组a我们额外开一个数组pre其中pre[i]表示a从第一个元素到第i个元素的累加和即pre[i] a[1] a[2] ... a[i]这里的下标我习惯从 1 开始计数后面会解释为什么这么写能省掉一堆边界判断。有了pre数组之后任意区间[l, r]的和就能用两次数组的直接访问搞定sum(l, r) pre[r] - pre[l - 1]举个例子a [3, 1, 4, 1, 5, 9, 2, 6]那么pre [0, 3, 4, 8, 9, 14, 23, 25, 31]。这里我特意让pre[0] 0这样sum(1, r) pre[r] - pre[0]也能统一套公式。你要算sum(4, 6)就是pre[6] - pre[3] 23 - 8 15对应1 5 9完全正确。整个过程从原来最坏O(n)的遍历变成O(1)的减法如果查询次数是m总复杂度从O(n * m)直接降到O(n m)数据规模越大优势越明显。很多人第一次看到前缀和会觉得“就这这不就是累加吗”但这个思想的价值密度非常高。它本质上是一种预处理换查询的思路在数据相对固定、查询非常频繁的场景下把计算成本前置到一次性的预处理阶段让后续每次查询都变得极其廉价。这个思路不仅能用在数组求和上后面你会看到它如何配合哈希表解决“和为 K 的子数组个数”这类看似需要双重循环才能解决的问题。1.3 适用场景与不适用场景作为一个刷题老手我想先泼一盆冷水前缀和不是万能药用错场景反而把问题复杂化。适用的典型场景包括数组固定不变需要大量区间求和查询子数组、子矩阵相关的计数或最值问题比如“和为 K 的子数组”“乘积小于 K 的子数组”配合差分数组做区间批量修改后的查询某些需要快速计算累计量的动态规划优化。不适用的场景也很明显数组本身频繁修改而且修改和查询交替出现。这时候前缀和每次修改都要重建复杂度反而高应该考虑树状数组或线段树。数据量很小比如n 100查询也只有两三次这时候前缀和的预处理成本不见得比暴力低多少写起来还多一个数组性价比不划算。我在实际做题里养成一个习惯凡是看到“区间和”“连续子数组”“子矩阵”这些关键词先想想能不能用前缀和降维。如果能看一眼数据规模确认修改操作不是主要矛盾就可以放心地往这个方向走。2. 模板代码从一维到二维2.1 一维前缀和模板C前缀和本身没有太多炫技空间但细节决定成败。下面是经过多次比赛验证的稳定模板下标从 1 开始可以省去大量if边界判断#include bits/stdc.h using namespace std; int main() { int n, q; cin n q; vectorlong long a(n 1); for (int i 1; i n; i) { cin a[i]; } vectorlong long pre(n 1, 0); for (int i 1; i n; i) { pre[i] pre[i - 1] a[i]; } while (q--) { int l, r; cin l r; cout pre[r] - pre[l - 1] \n; } return 0; }这个模板有几个值得注意的点。首先pre数组用long long而不是int。区间求和很容易爆 int尤其是数组元素有正有负时累加和的绝对值可能远超单元素范围。我曾经在一道题里因为用int存前缀和数据一大就直接溢出成负数调试了半小时才发现问题。这种低级错误在面试现场非常致命直接用long long可以从源头避免。其次pre[0] 0这个设计很重要。它让pre[1] a[1]然后查询区间[1, r]时就是pre[r] - pre[0]公式统一不需要特判l 1。如果你贪图省事用下标从 0 开始虽然也能写但查询时得单独处理l 0的情况代码就脏了。Python 版本同样简洁n, q map(int, input().split()) a [0] list(map(int, input().split())) pre [0] * (n 1) for i in range(1, n 1): pre[i] pre[i - 1] a[i] for _ in range(q): l, r map(int, input().split()) print(pre[r] - pre[l - 1])2.2 二维前缀和模板如果一维数组的区间和对应一维前缀和那二维矩阵的子矩阵和就对应二维前缀和。这个扩展非常自然但公式的推导稍微绕一点值得单独拎出来讲。设pre[i][j]表示从矩阵左上角(1, 1)到(i, j)这个子矩阵内所有元素的和。递推公式是pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] a[i][j]为什么减掉pre[i-1][j-1]因为pre[i-1][j]和pre[i][j-1]都包含了左上角那片(1,1)到(i-1,j-1)的区域加起来之后那片被算了两次必须减去一次再加上当前元素a[i][j]。这个思路和小学学的容斥原理一模一样。查询以(x1, y1)为左上角、(x2, y2)为右下角的子矩阵和公式对称sum pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] pre[x1-1][y1-1]同样用容斥原理大矩形减去左边竖条、减去上边横条最后把多减的左上角小矩形加回来。模板如下int n, m; cin n m; vectorvectorlong long a(n 1, vectorlong long(m 1)); for (int i 1; i n; i) for (int j 1; j m; j) cin a[i][j]; vectorvectorlong long pre(n 1, vectorlong long(m 1, 0)); for (int i 1; i n; i) for (int j 1; j m; j) pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] a[i][j]; // 查询子矩阵和 int x1, y1, x2, y2; cin x1 y1 x2 y2; long long ans pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] pre[x1-1][y1-1]; cout ans \n;二维前缀和的坑主要在边界。我第一次写的时候把pre[i-1][j-1]漏了结果所有子矩阵的和都比正确值大还以为是输入数据有问题。后来我给自己定了一条规矩写完递推公式先在纸上画一个 2×2 的矩阵手算一遍再写代码从此再没犯过这种错。2.3 差分数组前缀和的“逆运算”前缀和有一个孪生兄弟叫差分数组它们之间是互逆的关系。如果你已经会前缀和那差分数组几乎是白送的。给定数组a定义差分数组diff满足diff[i] a[i] - a[i-1]换句话说对diff做前缀和就能还原出a。这个看似简单的性质在“区间批量加法”场景下有奇效。举例来说要把区间[l, r]内所有元素都加上x如果暴力做就是O(n)。但利用差分只需要diff[l] x; diff[r 1] - x;然后做完所有区间操作后一次性对diff求前缀和就能得到每个位置最终的值。时间复杂度变成O(区间操作数 n)。为什么要diff[r 1] - x因为前缀和的累加是连续的你在l位置加上x后从l开始一直到数组末尾都会加上这个x。为了让它只在r处截止需要在r 1位置减去x这样累加到r 1时正负抵消后面的位置就不受影响了。理解了这个差分数组就完全拿下了。我通常把前缀和和差分放在一起记它们是一对互补的工具工具解决的问题单次操作复杂度前缀和多次区间求和预处理 O(n)查询 O(1)差分数组多次区间批量修改修改 O(1)最后还原 O(n)实际题目里经常前缀和和差分一起出现先做区间修改再问最终数组或者先差分修改再前缀和求和一个套路打通很多题。2.4 常见易错点小结pre[l - 1]不是pre[l]。区间[l, r]的起点是l你减去的是起点之前所有元素的和。这是新手最容易犯的错我见过不止一个人在这里栽跟头。二维前缀和的四个项一个都不能少。少一个pre[i-1][j-1]结果永远是错的。边界下标从 1 开始。虽然 0 下标也能用但 1 下标配合pre[0] 0能让公式在所有情况下都成立。长时间不加long long。我会在写前缀和模板时就默认全部用long long后续题目用到时直接抄模板不会临时想。3. 经典题型实战拆解3.1 最朴素的模板题区间和检索LeetCode 303这道题就是前缀和模板的直接应用给定一个数组反复查询区间[i, j]的和。没有任何变体就是测你有没有掌握模板。class NumArray { public: vectorlong long pre; NumArray(vectorint nums) { int n nums.size(); pre.resize(n 1, 0); for (int i 0; i n; i) { pre[i 1] pre[i] nums[i]; } } int sumRange(int left, int right) { return pre[right 1] - pre[left]; } };这里我用了pre[i 1]的偏移写法对应原始数组的nums[0]到nums[i]。虽然类实现要求从 0 下标开始但内部用 1 下标偏移查询公式依然整洁。AC 之后你基本就掌握了前缀和的“肌肉记忆”。这道题我推荐作为热身不要太在意它简单关键是让自己形成条件反射看到“多次区间求和”立刻想到pre[r] - pre[l-1]不要多想。3.2 思维进阶和为 K 的子数组LeetCode 560如果说 303 是用来建立信心的那 560 就是真正考验前缀和理解的题目。给你一个整数数组nums和一个整数k你需要统计和为 k 的连续子数组的个数。暴力做法是枚举所有子数组O(n^2)复杂度数据规模一大直接超时。用前缀和可以把子数组求和降到O(1)但要枚举所有左右端点依然需要O(n^2)。这时候需要用前缀和配合哈希表做优化。核心思路是一个子数组[j, i]的和等于pre[i] - pre[j-1]如果它等于k那就等价于pre[j-1] pre[i] - k。于是当我们遍历到i时只需要知道之前有多少个前缀和的值等于pre[i] - k这个数量就是以i结尾的、和为k的子数组的数量。用哈希表记录每个前缀和值出现的次数遍历一遍数组即可时间复杂度O(n)class Solution { public: int subarraySum(vectorint nums, int k) { unordered_maplong long, int cnt; cnt[0] 1; // 表示前缀和为 0 的已经出现过一次 long long pre 0; int ans 0; for (int num : nums) { pre num; if (cnt.count(pre - k)) { ans cnt[pre - k]; } cnt[pre]; } return ans; } };关键点是cnt[0] 1这一行。它处理的是一个特殊场景从数组开头到当前位置的子数组即[0, i]它的和正好等于k。如果没有这行初始化这种子数组就会被漏掉。我第一次写这道题时就是忘了这行提交后比预期答案少排查了很久才意识到是初始状态没设置对。这道题我强烈建议反复刷三遍以上因为它不仅是前缀和题还教会你“用哈希表把找配对的问题变成查找问题”的思维模式。很多前缀和变体题比如“和可被 K 整除的子数组”“连续的子数组和”等等都是在这个基础上加一点小变化。3.3 二维扩展二维区域和检索LeetCode 304这题就是 2.2 节模板的直接应用。给定一个二维矩阵反复查询某个子矩阵的元素和。你只要把二维前缀和模板块抄上去再稍微封装就能 AC。class NumMatrix { public: vectorvectorlong long pre; NumMatrix(vectorvectorint matrix) { int n matrix.size(); int m matrix[0].size(); pre.assign(n 1, vectorlong long(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] matrix[i-1][j-1]; } } } int sumRegion(int row1, int col1, int row2, int col2) { return pre[row21][col21] - pre[row1][col21] - pre[row21][col1] pre[row1][col1]; } };从一维到二维的跳跃最重要的不是背公式而是理解为什么二维前缀和要用容斥原理来推。考试时如果记不清公式现推也就 30 秒的事远比死记硬背靠谱。我后来做更高维度的题目时都用类似的画图推导方式从来没在公式上翻过车。3.4 前缀和的变形与思维延伸把前缀和只当“求和工具”是远远低估了它。我在刷题过程中发现前缀和最迷人的地方在于它可以把“区间问题”转化为“两个前缀值的关系问题”。比如 LeetCode 724“寻找数组的中心下标”题意是找到一个位置让左边元素之和等于右边元素之和。暴力做法是每个位置都扫一遍但用前缀和只需要记下总和的total然后从左到右遍历维护左边累计sum每次判断sum total - sum - nums[i]即可一遍遍历结束。再比如“连续子数组的和小于等于某个阈值的个数”这类题目如果数组元素都为正数前缀和数组是单调递增的就能配合二分查找优化到O(n log n)。如果数组元素有正有负前缀和就不是单调的二分直接失效这时候得再想别的办法比如 3.2 中的哈希表思路。这也是我想强调的一点刷前缀和题的目的不只是背模板而是学会用“累计量”的视角审视数组问题。当你把pre数组画出来许多区间问题就变成了“在 pre 数组上找满足某种关系的下标对”的问题这时候你手里的工具就丰富多了。4. 常见问题与排查技巧实录4.1 边界索引混乱怎么办这是我见过最多的问题也是我早期经常踩的坑。以 1 下标为例查询区间[l, r]必须写成pre[r] - pre[l-1]。如果你写成了pre[r] - pre[l]结果等于把区间[l1, r]的和给算出来了看起来答案差不多但数据一验证就错。我的排查经验是先构造一个简单数组比如a [1, 2, 3, 4, 5]手动算出pre [0, 1, 3, 6, 10, 15]然后随机选几个区间手算对比。这个方法比盯着代码看高效一万倍。如果你算出sum(1, 5)不是15说明pre构造就有问题如果单个区间能算对但批量查询错大概率是边界处理不一致。4.2 数据溢出和负数陷阱前缀和数组里的累加和可能非常大也可能很小。int的范围大约是-2.1e9到2.1e9如果数组长度是10^5、每个元素绝对值是10^5累加和的量级就是10^10直接爆 int。我曾在一次模拟面试里犯过这个错代码逻辑全对就因为pre用int存大样例全部 WA。面试官盯着我看了半天问我是不是思路有问题我排查了半天才意识到是数据类型的问题。从那以后任何可能涉及累加的数组我都一律用long long宁可浪费点内存绝不冒溢出的风险。负数场景同样要留意前缀和数组不一定是单调的如果你在负数数组上强行用“前缀和二分”的思路结果必然出错。做题前先确认数组是否满足单调性条件。4.3 前缀和数组要不要额外占空间4.3 空间换时间但别忽略空间开销有些初学者会问能不能直接在原数组上做前缀和省掉一个数组的空间答案是可以但这会改变原数组的值如果后续还需要原数组信息就麻烦了。更推荐的做法是额外开一个pre数组空间复杂度O(n)在算法题中完全可接受。一个常见的空间优化技巧是如果只用前缀和做一次遍历可以像 3.2 那样只维护一个滚动变量pre配合哈希表记录历史值从而把空间压到O(1)不算哈希表的话或O(n)算哈希表。这种“不用数组存前缀和只存需要的历史结果”的思路在内存受限的题目里非常有用。4.4 多维前缀和的调试技巧调试二维前缀和时我习惯写一个打印函数把pre数组打印出来和手算结果对比。这个方法虽然笨但定位问题极快。另一个实用技巧是先把矩阵的那个角标错位画出来。比如pre[i][j]是“从(1,1)到(i,j)”的和查询(x1,y1)到(x2,y2)时转换成pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] pre[x1-1][y1-1]每一步都把坐标代入手算一遍。多做几次后你对容斥公式的理解会明显加深以后遇到三维前缀和推导也不会慌。5. 从模板到实战的一些心得5.1 前缀和与其他算法的结合前缀和本身不难真正体现功力的是它和其他思想结合的题目。比如配合二分求解“和不超过 K 的最大子数组长度”数组为正数时、配合单调队列解决滑动窗口内的累计问题、配合离散化处理大范围数据点上的区间统计等等。我之前遇到过一道题需要在一个稀疏矩阵里多次查询子矩阵和直接开二维pre数组内存不够。后来我先把矩阵的行和列做了离散化再用哈希表存储稀疏的前缀和成功把空间压缩到可以通过测试的程度。这就是典型的前缀和与离散化结合。再比如中位数相关问题如果题目要求“子数组的中位数”光靠前缀和还不够往往需要配合二分答案和前缀和大于答案记 1小于等于记 -1子数组和大于 0 则中位数可提高。这种交叉题型很考验功底但核心还是前缀和那一套累计逻辑。5.2 一些实战套路总结看到“区间和”“子数组”“子矩阵”等关键词优先考虑前缀和。看到“区间批量加、最后统一查询”的场景优先考虑差分数组最后用前缀和还原。看到“和为 K 的子数组数量”“和能被 K 整除”等计数类问题前缀和 哈希表是标准方案。如果数组元素为正数前缀和具有单调性可以配合二分查找有负数时切忌直接二分。构建前缀和之前先确认数据规模选择long long避免溢出。刷题不能只刷数量前缀和这类基础算法尤其需要“举一反三”。我的做法是拿一道模板题做熟然后把它的所有变形都过一遍一维区间求和、二维子矩阵求和、区间修改加单点查询、子数组计数、配合哈希表计数、配合二分求解最值。这一套全部吃透后前缀和相关的题目基本就没有能绊住你的了。最后再分享一个小技巧我平时会把不同场景的模板整理成一个代码片段文件每一份模板上标注清楚适用条件、复杂度、易错点。写题时直接调用成熟模板把精力集中在题目本身的思维难度上而不是浪费在重复的边界调试上。磨刀不误砍柴工这个习惯让我的刷题效率高了不止一个档次。
阅读完成 · 觉得有帮助？
