说起前缀和我先聊一个非常实际的场景。假设你手上有一串长度为十万、甚至上百万的整数数组后面跟着十万个形如“请问第l个位置到第r个位置这段区间里的所有数字之和是多少”的查询。如果每次都老老实实地从头加到尾总共需要差不多10的11次方次加法运算常规机器跑完基本等于等一个世纪。而前缀和这个东西能在预处理之后让每次区间求和变成一次减法操作直接把问题压到近乎“秒回”的级别。前缀和本质上就是“在前i个位置上累计下来的总和”。维护好这个累计总和后面不管怎么查都能从累计结果里截取片段。做算法题、写数据处理脚本、搞性能敏感的程序这个思路都算得上最基础又最好用的几把工具之一。这篇文章我打算把一维和二维前缀和都捋一遍包括核心公式、边界条件、差分互补、内存优化、常见坑以及可以直接抄走的代码模板。1. 前缀和到底解决的是哪一类问题1.1 为什么不直接暴力求和先回到最朴素的需求。给定一个数组a每次查询要回答下标区间[l, r]内所有元素的和。暴力解法没有任何预处理查询时用一个循环从l加到r。看起来非常直觉也不用想太多。问题在于当数组长度和查询次数都到达一定量级之后暴力解法的时间消耗会迅速失控。做个简单的数学估计。数组长度n 100000查询次数m 100000最坏情况下每次查询都要遍历一整个数组总的加法操作达到n * m 10^10次。就算现代CPU每秒能跑十亿次级别的加法这种规模也要跑上十几秒。如果数据再涨到百万级或者查询再翻几倍直接没法用了。所以问题就变成了有没有一种办法让我们在查询之前花一点时间做准备工作把后续的每次查询都变成常数时间O(1)级别的操作。这就是前缀和出现的动机。1.2 核心思想空间换时间前缀和的思路很朴素。预处理阶段额外开一个数组S让S[i]表示原数组前i个元素的总和。有了S之后要算[l, r]区间和直接拿S[r]减去S[l-1]。因为前r个元素的和减掉前l-1个元素的和剩下来的自然就是第l到第r个元素的和。这就像你记录自己每月的存款余额变化。想知道3月到7月一共存了多少钱只需要看7月底的账户余额减去2月底的账户余额中间的流水不用一笔笔重新数。前缀和的预计算做的就是“把余额写到账本上”这件事。用空间换时间是算法设计里的经典套路。前缀和付出的空间是O(n)的额外数组换来的是查询时间从O(n)降为O(1)。在绝大多数场景下这个交换非常划算。它也是很多更复杂算法的基石比如后面会讲的二维前缀和、差分数组、矩阵快速求和等等。2. 一维前缀和定义、构造与复杂度分析2.1 原始数组与前缀和数组的对应关系假设原始数组下标从1开始很多人写算法题时习惯这样后面会解释为什么长度为n。定义前缀和数组S长度也是n并且令S[0] 0。那么有S[1] a[1] S[2] a[1] a[2] S[3] a[1] a[2] a[3] ... S[i] S[i-1] a[i]如果原数组下标从0开始同样可以处理常见做法是令S[0] 0然后S[i]表示数组前i个元素的和。此时S[i] S[i-1] a[i-1]查询区间[l, r]仍是0下标的和时用S[r1] - S[l]。两种写法都是对的选择哪种要看你习惯用哪种下标体系关键是全篇统一。我个人强烈推荐做题时用从1开始的下标。原因只有一个查询[l, r]时公式S[r] - S[l-1]不需要处理边界偏移写起来更顺手。而很多经典教材和模板也更偏爱这种记法。2.2 区间查询公式及边界条件区间查询公式非常简单sum(l, r) S[r] - S[l-1]为了保证l 1的时候不越界前缀和数组通常多开一个位置把S[0]空出来置为0。这样S[1] - S[0]恰好等于a[1]逻辑自洽。容易踩的坑是忘记减S[l-1]而减去S[l]。举个例子数组a [3, 1, 4, 1, 5]前缀和S [0, 3, 4, 8, 9, 14]。如果要求下标[2, 4]的和正确结果是1 4 1 6。用公式算S[4] - S[1] 9 - 3 6完全正确。但如果错误地用S[4] - S[2] 9 - 4 5就把位置2的那个元素给丢了。所以这个l-1为什么是l-1关键在于前缀和定义的是“包含当前下标之前所有元素的总和”。2.3 复杂度预处理O(n)查询O(1)前缀和整体流程分两步预处理用一个循环扫描原数组依次生成前缀和数组时间复杂度O(n)。查询每次区间求和做一次减法时间复杂度O(1)。回到开头那个十万级别的例子。预处理需要大约十万次加法然后每次查询一次减法十万次查询也是十万级别的操作。总操作量大概在两百万左右跟暴力的十的十次方相比已经是天壤之别。这也是前缀和最有吸引力的地方预处理成本很低后续查询代价几乎可以忽略。如果你的场景是“数组很少变化但查询很多”前缀和基本就是最优解之一。当然如果数组本身会频繁修改那就要考虑树状数组、线段树之类的结构了这是后话。3. 二维前缀和从一维到矩阵的扩展3.1 为什么需要二维前缀和把问题从数组扩展到矩阵。给定一个n行m列的二维数组现在要回答形如“以(x1, y1)为左上角以(x2, y2)为右下角的矩形区域里所有元素的和是多少”的查询。如果每次都暴力遍历矩形内部元素最坏情况下一次查询就是O(n*m)查询多了完全扛不住。二维前缀和的思路和一维完全一样只不过这次维护的对象变成了“从矩阵左上角(1,1)到 任意一点(i,j)这个矩形区域内的元素总和”。把这个二维累计结果预处理好后面的任意子矩形求和也可以从累计结果里通过几次加减运算得到。3.2 容斥原理推导递推式定义S[i][j]表示从(1,1)到(i,j)这个矩形区域内所有元素之和。怎么由已知的小范围推出大范围看下面这个关系一个以(1,1)为左上角、(i,j)为右下角的矩形可以拆成三部分从(1,1)到(i-1,j)的区域也就是S[i-1][j]从(1,1)到(i,j-1)的区域也就是S[i][j-1]单独点(i,j)处的一个元素a[i][j]但前面两项加起来会重复计算从(1,1)到(i-1,j-1)的那一块。因为它在S[i-1][j]里算了一次在S[i][j-1]里又算了一次。所以要在推导公式里把这块多算的减掉一次。于是得到二维前缀和的递推式S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] a[i][j]这个“加两个减一个”的套路本质上是容斥原理。它很适合用一个两个圆交叠的韦恩图来理解两个集合取并集等于两个集合大小之和减去它们的交集。在这里S[i-1][j]和S[i][j-1]的交集就是S[i-1][j-1]。实现时通常把S数组多开一行一列让第0行和第0列全是0这样递推时不需要额外的边界判断。3.3 子矩阵求和公式有了二维前缀和数组S现在求左上角(x1, y1)、右下角(x2, y2)的矩形元素之和。依旧用容斥sum(x1, y1, x2, y2) S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] S[x1-1][y1-1]为什么加回S[x1-1][y1-1]因为S[x2][y2]减去S[x1-1][y2]和S[x2][y1-1]之后左上角那块矩形(1,1)到(x1-1, y1-1)被减了两次所以必须加回来一次。这个公式怎么看都不算难但实际做题时特别容易在符号上搞反。我自己的经验是用具体的2x2矩阵走一遍比死记硬背公式靠谱得多。比如a [[1, 2], [3, 4]]前缀和是S [[0, 0, 0], [0, 1, 3], [0, 4, 10]]要求整个矩阵的和也就是(1,1)到(2,2)S[2][2] - S[0][2] - S[2][0] S[0][0] 10 - 0 - 0 0 10完全正确。如果只求右下角那个4也就是(2,2)到(2,2)S[2][2] - S[1][2] - S[2][1] S[1][1] 10 - 3 - 4 1 4也是对的。每次写公式之前拿这种小例子验算一遍能省掉大量调bug的时间。4. 二维后缀里的内存优化思路滚动数组与压缩技巧4.1 内存爆炸问题是怎么出现的二维前缀和最烦人的问题不是时间而是空间。一个n x m的二维数组如果n和m都是10000那总元素数量就是10^8。在 C 里一个int占4字节光是前缀和数组就要约占400MB。大多数在线评测平台内存限制在128MB或者256MB直接开二维整型数组大概率会内存超限。所以如果你只需要求所有以当前行结尾的子矩阵最大和或者只需要顺序扫描一遍矩阵二维前缀和的完整数组不是唯一的选择。此时可以用“滚动数组”或者“降维”的思路把二维前缀和压缩成一维进行滚动更新。4.2 用滚动数组做二维前缀和滚动数组的核心思想是我只保留当前行对应的前缀和以及上一行的前缀和用这两行递推下去。具体来说准备两个一维数组preRow[j]上一行中第(i-1, j)位置的前缀和。curRow[j]当前行中第(i, j)位置的前缀和。递推关系可以写成rowSum a[i][j] curRow[j] preRow[j] rowSum其中rowSum表示当前行从第一列到第j列的累计和。更新完当前行之后把preRow换成curRow继续下一行。用滚动数组的好处是把空间从O(n*m)降到O(m)。坏处是它并不支持任意的矩形子区域查询因为旧行的前缀和已经被覆盖了。它更常用于那种需要顺序处理每一行、并且只需要统计当前状态的问题比如求最大子矩阵和这类场景。如果你确实需要支持任意次任意矩形查询那完整的二维前缀和数组通常是躲不掉的这时就得靠优化读入、使用更紧凑的数据结构、或者考虑内存映射等方式来缓解压力。4.3 读入优化、数据类型和精度问题实战中还有一个容易被忽略的点前缀和累加之后的数值可能特别大。比如一个长度100000的数组元素值都在10^9量级加起来轻松超过10^14这已经超出了32位整型的范围。所以前缀和数组建议直接用long longC 里是long longJava 里是longPython 因为是大整数可以暂时不用太担心。读入方面如果数据量特别大建议使用快速读入比如 C 的scanf或者自写快读不要用cin默认的同步关闭设置。Python 则建议用sys.stdin.buffer.read()一次性读入后切分别用input()一行行读尤其是二维矩阵场景输入几百MB时会明显感觉到差距。5. 差分与前缀和一对反向操作5.1 一维差分快速区间加前缀和解决的是“频繁查询区间和”的问题差分解决的是“频繁对某个区间统一增减”的问题。两者是一对互逆的操作对差分数组求前缀和能得到原数组对原数组求前缀和能得到累计和数组。给定原数组a它的差分数组D满足D[1] a[1] D[i] a[i] - a[i-1] (i 1)如果要把区间[l, r]内所有的数同时加上v不需要真的去遍历这个区间。只需要在差分数组上做两个修改D[l] v D[r1] - v等所有区间操作都做完之后再对差分数组求一遍前缀和就能得到实际修改后的数组。原理很简单D[l] v会让从l开始之后的所有前缀和都增加v而D[r1] - v会让从r1开始之后的部分又恢复正常。一加一减区间加的效果就被精确限制在了[l, r]。这个技巧的典型应用是有大量区间更新的需求但更新完成后只需要查询最终的数组状态。这个时候用差分每次更新O(1)最后统一还原O(n)比暴力遍历快得多。如果更新和查询交替进行那还得上线段树或者树状数组。5.2 二维差分矩形区域加二维差分是二维前缀和的逆操作。矩阵中有一个矩形区域(x1, y1)到(x2, y2)想让这个区域里的所有元素同时加v。在二维差分数组D上需要做四次修改D[x1][y1] v D[x21][y1] - v D[x1][y21] - v D[x21][y21] v解释起来还是看容斥第一个加号让从(x1, y1)开始的右下角所有区域都加了v第二个减号把从(x21, y1)开始往下那一长条区域的加成都抵消掉第三个减号把从(x1, y21)开始往右那一长条区域的加成都抵消掉但这两个减号会重叠在从(x21, y21)开始的右下角区域所以这个区域被多减了一次要再加回来。所有区域更新完成之后对二维差分数组求一次二维前缀和得到的数组就是真实修改后的矩阵。这也是很多矩阵模拟题中“批量染色”、“批量增加权重”类问题的核心套路。6. 前缀和的应用场景与进阶套路6.1 子数组和等于K前缀和配合哈希表前缀和不只是“区间和查询”这么简单。一个经典扩展题是给定数组问有多少个子数组的和恰好等于k。暴力做法是枚举所有(l, r)对O(n^2) 判断。而用前缀和的话一个子数组[l, r]的和等于S[r] - S[l-1]。要等于k就需要S[r] - k S[l-1]。这意味着当我们在遍历到某个位置r时只需要知道之前出现过多少个前缀和值等于S[r] - k这些位置都能作为合法的l-1。于是可以用一个哈希表把每个前缀和值出现的次数记录下来。遍历过程中边累加前缀和边查哈希表边更新答案。时间复杂度从O(n^2)降到了O(n)。这个套路在面试和竞赛里非常常见本质上是把等式变换之后用一个map把历史前缀和缓存起来。6.2 最大子数组和与最大子矩阵和有名的“最大子数组和”问题可以用Kadane算法在线性时间内解决。但如果前面前缀和处理到一半想在二维矩阵里求最大和子矩阵思路就变成了枚举子矩阵的上边界和下边界把上下边界之间每一列的元素累加成一个一维数组然后对这个一维数组求最大子数组和。上下边界枚举本身是O(n^2)的每一行压缩和计算是O(m)的整体复杂度O(n^2 * m)。前缀和在这里的作用是能快速得到“从第i行到第j行第k列”的和从而把二维问题压缩成一维问题。这也是二维前缀和非常经典的一个进阶应用。6.3 前缀和的单调性与二分查找如果原始数组全是非负整数前缀和数组就是单调不降的。这种单调性可以和二分查找结合。比如想找“长度最短且和大于等于target的子数组”就可以枚举左端点然后在前缀和数组上二分查找最小的右端点。因为前缀和单调递增S[r] - S[l-1] target等价于S[r] target S[l-1]直接在S里用lower_bound找即可。这类“前缀和 二分”的组合在很多最短、最长子数组问题里都会出现。它再一次说明前缀和不只是“为了区间查询”更是一个能够支持后续各种算法操作的数据基础。7. 常见问题与实测避坑记录7.1 下标从0开始还是从1开始这是新手最容易纠结的问题。两种都可以但混用就会死得很难看。我建议竞赛与算法题默认采用“从1开始”的写法原因前面说过了边界公式更自然。如果你在写通用代码数组本身从0开始那也可以用S[i1] S[i] a[i]的模式让前缀和数组的S[i]表示前i个元素的和查询[l, r]时用S[r1] - S[l]。最怕的是写一半觉得从0开始更方便从1开始也挺好于是两种写法交叉出现调试时需要反复脑补下标偏移。我的建议是写任何涉及前缀和的代码之前先在注释里写清楚“这里的数组下标从几开始”再动手。7.2 二维前缀和算错总是漏加减重叠矩形二维前缀和无论是构造还是查询都逃不开那个容斥式子。构造时S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] a[i][j]查询时sum S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] S[x1-1][y1-1]。这四个符号的规律是“先加两个减一个再加被多减的一个”或者反过来“减两个加一个”。如果实在记不住就在纸上画一个简单的矩形标出几个关键区域很容易就能照着推出公式。我也见过很多人在确认公式时用随机小矩阵暴力对拍这是最稳妥的检验方式。7.3 差分数组还原时忽略r1的处理一维差分区间加时要改D[r1] - v这个r1很容易漏。漏掉之后从r1开始到末尾的所有元素也会被错误地加上v。二维差分更是要四个位置全部改到位漏掉任何一个还原出来的矩阵就会在某一行或某一列出现整体偏移。处理差分数组时建议数组开大一点。比如原数组长度n那差分数组至少开到n2目的就是让r1这个下标永远不越界。7.4 常见问题速查表现象可能原因排查思路区间求和结果比预期大忘记减S[l-1]减成了S[l]用一个小数组手写验算二维子矩阵求和结果不对容斥公式中某项符号写反拿2x2矩阵逐项代入差分还原后后半段全部偏移D[r1] - v漏了检查区间末尾是否处理大数组运行内存超限二维数组直接开满未做内存优化改用滚动数组或换思路累加和中途溢出成负数前缀和数值超出int范围换成long long重新计算8. 完整代码模板可以直接抄作业8.1 一维前缀和模板C 写法从1开始存储#include bits/stdc.h using namespace std; typedef long long ll; int main() { int n, m; cin n m; vectorll a(n 1), S(n 1, 0); for (int i 1; i n; i) { cin a[i]; S[i] S[i - 1] a[i]; } while (m--) { int l, r; cin l r; cout S[r] - S[l - 1] \n; } return 0; }Python 写法import sys input sys.stdin.readline n, m map(int, input().split()) a [0] list(map(int, input().split())) S [0] * (n 1) for i in range(1, n 1): S[i] S[i - 1] a[i] for _ in range(m): l, r map(int, input().split()) print(S[r] - S[l - 1])8.2 二维前缀和模板C 写法#include bits/stdc.h using namespace std; typedef long long ll; int main() { int n, m, q; cin n m q; vectorvectorll S(n 1, vectorll(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { ll x; cin x; S[i][j] S[i - 1][j] S[i][j - 1] - S[i - 1][j - 1] x; } } while (q--) { int x1, y1, x2, y2; cin x1 y1 x2 y2; ll ans S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] S[x1 - 1][y1 - 1]; cout ans \n; } return 0; }Python 写法import sys input sys.stdin.readline n, m, q map(int, input().split()) S [[0] * (m 1) for _ in range(n 1)] for i in range(1, n 1): row list(map(int, input().split())) for j in range(1, m 1): S[i][j] S[i - 1][j] S[i][j - 1] - S[i - 1][j - 1] row[j - 1] for _ in range(q): x1, y1, x2, y2 map(int, input().split()) ans S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] S[x1 - 1][y1 - 1] print(ans)8.3 差分模板一维与二维一维差分int D[N]; // 区间更新[l, r] 增加 v D[l] v; D[r 1] - v; // 全部更新完成后求一次前缀和得到最终数组 for (int i 1; i n; i) { D[i] D[i - 1]; a[i] D[i]; }二维差分int D[N][M]; // 矩形更新(x1,y1) 到 (x2,y2) 增加 v D[x1][y1] v; D[x2 1][y1] - v; D[x1][y2 1] - v; D[x2 1][y2 1] v; // 全部更新完成后做二维前缀和还原 for (int i 1; i n; i) { for (int j 1; j m; j) { D[i][j] D[i - 1][j] D[i][j - 1] - D[i - 1][j - 1]; a[i][j] D[i][j]; } }9. 我的实操心得写前缀和这类基础算法最容易翻车的往往不是算法本身而是那些看起来“不算技术”的小习惯。我自己踩过无数次坑之后总结出来几条比较管用的经验分享给读者。第一所有数组都尽量多开一点空间。一维数组开n 2二维开(n 2) * (m 2)。多出的那一两个位置不是为了好看是为了处理S[i-1]、D[r1]这类边界下标时不用每步都判断越界。宁可内存多写几个零也别让下标问题把时间浪费在调试上。第二写核心公式前先在纸上画图。尤其二维前缀和和二维差分容斥那四项看着简单但真到了高压的考试环境或面试白板环节很容易手滑。画一个简单的2x2矩阵把S[x2][y2]、S[x1-1][y2]这些项在图上对应出来十秒钟就能避免一次低级错误。第三遇到复杂问题先想一想能不能两个前缀和叠加用。有时候一个前缀和不够用比如要同时维护“区间和”和“区间平方和”就可以开两个前缀和数组。还有时候要配合差分、二分、哈希表前缀和只是其中一块拼图。不要局限在“前缀和只是用来查区间和”的固化思维里它更常作为一种预处理手段跟其他算法组合出强有力的解法。最后再分享一个小技巧写单元测试或者自己造数据时用暴力方法跟前缀和方法对拍。随便生成一个小规模数组跑几个查询两边结果一对比出错就能立刻发现。这个方法虽然土但在所有前缀和、差分、树状数组相关问题里都极其好使。毕竟算法题这行稳妥永远比炫技重要。