不知道你有没有过这种经历拿到一道题明明暴力解法想得很顺代码也就二十来行交上去却总是超时。你反复优化循环、改输入输出折腾半天还是卡在性能上。后来看了别人题解发现他只是在开头多写了一小段预处理把一堆“每次都要重新算”的东西提前存好查询就变成了 O(1)。这个预处理技巧八成就是前缀和和它经常一起出现的还有能高效处理“区间加值”的差分。这两个东西在信奥和算法题里几乎属于“保命技能”c 选手绕不开的那种。这篇文章就专门讲前缀和与差分。我会从一维到二维从静态数组到树状数组把公式怎么推、代码怎么写、边界怎么防坑都拆开讲。适合刚接触算法的初学者也适合刷题刷到瓶颈、想系统梳理一下的读者。顺便先提醒一句你要是去搜索引擎里搜“差分”大概率先看到一堆“差分放大器”“差分信号线”之类电子学内容跟算法里的差分完全是两码事——别搞混了。1. 前缀和从“暴力求和”到“O(1)查询”的思维跃迁1.1 一维前缀和的定义与构造先看最简单的情况。假设你有一个长度为 n 的数组 a下标从 1 开始。前缀和数组 S 的定义是S[i] a[1] a[2] ... a[i]也就是“数组前 i 个元素的和”。这个定义本身就是递推的要求 S[i]你不需要重新加一遍前面所有数只需要用 S[i-1] 加上 a[i] 就行。S[i] S[i-1] a[i]预处理阶段从头到尾扫一遍数组O(n) 就能把 S 算出来。之后你想知道任意一个区间 [l, r] 的和不需要再遍历直接用下面的公式sum(a[l..r]) S[r] - S[l-1]很多人第一次看到这个公式会愣一下为什么减的是 S[l-1] 而不是 S[l]因为 S[r] 包含的是前 r 个元素之和里面已经把前 l-1 个元素算进去了要单独留下 [l, r] 这一段自然要把前面的部分减掉。如果你下标从 1 开始那 S[0] 定义为 0这样当 l1 时S[l-1] 就是 S[0]0公式依然成立。这是从 1 开始编号最大的好处不用为区间左端点是 1 的情况单独写 if。在 c 里实现起来非常简单#include bits/stdc.h using namespace std; int main() { int n, q; cin n q; vectorlong long 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 (q--) { int l, r; cin l r; cout s[r] - s[l-1] \n; } return 0; }这个代码里有个细节s 和 a 都用 long long。原因很简单n 个 int 相加很可能超过 int 范围。别问问就是吃过亏。前缀和的本质是用“额外空间换时间”你多开一个数组预处理 O(n)之后每次查询 O(1)。如果题目里查询次数 q 很大比如 10^5 甚至 10^6暴力做法每次 O(n) 就会变成 O(nq)直接爆炸而前缀和总复杂度只有 O(n q)。1.2 二维前缀和矩形区域求和的利器一维前缀和解决的是“区间和”二维前缀和解决的是“子矩阵和”。假设有一个 n 行 m 列的矩阵 a定义二维前缀和数组 P[i][j] 表示从 (1,1) 到 (i,j) 这个子矩阵的所有元素之和。构造递推公式是这个P[i][j] P[i-1][j] P[i][j-1] - P[i-1][j-1] a[i][j]这个公式的图形理解是P[i-1][j] 是上边一块P[i][j-1] 是左边一块两个加起来左上角那块 P[i-1][j-1] 被加了两次所以要减掉一次最后再加上 a[i][j] 自己。这就是容斥原理的基本应用。查询时要计算左上角 (x1, y1)、右下角 (x2, y2) 的子矩阵和ans P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] P[x1-1][y1-1]同样是容斥先取整个大矩形减掉上边多出来的减掉左边多出来的然后左上角重叠被减了两次的部分要加回来。信奥题里二维前缀和的典型场景是给一张地图多次询问某个矩形区域内数字的总和。你不用每次重新遍历这个矩形提前 O(nm) 预处理每次查询 O(1)。比如后面的“救生员”“地毯”这类经典题实际上都是二维前缀和或者二维差分的变形。二维前缀和构造和查询的 c 代码逻辑如下vectorvectorlong long p(n 1, vectorlong long(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; p[i][j] p[i-1][j] p[i][j-1] - p[i-1][j-1] a[i][j]; } } // 查询 (x1, y1) 到 (x2, y2) long long ans p[x2][y2] - p[x1-1][y2] - p[x2][y1-1] p[x1-1][y1-1];注意 p 数组的维度要开 (n1) 行 (m1) 列并且第 0 行、第 0 列全部为 0。这样当 x11 或 y11 时下标 0 能兜住边界不用特判。1.3 为什么前缀和这么“香”一个很容易被忽略的点是前缀和不只是用来做区间求和。它更重要的价值在于“把区间信息压缩成两个前缀信息的差”。很多题目里只要遇到了“连续一段”“某个范围内的总量”这类表述你都应该下意识想想能不能用前缀和。举例来说统计一个数组中正数个数你可以用布尔标记加前缀和统计某段区间内某个值出现的次数也可以用前缀和。前缀和本质上是一种“可减性”的利用只要信息满足类似“整体 - 前面 后面”的运算规则就能前缀化。这和后面的差分形成了完美的镜像关系前缀和把区间和变成两次查询的差差分把区间修改变成两次单点修改。2. 差分区间修改的反向操作2.1 一维差分把“区间修改”化为“两次单点修改”如果说前缀和是“提前算好总和”那差分就是它的逆运算。给定数组 a构造差分数组 bb[i] a[i] - a[i-1]注意这里也是从下标 1 开始并且定义 a[0] 0所以 b[1] a[1]。差分数组有一个关键性质对差分数组 b 做前缀和还原出来就是原数组 a。换句话说a 是 b 的前缀和b 是 a 的差分两者互为逆运算。这个性质有什么用最经典的场景是对原数组 a 的某个区间 [l, r] 统一加上一个值 v。如果直接操作 a最坏要 O(n)但如果操作差分数组 b只需要做两处修改b[l] v b[r1] - v为什么这样可行因为 a 是 b 的前缀和。b[l] 加 v会让 a[l]、a[l1]、... 一直到 a[n] 都加上 v。为了让 a[r1] 及之后恢复原状再在 b[r1] 减去 v这样从 a[r1] 开始前缀和抵消就不再变化。整体效果就是只有 [l, r] 这段被加了 v。给你一个具体例子。a 初始全 0长度 n8。我想让 [2, 5] 都加 3[4, 7] 都加 1。用差分数组操作操作1b[2] 3b[6] - 3。 操作2b[4] 1b[8] - 1。然后对 b 做一遍前缀和得到最终 aa[1] 0 a[2] 3 a[3] 3 a[4] 3 1 4 a[5] 4 a[6] 4 - 3 1 a[7] 1 a[8] 1 - 1 0手推一遍你就会发现整个过程不只是“公式背下来”而是真正理解了前缀和的逆运算。这也是我强烈建议初学者自己拿笔推一次的原因。m 次区间修改每次都 O(1) 改两个位置全部操作结束后只用 O(n) 做一次前缀和把 a 还原出来。总复杂度 O(n m)暴力修改则是 O(nm)。当 n 和 m 都到 10^5 以上时这是本质区别。区间加操作的实现模板vectorlong long diff(n 2, 0); auto add [](int l, int r, long long v) { diff[l] v; diff[r 1] - v; // 注意 r1 可能等于 n1所以数组开 n2 }; // 所有操作结束后还原 for (int i 1; i n; i) { diff[i] diff[i-1]; a[i] diff[i]; // 此时 diff 已经变成原数组 }我这里的 diff 数组开的是 n2因为 r 最大是 nr1 就是 n1如果数组只开到 n1会越界。这个问题在二维差分里更明显后面会专门讲。2.2 二维差分矩阵区域加值二维差分配合二维前缀和能解决“给某个子矩阵统一加一个值最后求整个矩阵变化后的值”这类问题。二维差分的构造思路与一维类似构建一个差分矩阵 D使得对 D 做二维前缀和后得到原矩阵 a。对于一次“左上角 (x1, y1)、右下角 (x2, y2) 加 v”的矩形修改只需要在差分矩阵里操作四个位置D[x1][y1] v D[x21][y1] - v D[x1][y21] - v D[x21][y21] v然后对 D 做一遍二维前缀和就得到操作后的原矩阵。这个四角操作的图形意义是在 (x1, y1) 加 v让从这个点开始的右下区域都加 v在右上角和左下角分别减 v把超出矩形范围的区域消掉但右上、左下两个区域会被减去两次所以右下角要加回来一次。这跟前缀和查询时的容斥是完全对称的。二维差分代码范式vectorvectorlong long d(n 2, vectorlong long(m 2, 0)); auto add [](int x1, int y1, int x2, int y2, long long v) { d[x1][y1] v; d[x21][y1] - v; d[x1][y21] - v; d[x21][y21] v; }; // 多次调用 add 修改 // 最后二维前缀和还原 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]; } }很多人在写二维差分时会犯一个经典错误忘记数组要开 n2 和 m2导致处理 x21 或 y21 时下标越界。为什么是 2 而不是 1因为修改时可能用到 x21而且做前缀和还原的时候i-1 位置也要能从 0 开始。实际上把第 0 行、第 0 列全留空再把第 n1 行、第 m1 列用来承接边界派生出的“抵消”是最稳妥的做法。宁可多开一点也不要越界这是基本功。二维差分还有一个常见的坑把修改和还原混在一起。很多人做一次修改就对整个矩阵做一次前缀和那复杂度又变回 O(nm) 了。正确的做法是先攒下所有修改用 O(1) 的四角法更新差分矩阵最后一次性做前缀和还原。差分的意义就在于“区间修改可以延迟到最后统一结算”这是它和直接修改最大的区别。3. 前缀和与差分的组合应用与信奥实战3.1 树状数组让前缀和与差分支持动态更新前面讨论的前缀和与差分都局限于“数组是静态的”预处理完后修改很少。但实际题目中经常出现“既有点修改又有区间查询”的动态场景比如洛谷模板题里的树状数组 1、树状数组 2。树状数组Fenwick Tree就是在这个需求下出现的它能维护一个数组支持单点修改和前缀和查询两者都能做到 O(log n)。拿一个非常经典的问题来理解树状数组维护一个长度为 n 16 的序列支持查询前缀和 sum(11)以及单点修改 add(3, x)。如果用普通数组查询前缀和要 O(n)修改只要 O(1)。用它反复来回操作整体还是 O(nq)。树状数组的做法是用一个树状结构把前缀和“分段存储”每个位置存的是某个 lowbit 区间上的和。lowbit(x) 定义是 x 的二进制表示里最低位的 1 所对应的数值比如 lowbit(6) 2因为 6 的二进制是 110最低位 1 对应的值是 2。query(11) 的流程是反复累加 tree[11]、tree[10]、tree[8]直到下标变成 0。11 的二进制是 1011lowbit(11) 1所以 11 - 101010lowbit(10) 2所以 10 - 81000lowbit(8) 8所以 8 - 0。查询是 O(log n)。单点修改 add(3, x) 则是从下标 3 开始不断向上更新父节点3 - 4 - 8 - 16每次 tree[下标] x直到超过 n。这也正好 O(log n)。如果想查区间和就用前缀和相减sum(r) - sum(l-1)。树状数组最巧妙的点在于它和差分可以嵌套使用如果想支持“区间修改 区间查询”只靠一棵树状数组不够因为区间修改如果用差分来转差分数组的每次单点修改对应原数组的区间影响而原来的前缀和查询会收到两棵树的共同影响。具体做法是维护两棵 BIT一棵维护差分数组 d[i]另一棵维护 i*d[i]。区间 [l,r] 加 v 时在两棵 BIT 上各做两次单点修改查询前缀和时用 (sum1 * x - sum2) 这种形式计算。这就是经典的“区间修改 区间查询”的双树状数组写法。struct Fenwick { int n; vectorlong long c; Fenwick(int size) : n(size), c(size 1, 0) {} void add(int pos, long long val) { for (; pos n; pos pos -pos) c[pos] val; } long long sum(int pos) { long long res 0; for (; pos 0; pos - pos -pos) res c[pos]; return res; } };我特意把 lowbit 写成pos -pos这是位运算写法也是最常见的写法。手动模拟一次sum(11)你会发现它比直接遍历 11 个数要快得多而且不受数组长度影响只和长度相关的二进制位数有关。信奥里面树状数组的常数比线段树小很多代码也短能处理绝大多数需要动态区间求和的问题。唯一的痛点是它天生只能处理前缀信息遇见区间最大值之类就不方便了那就要请出线段树。但至少在“前缀和与差分动态化”这个场景树状数组几乎是标准答案。3.2 经典题型拆解从“借教室”到“差分前缀和还原”差分最常见的出题套路是给你一堆区间每个区间都让某个统计量 1最后问每个点的实际情况。经典题有“种树”“铺地毯”“挤牛奶”等。我的建议是遇到这种题不要犹豫直接往差分上想。举个例子一个有 n 个房间的公寓m 个租房请求每个请求从第 l 天到第 r 天租住每天需要一个房间问有没有哪天房间不够用。这类题盯着“区间加 1”这个操作差分数组维护每个时间点的增量所有请求处理完后做前缀和就能得到每一天的占用房间数和房间总数比较即可。复杂度 O(n m)如果用暴力去每一天查占用就变成 O(nm)显然不现实。还有一类题是“差分 二分答案”比如经典的“借教室”题。它的操作是依次处理若干个区间减 1 的订单一旦某天教室数量变成负数就停。最容易想到的办法是每次都去区间暴力减那肯定超时。更稳的思路是二分答案判断前 k 个订单能否执行。check(k) 时只对前 k 个订单做差分区间减然后一次前缀和还原看看哪天会变负。每个 check 是 O(n k)二分要 O(log m) 次总复杂度 O((n m) log m)完全能过。这算把差分从一个“小技巧”升级成了“算法框架中的核心组件”。3.3 复杂度与空间取舍什么时候能用什么时候不能用选了前缀和或差分代价是什么空间。一维前缀和需要额外 O(n)二维需要 O(nm)。如果 n 和 m 本身都到 10^6那你必须考虑内存够不够。有时候题目卡内存你就要想能不能用滚动数组、原地修改或者离散化缩小范围。举个例子差分数组完全可以在原数组上做先把原数组当成全 0区间修改都打在差分上最后原数组本身变成“还原后的结果”。这样只用一份内存不需要额外开一个“最终结果数组”。但还有一个更隐蔽的限制前缀和依赖的信息必须满足“可减性”。像是求和、求异或和、求布尔值和这种可以整体与部分互相抵消的运算都能前缀化。但“最大值”“最小值”这种没法通过“减掉前面一部分”得到后面一部分的信息就不能直接用普通前缀和。这类问题要么用线段树要么用稀疏表等其他数据结构。我见过不少初学者学会了前缀和就什么题都想硬套结果误判了题意。你要记住前缀和是个“减法型”工具不是“全局型”工具。差分的限制则正好相反它要求你的操作是“区间整体加减同一个常数”而且这种加减在预处理期间不会产生“交叉影响”需要即时反馈。如果修改是“区间赋值成某值”而不是“加某值”差分就帮不上忙了因为赋值破坏可逆性。好在大部分竞赛题里加减操作是主流差分用得飞起。4. 实操中的常见问题与避坑经验4.1 下标从 0 还是从 1一个能省半天调试时间的选择这是一个看起来小、影响却极大的决策。我的建议很直接算法题里涉及前缀和、差分的场景一律从 1 开始存储数组把 0 位置空出来当哨兵。为什么因为 S[0] 0 可以让 [1, r] 的查询公式 S[r] - S[0] 不用特判差分的 b[1] a[1] 也不用特殊处理。二维里第 0 行、第 0 列全 0 的价值更明显每一条递推公式都能无脑套。如果你非要从 0 开始前缀和公式会变成 S[r1] - S[l]差分的话要处理 b[0] a[0] 这个“无中生有”的边界还要时刻注意 r1 是否会越界。我不是说从 0 开始写不了而是说从 1 开始能少想很多边界条件。在你还没有形成“下标偏移”的肌肉记忆之前从 1 开始是最不容易出错的选择。刷题群里你去看老选手的代码绝大多数前缀和题都是这么写的。4.2 溢出、负数与取模细节决定的 0 分与 100 分前缀和和差分最大的数值风险是“中间结果溢出”。差分数组在多次区间加之后某个位置的值可能是很大的数再做前缀和还原时更可能溢出。我的建议是无脑用 long long除非你明确知道数据范围非常小。有些题还会要求取模这个时候更要注意负数问题差分中做减法比如 b[r1] - v之后前缀和还原过程中可能出现负数。标准写法是在每次运算后加 mod 再取模避免出负数。举例diff[r1] - v 之后如果后面要直接做前缀和并用模运算最好写成(d[i] mod - v) % mod;虽然这不影响差分本身的正负但是如果你最后要对原数组取模那么差分累积过程中的负值会通过加法传递必须时刻保证每一步都在 [0, mod) 范围内。不少选手在这个环节吃过亏明明样例能过大数据一提交就 WA检查半天发现是负数取模的问题。4.3 二维操作最易错的四个点二维前缀和和二维差分的坑比一维多得多。我总结了四个最容易踩的第一数组开小了。前面反复强调二维差分需要 n2 行 m2 列因为修改操作会用到 x21、y21从 1 开始编号时这俩值最大值就是 n1、m1数组少一位就越界。第二还原差分时把公式抄错。还原的二维前缀和公式是d[i][j] d[i-1][j] d[i][j-1] - d[i-1][j-1]有人会漏掉中间的减号。第三查询矩形范围搞反。对 (x1,y1) 到 (x2,y2)正确的容斥下标是 x1-1、y1-1、x2、y2写成别的就会得到完全错误的结果。第四把修改和还原混在一起。有些人每做一次区间修改就暴力跑一边前缀和复杂度全毁。真正写法是攒修改、最后还原前面多次提到实际操作时特别容易犯。我建议初学二维部分时拿一个 3x3 的小矩阵手算一遍把数组下标和公式每一项对应关系写出来。写一次比看十遍都管用。等你完全理解了那个容斥逻辑再去写代码就不会只是“背模板”了。4.4 树状数组与差分结合的边界细节树状数组和差分结合时有个容易忽略的问题两棵树状数组的大小定义。如果原数组长度是 n区间修改时你要在差分数组的 r1 位置减 v此时 r1 可能等于 n1。树状数组内部 add 操作的循环条件是pos n如果 pos 超过 n 就更新不了这个“减 v”就丢失了。但这个时候其实无所谓因为前缀和查询只查到 n永远不会去查 n1 以后的位置在 r1 减 v 的操作本来就是多余的。所以你可以选择不处理它或者专门处理成if (r1 n) add(r1, -v)。两种逻辑都该在心里有个数不然你在调试时会很困惑为什么 add 传了一个 n1 进去树状数组却没反应还有一个细节两棵 BIT 维护 i*d[i] 时i 是原数组下标d[i] 是差分值。区间修改对第二棵树的影响是add(l, v*l)、add(r1, -v*(r1))。这里 v 和下标相乘也要尽量用 long long不然又是一个隐蔽的溢出点。4.5 从“会模板”到“会思路”我的个人刷题心得前缀和与差分看起来是小知识点但它们其实是“逆运算思维”的启蒙你看到一个数组不仅可以直接操作它还可以换一个视角通过操作它的差分来间接完成目标。这种思维迁移到很多领域都有用。比如在图像处理里“积分图”就是二维前缀和的应用让任意矩形区域的像素和能被 O(1) 查询在统计区间覆盖次数时差分的思路也比直接遍历高效得多。我甚至觉得如果你能彻底理解“差分是前缀和的逆运算”这一句话很多算法题就不再需要死记硬背模板了。就我个人经验来说遇到一个新题型我会先问自己三个问题能不能转化成区间加减能不能转换成前缀和查询能不能用差分延迟计算这三个问题任何一个是“能”题目基本就破解一半了。反之如果你对一个题目完全没有思路先往这三个方向想往往也能打开局面。这个习惯是我刷了上百道题之后才慢慢养成的如果你刚接触可以直接把这三个问题当“ checklist”用。到了这里前缀和与差分的核心内容就全讲完了。代码不多但每一个模板背后都有值得琢磨的推导过程。希望你不要只背代码而是真的拿笔在草稿纸上推一遍把差分数组前缀化还原成原数组感受一下“逆运算”的美妙。下次再遇到区间修改和区间查询你就知道用不上那些花里胡哨的数据结构前缀和与差分就够你走得非常远了。 
长河君 · 2026/10/4 4:09:33 · 阅读 1.2k 前缀和与差分：从区间查询到区间修改的算法利器
不知道你有没有过这种经历拿到一道题明明暴力解法想得很顺代码也就二十来行交上去却总是超时。你反复优化循环、改输入输出折腾半天还是卡在性能上。后来看了别人题解发现他只是在开头多写了一小段预处理把一堆“每次都要重新算”的东西提前存好查询就变成了 O(1)。这个预处理技巧八成就是前缀和和它经常一起出现的还有能高效处理“区间加值”的差分。这两个东西在信奥和算法题里几乎属于“保命技能”c 选手绕不开的那种。这篇文章就专门讲前缀和与差分。我会从一维到二维从静态数组到树状数组把公式怎么推、代码怎么写、边界怎么防坑都拆开讲。适合刚接触算法的初学者也适合刷题刷到瓶颈、想系统梳理一下的读者。顺便先提醒一句你要是去搜索引擎里搜“差分”大概率先看到一堆“差分放大器”“差分信号线”之类电子学内容跟算法里的差分完全是两码事——别搞混了。1. 前缀和从“暴力求和”到“O(1)查询”的思维跃迁1.1 一维前缀和的定义与构造先看最简单的情况。假设你有一个长度为 n 的数组 a下标从 1 开始。前缀和数组 S 的定义是S[i] a[1] a[2] ... a[i]也就是“数组前 i 个元素的和”。这个定义本身就是递推的要求 S[i]你不需要重新加一遍前面所有数只需要用 S[i-1] 加上 a[i] 就行。S[i] S[i-1] a[i]预处理阶段从头到尾扫一遍数组O(n) 就能把 S 算出来。之后你想知道任意一个区间 [l, r] 的和不需要再遍历直接用下面的公式sum(a[l..r]) S[r] - S[l-1]很多人第一次看到这个公式会愣一下为什么减的是 S[l-1] 而不是 S[l]因为 S[r] 包含的是前 r 个元素之和里面已经把前 l-1 个元素算进去了要单独留下 [l, r] 这一段自然要把前面的部分减掉。如果你下标从 1 开始那 S[0] 定义为 0这样当 l1 时S[l-1] 就是 S[0]0公式依然成立。这是从 1 开始编号最大的好处不用为区间左端点是 1 的情况单独写 if。在 c 里实现起来非常简单#include bits/stdc.h using namespace std; int main() { int n, q; cin n q; vectorlong long 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 (q--) { int l, r; cin l r; cout s[r] - s[l-1] \n; } return 0; }这个代码里有个细节s 和 a 都用 long long。原因很简单n 个 int 相加很可能超过 int 范围。别问问就是吃过亏。前缀和的本质是用“额外空间换时间”你多开一个数组预处理 O(n)之后每次查询 O(1)。如果题目里查询次数 q 很大比如 10^5 甚至 10^6暴力做法每次 O(n) 就会变成 O(nq)直接爆炸而前缀和总复杂度只有 O(n q)。1.2 二维前缀和矩形区域求和的利器一维前缀和解决的是“区间和”二维前缀和解决的是“子矩阵和”。假设有一个 n 行 m 列的矩阵 a定义二维前缀和数组 P[i][j] 表示从 (1,1) 到 (i,j) 这个子矩阵的所有元素之和。构造递推公式是这个P[i][j] P[i-1][j] P[i][j-1] - P[i-1][j-1] a[i][j]这个公式的图形理解是P[i-1][j] 是上边一块P[i][j-1] 是左边一块两个加起来左上角那块 P[i-1][j-1] 被加了两次所以要减掉一次最后再加上 a[i][j] 自己。这就是容斥原理的基本应用。查询时要计算左上角 (x1, y1)、右下角 (x2, y2) 的子矩阵和ans P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] P[x1-1][y1-1]同样是容斥先取整个大矩形减掉上边多出来的减掉左边多出来的然后左上角重叠被减了两次的部分要加回来。信奥题里二维前缀和的典型场景是给一张地图多次询问某个矩形区域内数字的总和。你不用每次重新遍历这个矩形提前 O(nm) 预处理每次查询 O(1)。比如后面的“救生员”“地毯”这类经典题实际上都是二维前缀和或者二维差分的变形。二维前缀和构造和查询的 c 代码逻辑如下vectorvectorlong long p(n 1, vectorlong long(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; p[i][j] p[i-1][j] p[i][j-1] - p[i-1][j-1] a[i][j]; } } // 查询 (x1, y1) 到 (x2, y2) long long ans p[x2][y2] - p[x1-1][y2] - p[x2][y1-1] p[x1-1][y1-1];注意 p 数组的维度要开 (n1) 行 (m1) 列并且第 0 行、第 0 列全部为 0。这样当 x11 或 y11 时下标 0 能兜住边界不用特判。1.3 为什么前缀和这么“香”一个很容易被忽略的点是前缀和不只是用来做区间求和。它更重要的价值在于“把区间信息压缩成两个前缀信息的差”。很多题目里只要遇到了“连续一段”“某个范围内的总量”这类表述你都应该下意识想想能不能用前缀和。举例来说统计一个数组中正数个数你可以用布尔标记加前缀和统计某段区间内某个值出现的次数也可以用前缀和。前缀和本质上是一种“可减性”的利用只要信息满足类似“整体 - 前面 后面”的运算规则就能前缀化。这和后面的差分形成了完美的镜像关系前缀和把区间和变成两次查询的差差分把区间修改变成两次单点修改。2. 差分区间修改的反向操作2.1 一维差分把“区间修改”化为“两次单点修改”如果说前缀和是“提前算好总和”那差分就是它的逆运算。给定数组 a构造差分数组 bb[i] a[i] - a[i-1]注意这里也是从下标 1 开始并且定义 a[0] 0所以 b[1] a[1]。差分数组有一个关键性质对差分数组 b 做前缀和还原出来就是原数组 a。换句话说a 是 b 的前缀和b 是 a 的差分两者互为逆运算。这个性质有什么用最经典的场景是对原数组 a 的某个区间 [l, r] 统一加上一个值 v。如果直接操作 a最坏要 O(n)但如果操作差分数组 b只需要做两处修改b[l] v b[r1] - v为什么这样可行因为 a 是 b 的前缀和。b[l] 加 v会让 a[l]、a[l1]、... 一直到 a[n] 都加上 v。为了让 a[r1] 及之后恢复原状再在 b[r1] 减去 v这样从 a[r1] 开始前缀和抵消就不再变化。整体效果就是只有 [l, r] 这段被加了 v。给你一个具体例子。a 初始全 0长度 n8。我想让 [2, 5] 都加 3[4, 7] 都加 1。用差分数组操作操作1b[2] 3b[6] - 3。 操作2b[4] 1b[8] - 1。然后对 b 做一遍前缀和得到最终 aa[1] 0 a[2] 3 a[3] 3 a[4] 3 1 4 a[5] 4 a[6] 4 - 3 1 a[7] 1 a[8] 1 - 1 0手推一遍你就会发现整个过程不只是“公式背下来”而是真正理解了前缀和的逆运算。这也是我强烈建议初学者自己拿笔推一次的原因。m 次区间修改每次都 O(1) 改两个位置全部操作结束后只用 O(n) 做一次前缀和把 a 还原出来。总复杂度 O(n m)暴力修改则是 O(nm)。当 n 和 m 都到 10^5 以上时这是本质区别。区间加操作的实现模板vectorlong long diff(n 2, 0); auto add [](int l, int r, long long v) { diff[l] v; diff[r 1] - v; // 注意 r1 可能等于 n1所以数组开 n2 }; // 所有操作结束后还原 for (int i 1; i n; i) { diff[i] diff[i-1]; a[i] diff[i]; // 此时 diff 已经变成原数组 }我这里的 diff 数组开的是 n2因为 r 最大是 nr1 就是 n1如果数组只开到 n1会越界。这个问题在二维差分里更明显后面会专门讲。2.2 二维差分矩阵区域加值二维差分配合二维前缀和能解决“给某个子矩阵统一加一个值最后求整个矩阵变化后的值”这类问题。二维差分的构造思路与一维类似构建一个差分矩阵 D使得对 D 做二维前缀和后得到原矩阵 a。对于一次“左上角 (x1, y1)、右下角 (x2, y2) 加 v”的矩形修改只需要在差分矩阵里操作四个位置D[x1][y1] v D[x21][y1] - v D[x1][y21] - v D[x21][y21] v然后对 D 做一遍二维前缀和就得到操作后的原矩阵。这个四角操作的图形意义是在 (x1, y1) 加 v让从这个点开始的右下区域都加 v在右上角和左下角分别减 v把超出矩形范围的区域消掉但右上、左下两个区域会被减去两次所以右下角要加回来一次。这跟前缀和查询时的容斥是完全对称的。二维差分代码范式vectorvectorlong long d(n 2, vectorlong long(m 2, 0)); auto add [](int x1, int y1, int x2, int y2, long long v) { d[x1][y1] v; d[x21][y1] - v; d[x1][y21] - v; d[x21][y21] v; }; // 多次调用 add 修改 // 最后二维前缀和还原 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]; } }很多人在写二维差分时会犯一个经典错误忘记数组要开 n2 和 m2导致处理 x21 或 y21 时下标越界。为什么是 2 而不是 1因为修改时可能用到 x21而且做前缀和还原的时候i-1 位置也要能从 0 开始。实际上把第 0 行、第 0 列全留空再把第 n1 行、第 m1 列用来承接边界派生出的“抵消”是最稳妥的做法。宁可多开一点也不要越界这是基本功。二维差分还有一个常见的坑把修改和还原混在一起。很多人做一次修改就对整个矩阵做一次前缀和那复杂度又变回 O(nm) 了。正确的做法是先攒下所有修改用 O(1) 的四角法更新差分矩阵最后一次性做前缀和还原。差分的意义就在于“区间修改可以延迟到最后统一结算”这是它和直接修改最大的区别。3. 前缀和与差分的组合应用与信奥实战3.1 树状数组让前缀和与差分支持动态更新前面讨论的前缀和与差分都局限于“数组是静态的”预处理完后修改很少。但实际题目中经常出现“既有点修改又有区间查询”的动态场景比如洛谷模板题里的树状数组 1、树状数组 2。树状数组Fenwick Tree就是在这个需求下出现的它能维护一个数组支持单点修改和前缀和查询两者都能做到 O(log n)。拿一个非常经典的问题来理解树状数组维护一个长度为 n 16 的序列支持查询前缀和 sum(11)以及单点修改 add(3, x)。如果用普通数组查询前缀和要 O(n)修改只要 O(1)。用它反复来回操作整体还是 O(nq)。树状数组的做法是用一个树状结构把前缀和“分段存储”每个位置存的是某个 lowbit 区间上的和。lowbit(x) 定义是 x 的二进制表示里最低位的 1 所对应的数值比如 lowbit(6) 2因为 6 的二进制是 110最低位 1 对应的值是 2。query(11) 的流程是反复累加 tree[11]、tree[10]、tree[8]直到下标变成 0。11 的二进制是 1011lowbit(11) 1所以 11 - 101010lowbit(10) 2所以 10 - 81000lowbit(8) 8所以 8 - 0。查询是 O(log n)。单点修改 add(3, x) 则是从下标 3 开始不断向上更新父节点3 - 4 - 8 - 16每次 tree[下标] x直到超过 n。这也正好 O(log n)。如果想查区间和就用前缀和相减sum(r) - sum(l-1)。树状数组最巧妙的点在于它和差分可以嵌套使用如果想支持“区间修改 区间查询”只靠一棵树状数组不够因为区间修改如果用差分来转差分数组的每次单点修改对应原数组的区间影响而原来的前缀和查询会收到两棵树的共同影响。具体做法是维护两棵 BIT一棵维护差分数组 d[i]另一棵维护 i*d[i]。区间 [l,r] 加 v 时在两棵 BIT 上各做两次单点修改查询前缀和时用 (sum1 * x - sum2) 这种形式计算。这就是经典的“区间修改 区间查询”的双树状数组写法。struct Fenwick { int n; vectorlong long c; Fenwick(int size) : n(size), c(size 1, 0) {} void add(int pos, long long val) { for (; pos n; pos pos -pos) c[pos] val; } long long sum(int pos) { long long res 0; for (; pos 0; pos - pos -pos) res c[pos]; return res; } };我特意把 lowbit 写成pos -pos这是位运算写法也是最常见的写法。手动模拟一次sum(11)你会发现它比直接遍历 11 个数要快得多而且不受数组长度影响只和长度相关的二进制位数有关。信奥里面树状数组的常数比线段树小很多代码也短能处理绝大多数需要动态区间求和的问题。唯一的痛点是它天生只能处理前缀信息遇见区间最大值之类就不方便了那就要请出线段树。但至少在“前缀和与差分动态化”这个场景树状数组几乎是标准答案。3.2 经典题型拆解从“借教室”到“差分前缀和还原”差分最常见的出题套路是给你一堆区间每个区间都让某个统计量 1最后问每个点的实际情况。经典题有“种树”“铺地毯”“挤牛奶”等。我的建议是遇到这种题不要犹豫直接往差分上想。举个例子一个有 n 个房间的公寓m 个租房请求每个请求从第 l 天到第 r 天租住每天需要一个房间问有没有哪天房间不够用。这类题盯着“区间加 1”这个操作差分数组维护每个时间点的增量所有请求处理完后做前缀和就能得到每一天的占用房间数和房间总数比较即可。复杂度 O(n m)如果用暴力去每一天查占用就变成 O(nm)显然不现实。还有一类题是“差分 二分答案”比如经典的“借教室”题。它的操作是依次处理若干个区间减 1 的订单一旦某天教室数量变成负数就停。最容易想到的办法是每次都去区间暴力减那肯定超时。更稳的思路是二分答案判断前 k 个订单能否执行。check(k) 时只对前 k 个订单做差分区间减然后一次前缀和还原看看哪天会变负。每个 check 是 O(n k)二分要 O(log m) 次总复杂度 O((n m) log m)完全能过。这算把差分从一个“小技巧”升级成了“算法框架中的核心组件”。3.3 复杂度与空间取舍什么时候能用什么时候不能用选了前缀和或差分代价是什么空间。一维前缀和需要额外 O(n)二维需要 O(nm)。如果 n 和 m 本身都到 10^6那你必须考虑内存够不够。有时候题目卡内存你就要想能不能用滚动数组、原地修改或者离散化缩小范围。举个例子差分数组完全可以在原数组上做先把原数组当成全 0区间修改都打在差分上最后原数组本身变成“还原后的结果”。这样只用一份内存不需要额外开一个“最终结果数组”。但还有一个更隐蔽的限制前缀和依赖的信息必须满足“可减性”。像是求和、求异或和、求布尔值和这种可以整体与部分互相抵消的运算都能前缀化。但“最大值”“最小值”这种没法通过“减掉前面一部分”得到后面一部分的信息就不能直接用普通前缀和。这类问题要么用线段树要么用稀疏表等其他数据结构。我见过不少初学者学会了前缀和就什么题都想硬套结果误判了题意。你要记住前缀和是个“减法型”工具不是“全局型”工具。差分的限制则正好相反它要求你的操作是“区间整体加减同一个常数”而且这种加减在预处理期间不会产生“交叉影响”需要即时反馈。如果修改是“区间赋值成某值”而不是“加某值”差分就帮不上忙了因为赋值破坏可逆性。好在大部分竞赛题里加减操作是主流差分用得飞起。4. 实操中的常见问题与避坑经验4.1 下标从 0 还是从 1一个能省半天调试时间的选择这是一个看起来小、影响却极大的决策。我的建议很直接算法题里涉及前缀和、差分的场景一律从 1 开始存储数组把 0 位置空出来当哨兵。为什么因为 S[0] 0 可以让 [1, r] 的查询公式 S[r] - S[0] 不用特判差分的 b[1] a[1] 也不用特殊处理。二维里第 0 行、第 0 列全 0 的价值更明显每一条递推公式都能无脑套。如果你非要从 0 开始前缀和公式会变成 S[r1] - S[l]差分的话要处理 b[0] a[0] 这个“无中生有”的边界还要时刻注意 r1 是否会越界。我不是说从 0 开始写不了而是说从 1 开始能少想很多边界条件。在你还没有形成“下标偏移”的肌肉记忆之前从 1 开始是最不容易出错的选择。刷题群里你去看老选手的代码绝大多数前缀和题都是这么写的。4.2 溢出、负数与取模细节决定的 0 分与 100 分前缀和和差分最大的数值风险是“中间结果溢出”。差分数组在多次区间加之后某个位置的值可能是很大的数再做前缀和还原时更可能溢出。我的建议是无脑用 long long除非你明确知道数据范围非常小。有些题还会要求取模这个时候更要注意负数问题差分中做减法比如 b[r1] - v之后前缀和还原过程中可能出现负数。标准写法是在每次运算后加 mod 再取模避免出负数。举例diff[r1] - v 之后如果后面要直接做前缀和并用模运算最好写成(d[i] mod - v) % mod;虽然这不影响差分本身的正负但是如果你最后要对原数组取模那么差分累积过程中的负值会通过加法传递必须时刻保证每一步都在 [0, mod) 范围内。不少选手在这个环节吃过亏明明样例能过大数据一提交就 WA检查半天发现是负数取模的问题。4.3 二维操作最易错的四个点二维前缀和和二维差分的坑比一维多得多。我总结了四个最容易踩的第一数组开小了。前面反复强调二维差分需要 n2 行 m2 列因为修改操作会用到 x21、y21从 1 开始编号时这俩值最大值就是 n1、m1数组少一位就越界。第二还原差分时把公式抄错。还原的二维前缀和公式是d[i][j] d[i-1][j] d[i][j-1] - d[i-1][j-1]有人会漏掉中间的减号。第三查询矩形范围搞反。对 (x1,y1) 到 (x2,y2)正确的容斥下标是 x1-1、y1-1、x2、y2写成别的就会得到完全错误的结果。第四把修改和还原混在一起。有些人每做一次区间修改就暴力跑一边前缀和复杂度全毁。真正写法是攒修改、最后还原前面多次提到实际操作时特别容易犯。我建议初学二维部分时拿一个 3x3 的小矩阵手算一遍把数组下标和公式每一项对应关系写出来。写一次比看十遍都管用。等你完全理解了那个容斥逻辑再去写代码就不会只是“背模板”了。4.4 树状数组与差分结合的边界细节树状数组和差分结合时有个容易忽略的问题两棵树状数组的大小定义。如果原数组长度是 n区间修改时你要在差分数组的 r1 位置减 v此时 r1 可能等于 n1。树状数组内部 add 操作的循环条件是pos n如果 pos 超过 n 就更新不了这个“减 v”就丢失了。但这个时候其实无所谓因为前缀和查询只查到 n永远不会去查 n1 以后的位置在 r1 减 v 的操作本来就是多余的。所以你可以选择不处理它或者专门处理成if (r1 n) add(r1, -v)。两种逻辑都该在心里有个数不然你在调试时会很困惑为什么 add 传了一个 n1 进去树状数组却没反应还有一个细节两棵 BIT 维护 i*d[i] 时i 是原数组下标d[i] 是差分值。区间修改对第二棵树的影响是add(l, v*l)、add(r1, -v*(r1))。这里 v 和下标相乘也要尽量用 long long不然又是一个隐蔽的溢出点。4.5 从“会模板”到“会思路”我的个人刷题心得前缀和与差分看起来是小知识点但它们其实是“逆运算思维”的启蒙你看到一个数组不仅可以直接操作它还可以换一个视角通过操作它的差分来间接完成目标。这种思维迁移到很多领域都有用。比如在图像处理里“积分图”就是二维前缀和的应用让任意矩形区域的像素和能被 O(1) 查询在统计区间覆盖次数时差分的思路也比直接遍历高效得多。我甚至觉得如果你能彻底理解“差分是前缀和的逆运算”这一句话很多算法题就不再需要死记硬背模板了。就我个人经验来说遇到一个新题型我会先问自己三个问题能不能转化成区间加减能不能转换成前缀和查询能不能用差分延迟计算这三个问题任何一个是“能”题目基本就破解一半了。反之如果你对一个题目完全没有思路先往这三个方向想往往也能打开局面。这个习惯是我刷了上百道题之后才慢慢养成的如果你刚接触可以直接把这三个问题当“ checklist”用。到了这里前缀和与差分的核心内容就全讲完了。代码不多但每一个模板背后都有值得琢磨的推导过程。希望你不要只背代码而是真的拿笔在草稿纸上推一遍把差分数组前缀化还原成原数组感受一下“逆运算”的美妙。下次再遇到区间修改和区间查询你就知道用不上那些花里胡哨的数据结构前缀和与差分就够你走得非常远了。