刷算法题的时候我经常看到有人一遇到“前缀和”“差分”就开始头皮发麻。原因倒也好理解这两个词听起来像两座大山好像没学过高等数学就翻不过去。但我想说你真的被名字唬住了。这俩东西本质就是你高中数列里天天见到的S_n前 n 项和和a_n通项公式/第 n 项换了个马甲而已。这篇文章就专门把这个“马甲”给你扒下来再把一维、二维、各种实战套路一次说透保证你看完能直接上手用。1. 先说根源Sn 和 an 怎么成了“前缀和”和“差分”1.1 高中课本里那两行被你忽略的公式高一学等差数列的时候老师一定写过两个式子前 n 项和S_n a_1 a_2 ... a_n通项公式a_n S_n - S_{n-1}n ≥ 2这第二个式子当年多数同学只把它当“求通项的手段”背完就忘了。但算法里的前缀和和差分全是靠这两行推导出来的。前缀和做的是什么事情把原始数组a从头到尾累加生成一个新数组s其中s[i]表示“前 i 个元素的和”。你仔细想这不就是数列里的S_i吗s[i] a[1] a[2] ... a[i]一模一样。差分做的是什么事情把原始数组a的相邻两项相减生成一个新数组b其中b[i] a[i] - a[i-1]。反过来看如果你对差分数组b求前缀和会得到什么b[1] b[2] ... b[i] (a[1] - a[0]) (a[2] - a[1]) ... (a[i] - a[i-1])中间全部抵消剩下a[i] - a[0]。如果空着的位置按 0 算那就是a[i]。你看差分就是前缀和的“反向操作”一个做“和”一个做“差”两边严丝合缝地对上了。1.2 为什么这对关系是算法的基础套路很多人学算法总觉得每个数据结构都是独立的新大陆但其实前辈们最大的本事就是把一个看似复杂的问题拆成自己已经会的几个简单操作。前缀和和差分恰好就是“区间操作”这个场景下最朴素的两块积木。举个例子。你手里有一个班级的成绩单老师问你“3 号到 8 号同学的总分是多少”。正常做法是拿张纸从 3 加到 8六个数加一遍。但如果老师今天心情好把每个区间都问一遍1-2 号、1-100 号、30-60 号……每次你都重新加手就废了。前缀和的做法是提前算好“前 1 个的和”“前 2 个的和”……“前 100 个的和”以后回答“3 到 8”就是“前 8 个的和”减“前 2 个的和”一次减法出结果。差分则是反过来用。假设你要给成绩单统一加分3 号到 8 号每人加 5 分。如果老老实实改 6 个格子发出去容易但改完可能又被要求“4 号到 6 号再加 3 分”改了又改。差分的思想是只记“从哪儿开始加的、从哪儿停止加”最后统一算总账。这个套路在算法里对应的是“区间修改 单点查询”在现实中的记账、排班、库存统计里到处都是。2. 前缀和把区间求和从 O(n) 砍到 O(1)2.1 核心推导区间和为什么是 s[r] - s[l-1]前缀和的构造很简单。假设数组a下标从 1 开始这点很关键后面我会专门说坑我们有s[0] 0s[1] a[1]s[2] a[1] a[2]s[3] a[1] a[2] a[3]一般地s[i] s[i-1] a[i]要找l到r的和等于(a[1] ... a[r]) - (a[1] ... a[l-1])也就是s[r] - s[l-1]。这个减法就像“用总长度剪掉前面挡着的那截”。前面挡着的是“前 l-1 个数的和”不是“前 l 个数的和”。我第一次写代码就犯过这个错s[r] - s[l]结果每次少算了一个a[l]。记住这里减的是s[l-1]因为你想要的是包含a[l]的区间。复杂度对比相当直观操作暴力法前缀和法预处理无O(n)单次区间和O(r-l1)O(1)m 次查询O(m × n)O(m n)n 是一万、m 是十万的场景下暴力是十亿次量级前缀和是十万次量级差距直接拉出一张“超时”和“通过”的分界线。2.2 标准模板代码与易错点下面给出三种常见语言的写法。以“给定数组求多个区间和”为例# Python 版 def build_prefix(nums): n len(nums) s [0] * (n 1) # 注意下标偏移s[0] 留空当 0 for i in range(1, n 1): s[i] s[i - 1] nums[i - 1] return s def range_sum(s, l, r): # 输入 l、r 是 1-based return s[r] - s[l - 1]// C 版适合竞赛党 vectorlong long buildPrefix(const vectorint nums) { int n nums.size(); vectorlong long s(n 1, 0); for (int i 1; i n; i) { s[i] s[i - 1] nums[i - 1]; } return s; } long long rangeSum(const vectorlong long s, int l, int r) { return s[r] - s[l - 1]; }几个容易踩的细节我边说边标出来下标统一用 1-baseds[0] 0。这样l1的时候s[1-1]s[0]不会越界公式也统一。数列和可能超过 int 范围尤其 LeetCode 和竞赛数据喜欢开大数前缀和数组尽量用long long。构造前缀和的过程中s[i] s[i-1] nums[i-1]这里nums[i-1]是因为原始数组如果是 0-based要做一个偏移。别混。如果你在做题时发现边界报错先检查两个位置第一s数组长度是不是n1第二查询时传进来的l、r是不是从 1 开始。这两个点对新手来说几乎是百分百会踩一次。3. 差分区间加法的“隐身术”本质是前缀和的逆3.1 差分数组怎么构造又怎么还原差分数组b的定义是b[i] a[i] - a[i-1]其中a[0]看作 0。直白地讲它记录的是a数组的“相邻变化量”。还原的时候对b做前缀和sum(b[1..i]) a[1] - 0 a[2] - a[1] ... a[i] - a[i-1] a[i]这就像你手里有一张“海拔表”上面记着每个观测点的海拔高度a。差分数组相当于记下“这一站比上一站高了多少”第一站比海平面高 10 米第二站比第一站高 3 米第三站比第二站低 2 米……只要把这一段段的“差”累加起来就能还原出每个站点的真实海拔。反过来如果你只想把“第 2 站到第 3 站之间的所有点都垫高 5 米”用差分数组就很省事。3.2 区间加法的核心只在两端做手脚现在考虑一个高频问题给数组a的某个区间[l, r]统一加上一个值v然后最后求每个位置的值。暴力做法for 循环从l到r挨个加时间复杂度 O(n)。如果在大型数据上反复执行 k 次区间修改就是 O(kn)。差分做法的关键操作非常反直觉只改两个位置。b[l] vb[r1] - v改完之后对b求一次前缀和得到的新数组就是区间修改后的a。为什么只改两个位置就对了我们来推理一下。对b做前缀和的过程中b[l] v会让l及以后所有位置的还原值都增加v影响范围是[l, n]。这多了一截所以我们要在r1位置- v让影响从r1开始被“中和”最终只有[l, r]这个区间真正增加了v。你可以把差分数组想象成一条“水坝的闸门”在l处开水闸水往下游一直流到n在r1处再开一个反向闸口把多余的水放掉于是真正被淹没的只有中间的[l, r]。一次区间操作变成两次 O(1) 的位置修改这就是差分“隐身”的地方。3.3 差分模板与一个典型场景先给标准模板// 差分: 多次区间加一次还原 void diffRangeAdd(vectorlong long diff, int l, int r, long long v) { diff[l] v; diff[r 1] - v; } vectorlong long restoreFromDiff(const vectorlong long diff) { int n diff.size() - 1; // diff[1..n] 有效 vectorlong long a(n 1, 0); long long cur 0; for (int i 1; i n; i) { cur diff[i]; a[i] cur; } return a; }一个特别容易碰到的场景是“区间加 单点查”比如某一天你的业务系统要统计各时段在线人数。用户 A 从 10 点到 12 点在线用户 B 从 11 点到 15 点在线问你每一小时后在线多少人。常规思路是每个用户都去[l, r]区间里逐个 1数据量一大就超时。差分做法是把每个用户变成“在 10 点 1、在 12 点结束后的那一格 -1”然后在时间轴上从左到右做一次前缀和每个时刻的在线人数就出来了。这个套路在各类“覆盖次数”题目里几乎是万能钥匙。4. 从一维到二维矩阵场景里的“面积思维”4.1 二维前缀和容斥原理的公式推导一维搞懂了二维是自然延伸。先看问题给一个 m 行 n 列的矩阵任意问你子矩形(x1, y1)到(x2, y2)的元素和。二维前缀和数组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)那一块相加时它被算了两次所以要减掉一次。这就是容斥原理。查询子矩形(x1,y1)到(x2,y2)的和时同样是容斥sum pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] pre[x1-1][y1-1]这里减掉两块大的再加回那块被减了两次的左上角。举一个具体的例子。矩阵长这样1 2 3 4 5 6 7 8 9要求 (2,2) 到 (3,3) 的和直观上是568928。二维前缀和算出来pre[3][3]45pre[1][3]6pre[3][1]12pre[1][1]1代入公式45-6-12128完美对上。实现上一般也是在矩阵外围多开一圈 0让pre[0][j]和pre[i][0]都是 0这样递推时不会越界。代码模板vectorvectorlong long buildPrefix2D(const vectorvectorint mat) { int m mat.size(), n mat[0].size(); vectorvectorlong long pre(m 1, vectorlong long(n 1, 0)); for (int i 1; i m; i) { for (int j 1; j n; j) { pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] mat[i-1][j-1]; } } return pre; }4.2 二维差分子矩阵统一加一个数二维差分和一维差分的思路一致同样是“只改四个角”最后做一次二维前缀和还原。假设我们要给矩形(x1, y1)到(x2, y2)整体加上v在差分矩阵d上做d[x1][y1] vd[x21][y1] - vd[x1][y21] - vd[x21][y21] v然后对整个差分矩阵做一次二维前缀和得到的就是修改后的矩阵。这四个点怎么理解用一维的“水闸”思路推广一下。d[x1][y1] v会让以(x1, y1)为左上角、向右下无限延伸的整个区域都被影响。为了让影响只保留在(x1, y1)到(x2, y2)矩形里就要在矩形的右下延伸线上“堵漏”在右边界右侧减回去在下边界下方减回去而右下角那个重叠区域被减了两次所以要再加回来一次。正好四个操作和容斥的“加加减减”形成镜像关系。二维差分的典型应用就是“给一块地图上的所有格子增加或减少某种数值”比如游戏里给某片区域统一加血、给某个矩形范围内 NPC 的刷新权重整体上调。暴力遍历整个矩形是 O(矩形面积)差分是 O(1) 改角 O(矩阵面积) 还原一次在多次批量修改时优势巨大。4.3 二维场景里最容易犯的错二维代码的常见错误第一个是把x1-1或y1-1写到循环里忘记防越界。解决办法是让矩阵从下标 1 开始预留 0 行 0 列。第二个错误是还原时把“修改”和“查询”顺序搞混了。二维差分只适合“先做一堆修改最后统一查询/还原”这种离线场景。如果每改一次就立即查询一次那复杂度反而会退化成 O(修改次数 × 矩阵面积)这种情况应该考虑二维树状数组或线段树别硬套差分。第三个错误是数据类型。二维矩阵的和、以及子矩形和常常轻松超过 int 上限尤其是题目数据范围到几千乘以几千的时候。long long是标配。5. 前缀和与差分套用的实战判断什么题用哪个5.1 典型场景一静态查询区间和选前缀和判断一句口诀如果数组本身不变只是有很多次“查某个区间的和”的请求就用前缀和。比如给你一个固定长度 n 的数组m 次询问[l, r]区间元素之和n、m 都到十万甚至百万。先 O(n) 构造前缀和之后每次 O(1) 回答整体 O(nm)。这类题的变形不少统计某个区间内出现多少次“正数”或“某个特征”只要把数组变成 0/1 的计数数组再做前缀和即可统计区间内数字有哪些恰好出现奇数次也可以用前缀异或前缀和的异或版本。核心还是“用预处理换查询速度”。5.2 典型场景二多次区间修改、一次还原选差分另一句口诀如果要对数组做很多次“区间整体加/减某个数”最后一次性输出所有位置的值就用差分。一个非常直观的例子是“停车场车位预约”。有 n 个时段、k 个预约每个预约覆盖[l, r]时段占用一个车位问每个时段最多同时有多少车。这本质就是“k 次区间加 1 最后输出每个位置”。差分处理完所有预约后做一次前缀和还原每个时段的车位数就出来了。如果再加一层循环每个预约去模拟数据一稍微大点就报废。另一个常见变体是“航班预订统计”给定一个航班列表每条记录表示[start, end]区间每天新增预订数求每天总预订数。同样是区间加 单点还原差分是标准解法。5.3 复杂一点的差分数组配合前缀和数组的嵌套实际题目不会总是一个模板直接套有时还要“先差分再前缀和”或者“前缀和数组再套一层前缀和”。我举一个嵌套思路。有些题目要求“区间加之后再统计区间和”。框架是先用差分完成多次区间修改但不要立刻还原整个数组因为修改次数和查询次数都很大时每次还原一次又查询一次复杂度可怕。更好的做法是“离线”把所有修改用差分数组累积好然后一次性把差分还原为实际数组再对这个实际数组建前缀和数组之后就能高效回答所有“区间和”查询。这种“先差分处理修改再前缀和处理查询”的两段式在处理大规模离线数据时是一套非常标准的组合拳。竞赛里好多“看着像线段树”的题其实用这个组合就能过而且代码好写得多、不容易写错。下面给一个简短的离线流程示意# 1. 处理所有修改 - diff 数组 diff [0] * (n 2) for l, r, v in all_updates: diff[l] v diff[r 1] - v # 2. 还原一次得到最终数组 (前缀和还原) arr [0] * (n 1) cur 0 for i in range(1, n 1): cur diff[i] arr[i] cur # 3. 再建前缀和应付区间和查询 prefix [0] * (n 1) for i in range(1, n 1): prefix[i] prefix[i - 1] arr[i] # 4. 回答查询 for l, r in all_queries: print(prefix[r] - prefix[l - 1])这套流程在 Gazillion 场次比赛里都出现过先记下来不亏。6. 几个我踩过的坑以及实用记忆技巧6.1 差分数组的“r 1 越界”问题差分区间加的标准操作是diff[r1] - v。如果r正好等于数组最后一个下标n那diff[n1]就已经超出“有效下标”了。处理办法有两种。一种是差分数组直接开n2大小多出来的格子留作缓冲无所谓另一种是在代码里判断if (r1 n) diff[r1] - v;。竞赛党一般直接开大一点并在构造函数里用n2的尺寸省心。我经常看到有人认为diff[n1]那格没有影响就懒得处理结果在最后求cur diff[i]时把i循环到了 n 就停了没看到越界。其实这个格只是存储了这辈子不会用到的“尾闸”但数组越界是 C 的未定义行为跨语言更要注意所以还是老老实实留空间。6.2 下标从 0 开始的是与非题目里的数组经常是 0-based。如果你用习惯的 1-based 公式一定要在做前缀和、差分时做偏移。一个稳妥的写法是读入原始数据后统一塞进a[1..n]下标从 1 开始。这样s[i]s[i-1]a[i]和range_sum s[r]-s[l-1]写起来最不容易错。如果题目给定、卢就是 0-based那区间[l, r]的查询应该写成s[r1] - s[l]因为s下标整体右移了一位。我个人的建议是新手阶段不跟题目下标较劲直接把所有数据都换成 1-based 再处理。多花几行读入的逻辑但换来公式、代码、调试的统一性绝对值。6.3 什么时候后缀和、前缀异或、前缀计数前缀和不是只有“加法前缀和”一种。很多题里你会遇到前缀异或用xor_prefix[i] xor_prefix[i-1] ^ a[i]查询区间异或值就是xor_prefix[r] ^ xor_prefix[l-1]。因为异或的逆运算还是异或不需要“减”。前缀计数把原数组替换成“某个事件是否出现”然后做前缀和就能快速回答“区间内这个事件出现了几次”。后缀和从右往左做累加解决“从第 i 个位置到末尾的和”这类问题。这些变体原理完全一样都是“预处理累积信息通过一次简单运算抵消掉多余部分”。学会一个其余触类旁通。6.4 “什么时候不能用前缀和/差分”也要心里有数这两个工具看起来挺万能但都有明显的边界。如果在区间修改之后紧接着就来一次区间查询要求实时、动态地维护。差分是“离线一次性还原”的思路改一次查一次就会退化前缀和也解决不了“数组元素动态变”的问题。这种要上树状数组或线段树。如果修改不是“整体加/减一个常数”而是“区间内每个元素乘一个数”或者其他非线性变换差分公式就不再成立需要找别的思路。如果矩阵太大、修改次数太多二维差分的还原 O(m×n) 本身也不可小觑。但相比于每次修改都去遍历矩形通常还是快得多。做题判断的时候把“查询 vs 修改”和“静态 vs 动态”这两个维度列出来往往一眼就能定到正确工具。6.5 我的一个习惯先用小样例手推一遍最后分享一个我很受用的习惯。拿到一道疑似前缀和/差分的题不管思路多清晰都先拿一个 3 到 5 个元素的小样例手推一遍全过程。比如a [0, 2, 4, 6]做一次差分b [0, 2, 2, 2]再对[1,3]加 3手动改b[1]3, b[4]-3再还原看结果。这么一推边界和符号错误基本能消灭八成。算法这东西最怕的不是公式看不懂而是“以为懂了”和“真会了”之间差的那一次手推。Sn 和 an 的两行公式你今天看完可能觉得不过如此但只要动手把前缀和、差分各写十遍以后区间题看到就能秒反应再也不觉得高不可攀。