到O(1)的区间操作优化)
每次在在线判题系统里看到“区间求和”四个字我都想起自己刚学算法时的狼狈逻辑一次全对但一提交就是 Time Limit Exceeded。后来才琢磨明白前缀和、差分这对互逆操作本质上是两种“时间管理术”——一个把重复劳动提前做完一个把批量修改攒到最后一口气释放。前缀和能把区间查询从 O(n) 压到 O(1)差分能把区间更新从 O(n) 压到 O(1)两者配合起来可以秒掉一大类区间问题。这篇文章不是把教科书定义抄一遍而是我在刷题、带新人和反复复盘之后沉淀下来的理解路径公式怎么推、二维怎么展开、哪些边界最坑、拿到题目怎么认出套路。1. 从超时现场出发前缀和是怎么一步步被“逼”出来的1.1 一个让萌新血压拉满的场景先看一道最朴素的题有一个长度为 n 的数组q 次询问每次给一个区间 [l, r]求区间内所有数字的和。n 和 q 都到 10^5 的规模时第一次写的人十有八九是这样的int l, r; cin l r; int sum 0; for (int i l; i r; i) sum a[i]; cout sum \n;逻辑没有错但复杂度是 O(nq)。10^5 × 10^5 等于 10^10也就是一百亿次加法。按每秒一亿次运算的保守估计这层循环要跑一百秒而在线评测系统往往只给一到两秒。这已经不是“有点慢”而是压根没法用。问题出在哪儿每次查询都把 [l, r] 重新加一遍可大部分区间是重叠的。前面算过的 a[1] 到 a[l-1] 这段每次查询都被人为重复消费。既然这样干脆把“从第 1 个位置到任意位置的总和”提前存好查询时用一次减法得到任意区间的和。这就是前缀和的核心动机——它不是魔法只是把重复劳动提前做完了。1.2 递推式与“为什么减的是 S[l-1]”定义前缀和数组 S长度为 n1令 S[0] 0递推关系是S[i] S[i-1] a[i]S[i] 的含义是 a[1] a[2] ... a[i] 的累计总和。预处理只需要一次 O(n) 的循环之后查询 [l, r] 时区间和 S[r] - S[l-1]这里 l-1 是最容易写错的地方。很多新手写成 S[r] - S[l]丢掉的是 a[l] 本身。可以通过生活类比来记前缀和像一本累计账本S[r] 是查到第 r 天的总消费想算第 l 天到第 r 天花了多少钱必须把前 l-1 天的账减掉。只减到第 l 天就把第 l 天的消费也扣了答案自然少了 a[l]。特别地当 l1 时S[l-1] 就是 S[0]。所以 S[0] 0 这个哨兵位不是可有可无的它让公式对所有的 l 都成立完全不用特判边界。1.3 一维前缀和的实现细节比赛里我习惯用“1 下标 多开一个位置”的写法能让所有公式零特判。C 长这样#include bits/stdc.h using namespace std; int main() { int n, q; cin n q; vectorint 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; }Python 版本类似n, q 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(q): l, r map(int, input().split()) print(s[r] - s[l - 1])如果题目给的是 0 下标数据我通常会先把数组前面塞一个 0再走 1 下标流程。这样查询部分一行都不用改只在读入时多一步非常省心。2. 差分把“区间更新”翻译成两次单点操作2.1 差分的定义前缀和的逆运算前缀和解决的是“静态查询”差分解决的是“批量区间更新”。什么是批量区间更新给 [l, r] 范围内的每个数统一加一个值而且可能要加很多轮最后才统一输出整个数组。暴力做法是每轮更新都扫一遍区间m 轮更新最坏就是 O(nm)。差分直接把思路反过来既然前缀和能从“差分数组”还原出原数组那么所有区间更新都不碰原数组只改差分数组的几个点最后收尾时做一次前缀和把所有修改一次性“压”回原数组。差分数组 d 的定义d[1] a[1] d[i] a[i] - a[i-1] (i 2)也就是说原数组是差分的“前缀和结果”a[i] a[i-1] d[i]。所以“前缀和”和“差分”是一对互逆操作一个负责压缩一个负责展开。理解这一层后面所有操作都顺理成章。2.2 区间加法的核心d[l]vd[r1]-v给 a[l..r] 全体加 v差分数组只需要两步d[l] v d[r1] - v为什么这样成立想象对差分数组做前缀和还原的过程d[l] 加了 v那么从 a[l] 开始后面所有位置的累计结果都会多出一个 vd[r1] 减了 v从 a[r1] 开始多出来的 v 又被抵消。两股“波”叠加之后只有 l 到 r 这一段净增加了 v区间之外完全不受影响。可以用轨道比喻来记忆在 l 号枕木下面垫高 v经过 l 之后再高的列车都会抬升 v再在 r1 号枕木下面挖掉 v经过 r1 后回落原高度。中间那一段整体抬升 v两端之外纹丝不动。2.3 手推一遍就会彻底明白拿一个短数组推荐新手都这样手动推一次。原数组取 [3, 7, 5, 2, 8]下标从 1 开始。先算原始差分d[1] 3 d[2] 7 - 3 4 d[3] 5 - 7 -2 d[4] 2 - 5 -3 d[5] 8 - 2 6现在执行“对区间 [2, 4] 全体加 2”d[2] 2 4 2 6 d[5] - 2 6 - 2 4更新后的差分数组是 [3, 6, -2, -3, 4]按 a[i] a[i-1] d[i] 还原a[1] 3 a[2] 3 6 9 a[3] 9 (-2) 7 a[4] 7 (-3) 4 a[5] 4 4 8最终数组是 [3, 9, 7, 4, 8]而原数组 [3, 7, 5, 2, 8] 给下标 2、3、4 各加 2 之后正是这个结果。手推过一遍d[l]v、d[r1]-v 这两个位置就再也忘不掉了。2.4 多轮更新后统一还原的“标准姿势”有一个非常经典的场景有 n 个位置m 组更新每组都是“区间 [l, r] 加 c”最后问每个位置的值。代码骨架是初始化 d 全部为 0 每读入一组 (l, r, c): d[l] c d[r1] - c 结束后: for i in 1..n: a[i] a[i-1] d[i]复杂度从 O(nm) 降到 O(nm)代码短到不可思议。这里有个容易忽略的细节d 数组的大小不是 n而是至少 n1。当 r 恰好等于 n 时d[r1] d[n1] 这个位置仍然要减 c只是后面没有元素了这个“尾巴”丢在数组末尾即可。用 1 下标的话建议直接开 n2省得每次都在脑子里纠结越界。提示差分数组本身存的是“相邻元素的差值”不是最终答案。很多人记不住最后那一次前缀和还原样例跑对了一到大数据就全错根因就是少了收尾步骤。3. 二维战场矩阵前缀和与二维差分的完整推导3.1 二维前缀和的容斥公式换成二维矩阵求任意子矩阵的和暴力就是四层循环n 和 m 到 500 以上基本就没戏。二维前缀和的思路是一维的自然推广预处理 S[i][j]表示从 (1,1) 到 (i,j) 这个大矩形里所有元素的和。递推式是S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] a[i][j]为什么要减 S[i-1][j-1]因为 S[i-1][j] 覆盖了 (1,1) 到 (i-1,j)S[i][j-1] 覆盖了 (1,1) 到 (i,j-1)这两个矩形在 (1,1) 到 (i-1,j-1) 的区域重复计算了一次必须减掉一个。这就是数学里的容斥多加的补回来多减的再加回去。查询左上角 (x1,y1)、右下角 (x2,y2) 的子矩阵和ans S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] S[x1-1][y1-1]记忆口诀右下角总和减掉上面一块减去左面一块再把左上角重复减掉的那块加回来。和一维的“S[r] - S[l-1]”对比一下规律完全一样只是从线段变成了矩形。3.2 二维差分四个点撑起一个矩形二维差分与一维同理只是从两个点变成四个点。给 (x1,y1) 到 (x2,y2) 的子矩阵整体加 v对差分矩阵 d 做四次修改d[x1][y1] v d[x21][y1] - v d[x1][y21] - v d[x21][y21] v这四个点的位置对应“矩形左上角加 v、右边界外一列减 v、下边界外一行减 v、右下角外一格的角落加 v”。最后做一次二维前缀和还原所有矩形叠加的效果就一次性展开到原矩阵上。这个技巧在“给一个大矩阵做很多次矩形加值、最后求最终矩阵”的题目里特别好用单次修改 O(1)收尾还原 O(nm)。3.3 二维实现代码骨架二维前缀和预处理和查询// s 初始为 0下标从 1 开始 for (int i 1; i n; i) for (int j 1; j m; j) s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j]; // 查询 (x1, y1) 到 (x2, y2) int ans s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1];二维差分更新与还原// 差分矩阵 d 全部初始化为 0 d[x1][y1] v; d[x21][y1] - v; d[x1][y21] - v; d[x21][y21] v; // 最后对 d 做二维前缀和还原 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]; // 此时 d 里存的就是每个格子的最终增量如果原矩阵本身有值就把最终增量加到原矩阵上。我个人的习惯是把“原矩阵”和“增量”分开写逻辑清晰出 bug 的概率比原地合并小得多。等熟练之后再合并也不迟。4. 实战中反复踩的坑下标、溢出与“边更新边查询”4.1 0 下标和 1 下标之间的混乱这是区间题里最典型的 WA 来源。0 下标数组上做一维前缀和查询 [l, r] 要写成s[r] - (l 0 ? 0 : s[l-1])做差分时更新 [l, r] 要写成d[l] v; d[r1] - v;此时 d 必须开 n1 大小因为 r1 最大可以取到 n也就是最后一个有效下标。而 1 下标版本里d 要开 n2因为 r1 最大可以取到 n1这个位置虽然超过数组语义范围但仍然要存储减掉的增量。两种方案都没有错错的是混着用。我在代码里会明确写注释“以下一律 1 下标”防止半夜改着改着就串味。4.2 溢出和取模前缀和累加的值很容易超出 int 范围。比如 n 10^5每个 a[i] 最大 10^9总和就达到 10^14int 早就爆了必须用 long long。差分也一样多轮区间更新在同一位置反复累加同样可能溢出开 long long 是最省心的习惯。如果是取模题前缀和要这样维护s[i] (s[i-1] a[i]) % MOD 查询 (s[r] - s[l-1] MOD) % MOD注意最后加的 MOD 不能省因为 s[r] 和 s[l-1] 都是取模后的值直接相减可能得到负数加上 MOD 再取模才能保证非负。4.3 “边更新边查询”不是前缀和的领地前缀和适合“静态查询”差分适合“把更新攒起来最后一次性还原”。如果操作序列里更新和查询交替出现比如“给 [l, r] 加 v然后立刻问 [l, r] 的和”每次更新之后前缀和数组就失效了重建又要 O(n)复杂度直接退回原点。这种动态区间问题应该交给树状数组或线段树这类支持单次 O(log n) 修改和查询的数据结构。这个边界很多人一开始分不清结果拿着一维差分硬套动态题样例过了、大数据挂了然后又回来怀疑自己差分写错了。其实不是写错是工具选错了。判断标准很简单更新和查询是分开的两个阶段用差分两件事交错进行换树状数组或线段树。5. 识别套路看到什么特征用前缀和看到什么特征用差分5.1 前缀和的常见变形前缀和最经典的应用就是“子数组和为 k 的计数”。维护前缀和 S配合哈希表统计每个前缀和值出现的次数遍历到 i 时查一下 S[i] - k 在之前出现过多少次累加进答案。核心思维从“区间和”变成“两段前缀和之差”一个非常自然的迁移。异或区间也是一个方向异或运算的“逆运算”就是自己区间异或值等于 p[r] ^ p[l-1]不需要额外维护逆元天然适配前缀和思想。乘积前缀和则要小心 0 的存在0 会让除法逆元失效不能简单用“总乘积除以区间外乘积”得分段处理或换维护方式。二维前缀和的应用就更广了图像区域均值、矩阵多次矩形求和都是同一套容斥公式。只要题目里出现“子矩阵的和”并且矩阵是静态的第一反应就应该是它。5.2 差分的常见变形差分的经典场景是区间覆盖次数统计有 m 条线段每条覆盖 [l, r]问每个点被多少条线段覆盖。做法是d[l]、d[r1]--最后做一次前缀和还原每个位置的累计值就是覆盖次数复杂度 O(nm)。另一个常见变形是“给初始全 0 的数组做 m 次区间加求最终数组”这是差分最直白的用途。二维差分则对应矩形区域加值、地图增益叠加、棋盘覆盖等问题。还有一个隐蔽考点差分数组还原时必须在原地或新数组上做严格从左到右、从上到下的前缀和顺序错了结果全乱但这类 bug 又不会在样例里暴露非常阴险。5.3 一张快速判断表题目特征首选方案复杂度静态数组 大量区间和查询一维前缀和预处理 O(n)查询 O(1)大量区间更新 最后一次性输出数组差分更新 O(1)还原 O(n)矩阵 大量子矩阵求和二维前缀和预处理 O(nm)查询 O(1)矩阵 大量矩形加值 最后求终值二维差分更新 O(1)还原 O(nm)更新、查询交替出现的动态区间问题树状数组 / 线段树单次 O(log n)这张表是我拿到区间题之后的第一反应。先问自己数据是静态还是动态操作是更新多还是查询多更新与查询是否分阶段往往几秒钟就能定方向。最后说点我自己的习惯。很多人学前缀和和差分上来就背公式结果换一道题就歇菜。我的做法是先在小本子上手推一个小数组比如 3、7、5、2、8 这种长度不超过 5 的把差分数组写出来加一轮更新再还原回去亲眼看到每个数字怎么变化。推过两三遍之后l-1 和 r1 这两个位置就再也不会错。二维的时候用 3×3 的矩阵再推一遍容斥的四个角配合图形看理解速度远快于直接背公式。这套“手推小样例”的习惯我在带新人的时候反复强调也是我自己认为性价比最高的学习方法。 
长河君 · 2026/10/17 16:33:04 · 阅读 1.2k 前缀和与差分详解：从O(n)到O(1)的区间操作优化
每次在在线判题系统里看到“区间求和”四个字我都想起自己刚学算法时的狼狈逻辑一次全对但一提交就是 Time Limit Exceeded。后来才琢磨明白前缀和、差分这对互逆操作本质上是两种“时间管理术”——一个把重复劳动提前做完一个把批量修改攒到最后一口气释放。前缀和能把区间查询从 O(n) 压到 O(1)差分能把区间更新从 O(n) 压到 O(1)两者配合起来可以秒掉一大类区间问题。这篇文章不是把教科书定义抄一遍而是我在刷题、带新人和反复复盘之后沉淀下来的理解路径公式怎么推、二维怎么展开、哪些边界最坑、拿到题目怎么认出套路。1. 从超时现场出发前缀和是怎么一步步被“逼”出来的1.1 一个让萌新血压拉满的场景先看一道最朴素的题有一个长度为 n 的数组q 次询问每次给一个区间 [l, r]求区间内所有数字的和。n 和 q 都到 10^5 的规模时第一次写的人十有八九是这样的int l, r; cin l r; int sum 0; for (int i l; i r; i) sum a[i]; cout sum \n;逻辑没有错但复杂度是 O(nq)。10^5 × 10^5 等于 10^10也就是一百亿次加法。按每秒一亿次运算的保守估计这层循环要跑一百秒而在线评测系统往往只给一到两秒。这已经不是“有点慢”而是压根没法用。问题出在哪儿每次查询都把 [l, r] 重新加一遍可大部分区间是重叠的。前面算过的 a[1] 到 a[l-1] 这段每次查询都被人为重复消费。既然这样干脆把“从第 1 个位置到任意位置的总和”提前存好查询时用一次减法得到任意区间的和。这就是前缀和的核心动机——它不是魔法只是把重复劳动提前做完了。1.2 递推式与“为什么减的是 S[l-1]”定义前缀和数组 S长度为 n1令 S[0] 0递推关系是S[i] S[i-1] a[i]S[i] 的含义是 a[1] a[2] ... a[i] 的累计总和。预处理只需要一次 O(n) 的循环之后查询 [l, r] 时区间和 S[r] - S[l-1]这里 l-1 是最容易写错的地方。很多新手写成 S[r] - S[l]丢掉的是 a[l] 本身。可以通过生活类比来记前缀和像一本累计账本S[r] 是查到第 r 天的总消费想算第 l 天到第 r 天花了多少钱必须把前 l-1 天的账减掉。只减到第 l 天就把第 l 天的消费也扣了答案自然少了 a[l]。特别地当 l1 时S[l-1] 就是 S[0]。所以 S[0] 0 这个哨兵位不是可有可无的它让公式对所有的 l 都成立完全不用特判边界。1.3 一维前缀和的实现细节比赛里我习惯用“1 下标 多开一个位置”的写法能让所有公式零特判。C 长这样#include bits/stdc.h using namespace std; int main() { int n, q; cin n q; vectorint 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; }Python 版本类似n, q 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(q): l, r map(int, input().split()) print(s[r] - s[l - 1])如果题目给的是 0 下标数据我通常会先把数组前面塞一个 0再走 1 下标流程。这样查询部分一行都不用改只在读入时多一步非常省心。2. 差分把“区间更新”翻译成两次单点操作2.1 差分的定义前缀和的逆运算前缀和解决的是“静态查询”差分解决的是“批量区间更新”。什么是批量区间更新给 [l, r] 范围内的每个数统一加一个值而且可能要加很多轮最后才统一输出整个数组。暴力做法是每轮更新都扫一遍区间m 轮更新最坏就是 O(nm)。差分直接把思路反过来既然前缀和能从“差分数组”还原出原数组那么所有区间更新都不碰原数组只改差分数组的几个点最后收尾时做一次前缀和把所有修改一次性“压”回原数组。差分数组 d 的定义d[1] a[1] d[i] a[i] - a[i-1] (i 2)也就是说原数组是差分的“前缀和结果”a[i] a[i-1] d[i]。所以“前缀和”和“差分”是一对互逆操作一个负责压缩一个负责展开。理解这一层后面所有操作都顺理成章。2.2 区间加法的核心d[l]vd[r1]-v给 a[l..r] 全体加 v差分数组只需要两步d[l] v d[r1] - v为什么这样成立想象对差分数组做前缀和还原的过程d[l] 加了 v那么从 a[l] 开始后面所有位置的累计结果都会多出一个 vd[r1] 减了 v从 a[r1] 开始多出来的 v 又被抵消。两股“波”叠加之后只有 l 到 r 这一段净增加了 v区间之外完全不受影响。可以用轨道比喻来记忆在 l 号枕木下面垫高 v经过 l 之后再高的列车都会抬升 v再在 r1 号枕木下面挖掉 v经过 r1 后回落原高度。中间那一段整体抬升 v两端之外纹丝不动。2.3 手推一遍就会彻底明白拿一个短数组推荐新手都这样手动推一次。原数组取 [3, 7, 5, 2, 8]下标从 1 开始。先算原始差分d[1] 3 d[2] 7 - 3 4 d[3] 5 - 7 -2 d[4] 2 - 5 -3 d[5] 8 - 2 6现在执行“对区间 [2, 4] 全体加 2”d[2] 2 4 2 6 d[5] - 2 6 - 2 4更新后的差分数组是 [3, 6, -2, -3, 4]按 a[i] a[i-1] d[i] 还原a[1] 3 a[2] 3 6 9 a[3] 9 (-2) 7 a[4] 7 (-3) 4 a[5] 4 4 8最终数组是 [3, 9, 7, 4, 8]而原数组 [3, 7, 5, 2, 8] 给下标 2、3、4 各加 2 之后正是这个结果。手推过一遍d[l]v、d[r1]-v 这两个位置就再也忘不掉了。2.4 多轮更新后统一还原的“标准姿势”有一个非常经典的场景有 n 个位置m 组更新每组都是“区间 [l, r] 加 c”最后问每个位置的值。代码骨架是初始化 d 全部为 0 每读入一组 (l, r, c): d[l] c d[r1] - c 结束后: for i in 1..n: a[i] a[i-1] d[i]复杂度从 O(nm) 降到 O(nm)代码短到不可思议。这里有个容易忽略的细节d 数组的大小不是 n而是至少 n1。当 r 恰好等于 n 时d[r1] d[n1] 这个位置仍然要减 c只是后面没有元素了这个“尾巴”丢在数组末尾即可。用 1 下标的话建议直接开 n2省得每次都在脑子里纠结越界。提示差分数组本身存的是“相邻元素的差值”不是最终答案。很多人记不住最后那一次前缀和还原样例跑对了一到大数据就全错根因就是少了收尾步骤。3. 二维战场矩阵前缀和与二维差分的完整推导3.1 二维前缀和的容斥公式换成二维矩阵求任意子矩阵的和暴力就是四层循环n 和 m 到 500 以上基本就没戏。二维前缀和的思路是一维的自然推广预处理 S[i][j]表示从 (1,1) 到 (i,j) 这个大矩形里所有元素的和。递推式是S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] a[i][j]为什么要减 S[i-1][j-1]因为 S[i-1][j] 覆盖了 (1,1) 到 (i-1,j)S[i][j-1] 覆盖了 (1,1) 到 (i,j-1)这两个矩形在 (1,1) 到 (i-1,j-1) 的区域重复计算了一次必须减掉一个。这就是数学里的容斥多加的补回来多减的再加回去。查询左上角 (x1,y1)、右下角 (x2,y2) 的子矩阵和ans S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] S[x1-1][y1-1]记忆口诀右下角总和减掉上面一块减去左面一块再把左上角重复减掉的那块加回来。和一维的“S[r] - S[l-1]”对比一下规律完全一样只是从线段变成了矩形。3.2 二维差分四个点撑起一个矩形二维差分与一维同理只是从两个点变成四个点。给 (x1,y1) 到 (x2,y2) 的子矩阵整体加 v对差分矩阵 d 做四次修改d[x1][y1] v d[x21][y1] - v d[x1][y21] - v d[x21][y21] v这四个点的位置对应“矩形左上角加 v、右边界外一列减 v、下边界外一行减 v、右下角外一格的角落加 v”。最后做一次二维前缀和还原所有矩形叠加的效果就一次性展开到原矩阵上。这个技巧在“给一个大矩阵做很多次矩形加值、最后求最终矩阵”的题目里特别好用单次修改 O(1)收尾还原 O(nm)。3.3 二维实现代码骨架二维前缀和预处理和查询// s 初始为 0下标从 1 开始 for (int i 1; i n; i) for (int j 1; j m; j) s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j]; // 查询 (x1, y1) 到 (x2, y2) int ans s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1];二维差分更新与还原// 差分矩阵 d 全部初始化为 0 d[x1][y1] v; d[x21][y1] - v; d[x1][y21] - v; d[x21][y21] v; // 最后对 d 做二维前缀和还原 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]; // 此时 d 里存的就是每个格子的最终增量如果原矩阵本身有值就把最终增量加到原矩阵上。我个人的习惯是把“原矩阵”和“增量”分开写逻辑清晰出 bug 的概率比原地合并小得多。等熟练之后再合并也不迟。4. 实战中反复踩的坑下标、溢出与“边更新边查询”4.1 0 下标和 1 下标之间的混乱这是区间题里最典型的 WA 来源。0 下标数组上做一维前缀和查询 [l, r] 要写成s[r] - (l 0 ? 0 : s[l-1])做差分时更新 [l, r] 要写成d[l] v; d[r1] - v;此时 d 必须开 n1 大小因为 r1 最大可以取到 n也就是最后一个有效下标。而 1 下标版本里d 要开 n2因为 r1 最大可以取到 n1这个位置虽然超过数组语义范围但仍然要存储减掉的增量。两种方案都没有错错的是混着用。我在代码里会明确写注释“以下一律 1 下标”防止半夜改着改着就串味。4.2 溢出和取模前缀和累加的值很容易超出 int 范围。比如 n 10^5每个 a[i] 最大 10^9总和就达到 10^14int 早就爆了必须用 long long。差分也一样多轮区间更新在同一位置反复累加同样可能溢出开 long long 是最省心的习惯。如果是取模题前缀和要这样维护s[i] (s[i-1] a[i]) % MOD 查询 (s[r] - s[l-1] MOD) % MOD注意最后加的 MOD 不能省因为 s[r] 和 s[l-1] 都是取模后的值直接相减可能得到负数加上 MOD 再取模才能保证非负。4.3 “边更新边查询”不是前缀和的领地前缀和适合“静态查询”差分适合“把更新攒起来最后一次性还原”。如果操作序列里更新和查询交替出现比如“给 [l, r] 加 v然后立刻问 [l, r] 的和”每次更新之后前缀和数组就失效了重建又要 O(n)复杂度直接退回原点。这种动态区间问题应该交给树状数组或线段树这类支持单次 O(log n) 修改和查询的数据结构。这个边界很多人一开始分不清结果拿着一维差分硬套动态题样例过了、大数据挂了然后又回来怀疑自己差分写错了。其实不是写错是工具选错了。判断标准很简单更新和查询是分开的两个阶段用差分两件事交错进行换树状数组或线段树。5. 识别套路看到什么特征用前缀和看到什么特征用差分5.1 前缀和的常见变形前缀和最经典的应用就是“子数组和为 k 的计数”。维护前缀和 S配合哈希表统计每个前缀和值出现的次数遍历到 i 时查一下 S[i] - k 在之前出现过多少次累加进答案。核心思维从“区间和”变成“两段前缀和之差”一个非常自然的迁移。异或区间也是一个方向异或运算的“逆运算”就是自己区间异或值等于 p[r] ^ p[l-1]不需要额外维护逆元天然适配前缀和思想。乘积前缀和则要小心 0 的存在0 会让除法逆元失效不能简单用“总乘积除以区间外乘积”得分段处理或换维护方式。二维前缀和的应用就更广了图像区域均值、矩阵多次矩形求和都是同一套容斥公式。只要题目里出现“子矩阵的和”并且矩阵是静态的第一反应就应该是它。5.2 差分的常见变形差分的经典场景是区间覆盖次数统计有 m 条线段每条覆盖 [l, r]问每个点被多少条线段覆盖。做法是d[l]、d[r1]--最后做一次前缀和还原每个位置的累计值就是覆盖次数复杂度 O(nm)。另一个常见变形是“给初始全 0 的数组做 m 次区间加求最终数组”这是差分最直白的用途。二维差分则对应矩形区域加值、地图增益叠加、棋盘覆盖等问题。还有一个隐蔽考点差分数组还原时必须在原地或新数组上做严格从左到右、从上到下的前缀和顺序错了结果全乱但这类 bug 又不会在样例里暴露非常阴险。5.3 一张快速判断表题目特征首选方案复杂度静态数组 大量区间和查询一维前缀和预处理 O(n)查询 O(1)大量区间更新 最后一次性输出数组差分更新 O(1)还原 O(n)矩阵 大量子矩阵求和二维前缀和预处理 O(nm)查询 O(1)矩阵 大量矩形加值 最后求终值二维差分更新 O(1)还原 O(nm)更新、查询交替出现的动态区间问题树状数组 / 线段树单次 O(log n)这张表是我拿到区间题之后的第一反应。先问自己数据是静态还是动态操作是更新多还是查询多更新与查询是否分阶段往往几秒钟就能定方向。最后说点我自己的习惯。很多人学前缀和和差分上来就背公式结果换一道题就歇菜。我的做法是先在小本子上手推一个小数组比如 3、7、5、2、8 这种长度不超过 5 的把差分数组写出来加一轮更新再还原回去亲眼看到每个数字怎么变化。推过两三遍之后l-1 和 r1 这两个位置就再也不会错。二维的时候用 3×3 的矩阵再推一遍容斥的四个角配合图形看理解速度远快于直接背公式。这套“手推小样例”的习惯我在带新人的时候反复强调也是我自己认为性价比最高的学习方法。