1. 为什么说差分算法是Java选手的“默认答案”做Java算法题尤其是准备蓝桥杯和面试手撕算法时区间操作几乎一定会遇到一个数组反复让你把某个范围内的所有数字加上一个值最后再把数组输出。暴力循环写法很简单可数据量一大就是灾难这时候最该第一个想到的就是差分算法。差分算法在Java里实现特别简洁不需要额外引入复杂数据结构核心就只有三四句代码却能从容搞定一维、二维甚至树上的区间更新问题。这篇文章写给准备蓝桥杯Java组、刷LeetCode或牛客、复习Java基础数据结构的读者我会从一维差分的原理讲到二维模板再给三个能直接跑的案例最后把踩过的坑一次说清楚。1.1 一个高频场景区间修改、最后查询以最常见的一维数组为例。假设数组长度 n1000000操作次数 m100000每一次操作都给出 l、r、v要求把 arr[l] 到 arr[r] 全部加 v。如果每次真的用循环去跑平均区间长度可能几十万最坏要执行约 1e11 次加法在Java里几乎不可能通过。而差分数组能用 O(1) 时间完成一次区间加最后用 O(n) 时间还原总复杂度从 O(n*m) 降到 O(nm)。这个性价比是很多高级数据结构也比不上的。你可能会问线段树不是也能做吗确实能但线段树代码量至少在五十行以上而且涉及建树、懒标记、区间更新、区间查询面试手写时很容易出细节错。这里不是贬低线段树而是说当题目只要求“最后统一输出”时用线段树属于杀鸡用牛刀。差分的代码量只有线段树的十分之一一次区间加只有两次端点修改几乎没有运行时的额外开销。1.2 差分和差分隐私没有关系搜索“差分算法”时经常有人把“差分隐私算法”一起搜出来。这里先明确一下本文讲的差分是一种数据结构思想在算法题里用来做区间批量更新差分隐私是另一种技术属于数据发布和隐私保护领域核心是往查询结果中加入噪声两者除了名字都带“差分”外没有关系。我去面试时曾遇到候选人把这两个概念混在一起场面很尴尬。所以如果你面试时被问到差分先确认面试官问的是算法模板还是隐私保护别答错方向。2. 一维差分公式、原理与可复用模板2.1 差分的定义与“端点记账”直觉设原数组为 a下标从 1 开始并规定 a[0]0。定义差分数组 dd[i] a[i] - a[i-1]比如 a [1,4,2,8]那么 d[1]1d[2]3d[3]-2d[4]6反过来对 d 做前缀和d[1] 等于 a1d[1]d[2] 等于 a2d[1]d[2]d[3] 等于 a3。所以 d 保存的是相邻元素的差值前缀和可以把它恢复成 a。这里有个很形象的类比a 是账户余额d 是每笔流水。我们希望知道某天余额不需要记每一天的具体余额只需要知道从开户日开始每天收入多少、支出多少然后逐日累加。差分数组就是这个流水账区间加就是给流水账加一笔“起始收入”和一笔“截止支出”。2.2 区间加操作的推导为什么是 r1现在要把 a[l..r] 每个数都加 v。我们先只改 d[l] v然后做前缀和从 d[l] 开始后面所有位置的前缀和都会多出一个 v。也就是说a[l]、a[l1]、a[l2]……直到数组末尾全都被加了 v。这显然不是我们想要的效果因为它影响到了 r 之后的位置。所以还要在 d[r1] - v。这样当前缀和累加到 r1 时前面多出来的 v 刚好被抵消。于是从 r1 开始前缀和又恢复正常。整段逻辑用一句话说就是左端点记一笔“加”右端点后面一格记一笔“减”最后统一求前缀和就能让修改只落在 [l,r] 区间内。这个“右端点1减掉”是差分算法里最核心、最反直觉的一个操作。一定要亲手推两遍而不是只背结论。我当年第一次学的时候也觉得多余直到自己拿小数组算了一遍才理解这是一个“截止记号”。2.3 Java代码从空数组到前缀和还原我的习惯是数组多开两个位置下标从1开始。n个元素diff长度至少n2这样当 rn 时diff[r1] 也就是 diff[n1] 仍可以安全写入不会越界。import java.util.*; public class Difference1D { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); long[] diff new long[n 2]; for (int i 0; i m; i) { int l sc.nextInt(); int r sc.nextInt(); long v sc.nextLong(); diff[l] v; diff[r 1] - v; } StringBuilder sb new StringBuilder(); for (int i 1; i n; i) { diff[i] diff[i - 1]; // 前缀和还原 if (i 1) sb.append( ); sb.append(diff[i]); } System.out.println(sb); } }这里直接用 diff 数组做了前缀和省得再开一个 result 数组。需要注意如果做的是“多组测试数据”每次 new 一个新的 diff 数组就好或者用 Arrays.fill 把 diff 清零千万别忘了上一组数据残留。2.4 原数组不是0时怎么初始化差分很多初学的人以为差分只能从全0数组开始。其实原数组 a 不为0时先对原数组求一次差分得到一个表示现状的 diff之后的区间加只需要继续在 diff 的端点做加减最后再做前缀和还原。这样不用拿原数组去做区间运算代码也很自然。long[] diff new long[n 2]; for (int i 1; i n; i) { diff[i] a[i] - a[i - 1]; // 先求原数组的差分 } // 之后的操作照旧diff[l] v; diff[r 1] - v; // 最后前缀和diff[i] diff[i - 1]结果就是更新后的a[i]实际比赛里很多题目初始就是全0直接用2.3的模板就行。但如果遇到初始数组有值或者题目要求“在已有数组上修改”这一小节的价值就体现出来了。3. 二维差分矩阵区间更新的“四角操作”3.1 二维前缀和的逆运算二维差分是二维前缀和的逆运算。二维前缀和公式大家应该熟悉s[i][j] a[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1]那么由二维数组 a 求差分 d 的公式就是反过来d[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]这个公式看起来复杂其实和一维一样d 存的是“当前位置相比左上一片区域的增量”。如果初始矩阵全0那差分矩阵也全0如果初始矩阵有值先按这个公式求一遍差分后面区间操作直接改 d最后再二维前缀和还原。二维下标同样从1开始更方便。否则处理 i-1、j-1 时还要写 if 判断代码会很啰嗦。3.2 子矩阵加 v 的四个端点若给以 (x1,y1) 为左上角、(x2,y2) 为右下角的子矩阵全部加 v需要对 d 做四次修改d[x1][y1] vd[x21][y1] - vd[x1][y21] - vd[x21][y21] v为什么是四角你可以把前缀和还原看成每个格子从左上角开始向下向右累加。在 (x1,y1) 加 v右方和下方整片都会被影响为了保证影响只落在目标子矩阵内需要在右边界外一列、下边界外一行分别设置“截止记号”再在右下角把重复多减的部分加回来。这就是容斥原理在差分里的体现。我第一次写二维差分时右下角那个加法总是忘结果矩阵右下角一大片区域全多加了 v。后来我养成了一个习惯假设目标区域只有 2x2 大小自己手动把四个端点的值列出来再一步步做前缀和跑一遍就彻底记住了。3.3 完整模板与边界处理二维差分输入量通常比一维大很多我建议直接用 BufferedReader StringTokenizerScanner 在十万级输入下容易超时。import java.io.*; import java.util.*; public class Difference2D { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); int m Integer.parseInt(st.nextToken()); int q Integer.parseInt(st.nextToken()); long[][] diff new long[n 2][m 2]; for (int k 0; k q; k) { st new StringTokenizer(br.readLine()); int x1 Integer.parseInt(st.nextToken()); int y1 Integer.parseInt(st.nextToken()); int x2 Integer.parseInt(st.nextToken()); int y2 Integer.parseInt(st.nextToken()); long v Long.parseLong(st.nextToken()); diff[x1][y1] v; diff[x2 1][y1] - v; diff[x1][y2 1] - v; diff[x2 1][y2 1] v; } StringBuilder sb new StringBuilder(); for (int i 1; i n; i) { for (int j 1; j m; j) { diff[i][j] diff[i - 1][j] diff[i][j - 1] - diff[i - 1][j - 1]; if (j 1) sb.append( ); sb.append(diff[i][j]); } sb.append(\n); } System.out.print(sb); } }注意 diff 数组开了 (n2) x (m2)因为 x21 可能等于 n1y21 可能等于 m1。还原时循环只到 n 和 m不会读取 n1 行的数据因此不会越界。3.4 为什么二维差分能省这么多时间假设一个 1000x1000 的矩阵执行 1000 次子矩阵加操作。暴力做法每次最多遍历 1e6 个格子总操作量约 1e9差分每次只动4个点最后遍历矩阵还原总操作量约 1e6 加 4000。差距是三个数量级。矩阵越大、操作次数越多差分的优势越明显。更关键的是暴力写法不仅慢代码里还容易出现下标错乱差分的四行端点修改是固定套路机械记忆即可正确率反而更高。4. 三个实战案例照着敲就能AC4.1 一维区间加手把手验证结果先用最初的一维例子。n5初始数组全0执行两次操作把 [2,4] 加 3把 [1,3] 加 5用上面的 Difference1D 跑输入样例5 2 2 4 3 1 3 5输出5 8 8 3 0手动验证一下位置1被第二个操作加5结果是5位置2和3同时被两个操作覆盖所以是8位置4只被第一个操作加3结果是3位置5不在任何操作区间内结果保持0。这个案例虽然简单但能帮你确认 diff[l]v 和 diff[r1]-v 的方向没有搞反。4.2 二维子矩阵加3x4小样例跑通用3行4列的零矩阵执行两次操作(1,1) 到 (2,2) 加 1(2,3) 到 (3,4) 加 2预期输出1 1 0 0 1 1 2 2 0 0 2 2输入格式3 4 2 1 1 2 2 1 2 3 3 4 2把这段输入放到 Difference2D 里运行应该能得到上面的矩阵。如果某个端点写错比如右下角那个加 v 忘了输出里右下角会多出一大片 2一眼就能发现问题。4.3 差分前缀和求最大重叠区间数这是差分数组非常经典的扩展应用给一批闭区间问任意时刻最多被多少个区间覆盖。不用逐个遍历区间内的点直接把每个区间 [l,r] 变成 diff[l]、diff[r1]--最后做前缀和。前缀和数组里每个位置的值就是该点被多少个区间覆盖求最大值即可。import java.util.*; public class MaxOverlap { public static void main(String[] args) { Scanner sc new Scanner(System.in); int t sc.nextInt(); int maxEnd 0; long[] diff new long[100005]; // 根据题目最大端点调整 while (t-- 0) { int l sc.nextInt(); int r sc.nextInt(); diff[l] 1; diff[r 1] - 1; maxEnd Math.max(maxEnd, r); } long cur 0, ans 0; for (int i 1; i maxEnd; i) { cur diff[i]; ans Math.max(ans, cur); } System.out.println(ans); } }输入样例3 1 3 2 5 4 6输出是 2。因为时间点2到5都有两个区间覆盖。这类题在蓝桥杯和日常笔试中很常见本质是把区间事件转换为端点事件这正是差分思想最迷人的地方。4.4 在蓝桥杯里怎么识别差分题蓝桥杯Java组里差分出现频率很高。题干通常会出现这些关键词“执行若干次区间加法”“把子矩阵都加上一个数”“最后输出数组/矩阵”。认准这几个关键字第一反应就应该是差分。还有一些题表面在问“某个位置的值是多少”实际只做一次全局查询也可以先用差分记录变化量再通过前缀和一次性回答。准备竞赛时差分、前缀和、二分、贪心这四个模板要滚瓜烂熟。差分是其中代码量最小、最容易检验的一个性价比极高。省赛时遇到区间操作别急着上线段树先想差分能不能解很多时候三分钟就能敲完。5. 常见问题与排查技巧5.1 为什么 diff 数组总是越界数组越界是新手最常踩的坑。一维操作中 l、r 都在 1 到 n 之间但如果 rnr1n1数组长度开成 n1 就不够用了下标 n1 越界。所以模板里统一开 n2。二维同理行和列都多开两格。我整理了一个常见错误对照表排查时可以直接对照错误现象正确做法diff 数组长度开成 n在 rn 时数组越界开 n2忘记前缀和还原输出结果完全不对for i1..n: diff[i] diff[i-1]二维右下角加号漏写矩阵右下大片多加了 v补上 diff[x21][y21] v用 Scanner 读百万级输入运行超时用 BufferedReaderStringTokenizer5.2 输出总不对大概率忘了前缀和还原diff[l] v; diff[r1] - v 之后diff 本身并不是最终数组。diff 只是“变化量”必须从左到右逐个累加也就是做前缀和才能还原出每个位置真正的结果。很多新手把 diff 数组直接输出当然看不到区间效果。调试时我习惯先打印 diff 数组再打印前缀和数组。比如上面 [2,4]3、[1,3]5 的例子操作结束后 diff 数组应该是 [5,3,0,-5,-3]从下标1开始前缀和才是 [5,8,8,3,0]。把中间态打出来问题一下就能定位。5.3 int 溢出和输入效率区间操作累加次数多了结果很容易超过 int 上限。长度为 1e6 的数组做 1e6 次 1最大结果可能到 1e12int 根本装不下。所以我模板里统一用 long别在这种地方交冤枉分。输入效率同样重要。一维输入量小Scanner 还能用但二维矩阵和十万级操作量下Scanner 的 nextInt/nextLong 会比较慢。建议用 BufferedReader StringTokenizer代码就多一两行性能却能提升一个档次。5.4 二维差分的容斥怎么记才不会错二维差分四角符号记不住我的方法是画一个 4x4 方格标记一个 2x2 目标区把四个端点的修改都写出来然后手算前缀和。三步下来就记住了。口诀是左上和右下是加右上和左下是减。这个减号来自二维前缀和公式里交叉项的符号理解了就不会混。如果实在怕记错写代码前可以先构造一个 3x3 的小矩阵心算一遍预期结果再跑一下模板。花一分钟验证比提交后白白丢分强得多。5.5 闭区间与开区间先确认题目定义大部分算法题是闭区间 [l,r]对应 diff[l]v、diff[r1]-v。但有些题目用的是左闭右开 [l,r)也就是包含 l、不包含 r此时右端点应该写作 diff[r]-v。二维同理看题目给的是闭区间还是开区间。蓝桥杯里大多是闭区间但面试题有时会故意写“半开半闭”。读题后先用小样例测边界不要默认它是怎么定义的。6. 从差分到线段树、树状差分一条学习主线6.1 差分能做什么不能做什么差分数组只适合“多次批量修改、最后统一查询”的场景。如果修改和查询交替出现每次都要求实时区间和那差分数组就无能为力了。这时候可以考虑树状数组或线段树树状数组可以理解成在差分数组基础上再做一层统计支持动态修改和区间查询线段树更通用能处理区间加、区间乘、区间最值等。面试时如果被问到“区间操作你会怎么选型”你可以顺着这条线回答一次性离线操作选差分动态单点改区间查选树状数组复杂更新选线段树。答出这条演进路线会比只背模板更有说服力。6.2 进阶方向树上差分再进一步是树上差分。比如统计每条边被多少条路径覆盖可以把一条从 s 到 t 的路径拆成 s 到 LCA、t 到 LCA 两条链在端点做标记最后 DFS 回溯时做累加。原理和数组差分完全一致只是把“线性前缀和”换成了“树上自底向上的累计”。这个概念在蓝桥杯国赛和部分面试算法轮偶尔出现现在不用深究知道有方向就行。先把一维和二维数组差分写熟再去看树上差分会顺手很多。6.3 工程场景里的差分从在线人数到计费差分思想在业务系统里也很常见。比如统计每个时刻直播间在线人数有人进来 1有人离开 -1如果手里有一批进入/离开区间用端点 1/-1 记录然后按时间排序累加就能得到全天人数曲线。再比如停车场各时段剩余车位、优惠券在某个区间内可用次数都属于同一模型。在日常开发里把“区间事件”转化成“端点事件”可以避开逐区间遍历的死循环。这也是为什么我觉得差分不仅仅是竞赛模板更是一种值得训练的思维方式。6.4 一个建议建立自己的算法模板库根据我个人的习惯算法模板一定要沉淀成自己的代码库。差分、前缀和、二分、并查集、DFS/BFS每个模板用熟后保存成一个类或一个文件做题时直接复用。这样在蓝桥杯考场上能节省大量时间。建议你把上面的一维和二维差分模板改成自己喜欢的变量命名和输入方案然后找几道区间操作的题反复测练到能盲打。我第一次学差分时觉得“d[r1]-v”特别反直觉总觉得是多余的一步直到自己用手算了五六个例子才真正理解它是一个“截止记号”。后来做二维差分我也没有硬背四角公式而是每次先画 3x3 矩阵手动验证。这个习惯让我的模板一直没写错过。希望你也别急着跳过推导亲手推一遍比背任何模板都管用。