东予薏米差分算法（Java）这个问题，最近连续被好几个正在备赛蓝桥杯的读者问到。我猜很多人搜这个词的时机，和当初的我很像：面对“区间加、区间减、最后求整个数组”这种题，第一反应写个 for 循环，结果被数据范围直接教做人。差分就是用来根治这个问题的：它是前缀和的逆运算，能把一次区间修改从 O(n) 压到 O(1)，非常适合“先批量修改、后统一查询”的场景。这篇文章我从原理讲起，给出一维、二维的完整 Java 模板，分析蓝桥杯和面试怎么考，再复盘几个我实际踩过的坑，最后用两道练手题带你把模板跑起来。适合准备蓝桥杯 Java 组、面试算法题，或者想系统补一下基础算法的人。另外提醒一句，网上常被一起搜到的“差分隐私算法”，和本文的差分数组完全是两回事，那个属于数据隐私保护领域，不要混淆。
1. 差分算法到底解决什么问题
1.1 先从最常见的场景说起
假设有一个长度为 n 的数组，初始全是 0，然后给你 m 次操作，每次把区间 [l, r] 内的所有元素统一加上一个值 v。操作做完之后，你要输出数组中每个位置的最终值。
最直觉的做法当然是暴力：每次 for 循环从 l 走到 r，逐个加 v。这个做法的时间复杂度是 O(n*m)。如果 n 和 m 都是 10^5，那就是 10^10 级别，Java 跑完基本要几十秒，在蓝桥杯和面试笔试题里属于必挂的写法。
差分的做法很巧妙：不再直接改原数组，而是开一个“差分数组”，把“区间修改”转换成“两个点的修改”。每次操作时，只需要在差分数组的两个位置做加减法，所有操作记录完之后，再做一次前缀和，就能还原出每个位置的最终值。
我特别喜欢用一个生活化的类比来解释。给一栋楼的 3 层到 6 层统一上调物业费，不需要一户一户上门改合同，物业只需要在自己的账本上记一笔“从 3 层开始，每户每月多收 20 元；从 7 层开始，每户每月少收 20 元”。到了月底结算时，从 1 层往上顺一遍账，每个人该交多少钱就全出来了。这个“账本”就是差分数组，“顺一遍”就是求前缀和。
1.2 差分和前缀和是天生一对
要理解差分，先得知道前缀和。给定数组 a，定义 pre[i] = a[1] + a[2] + ... + a[i]，这个 pre 数组就是 a 的前缀和。前缀和的用途是快速求某一段的和：sum(l, r) = pre[r] - pre[l-1]。
差分是反过来的操作：给定数组 a，构造 b，使得 b[i] = a[i] - a[i-1]。对 b 再做一次前缀和，就能还原出 a。所以说，差分是前缀和的逆运算，就像乘法和除法的关系那样。
这个“互逆”的理解很重要，因为它决定了一个关键判断：前缀和是为了“快速查询”而牺牲“修改效率”，差分是为了“快速修改”而牺牲“即时查询”。前缀和适合静态数据多次查询，差分适合批量修改后一次性查询。两者不是竞争关系，而是互补关系，分别处理不同时间特征的问题。
二维的情况也一样。二维前缀和 A[i][j] 表示从左上角到 (i, j) 的整个子矩阵的和，二维差分就是它的逆运算。理解了这一层关系，后面二维修改的四个点操作就顺理成章了。
1.3 差分的复杂度优势一览
拿上面的“区间加法、最后查询”场景做个对比：
| 方案 | 单次区间修改耗时 | 最终查询耗时 | m 次修改总成本 |
|---|---|---|---|
| 暴力 for 循环 | O(n) | O(1) | O(n*m) |
| 每次修改后重建前缀和 | O(n) | O(1) | O(n*m) |
| 差分 | O(1) | O(n) | O(n+m) |
当 n 和 m 都到 10^5 甚至 10^6 时，O(n*m) 是天文数字，而 O(n+m) 基本可以秒出结果。这就是差分的核心价值。
这里有个容易忽略的细节：差分虽然修改是 O(1)，但查询不是 O(1)。它假设所有修改都发生在查询之前，最后统一做一次 O(n) 的前缀和还原。如果题目要求“每修改一次，立刻查询某个位置”，差分就退化了，那应该用树状数组或线段树，这部分我放到第 5 章详细讲。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 一维差分：原理与 Java 实现
2.1 记住两个性质，后面全靠它们推
一维差分只需要掌握两个性质。
性质一：原数组 a 是差分数组 b 的前缀和。也就是 a[i] = b[1] + b[2] + ... + b[i]。这个性质决定了“还原”操作怎么做。
性质二：对原数组区间 [l, r] 整体加 v，等价于 b[l] += v，b[r+1] -= v。为什么？因为 b[l] 加 v 之后，从位置 l 开始的所有前缀和都加了 v；而 b[r+1] 减 v 之后，从位置 r+1 开始的所有前缀和又减回 v。两者叠加，受到影响的正好只有 [l, r] 这一段。
举个例子。数组 [0, 0, 0, 0, 0, 0]，对 [2, 4] 加 5。按照性质二，b[2] += 5，b[5] -= 5。还原时对 b 求前缀和：
索引 1 到 6 的结果是 [0, 5, 5, 5, 0, 0]，正好第 2、3、4 位变成了 5，第 1、5、6 位不受影响。
这个性质是整套模板的根基，建议自己随手写几个小数组验一遍。验过一次之后，add 方法的两个操作就不会再记错了。
2.2 构造差分数组的两条路
很多初学差分的同学会纠结一个问题：原数组不是 0 怎么办？其实有两条路。
第一条路：先完整读入原数组 a，然后按定义构造 b，b[1] = a[1]，b[i] = a[i] - a[i-1]。这种写法直白，但要额外多读一遍原数组。
第二条路：把“原数组的初始值”也当成 m 次区间操作来对待。原数组每个位置 i 的初始值 x，本质上就是“单点 [i, i] 加 x”，直接调用 add(i, i, x)。这样代码统一，只有一个 add 方法，不需要单独写构造差分的逻辑。
我日常刷题更推荐第二条路，因为写出来的模板可以复制粘贴，不管原数组是不是全 0。个人习惯是：凡是在代码开头会调用 add(i, i, x) 的地方，就是把初始值当单点修改处理了。
2.3 完整的竞赛向 Java 模板
这是我最常用的一维差分模板，直接拿去跑没有问题：
java复制import java.util.Scanner;
public class DiffTemplate1D {
static long[] diff;
// 区间[l, r]整体加v
static void add(int l, int r, long v) {
diff[l] += v;
diff[r + 1] -= v;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
diff = new long[n + 2];
// 读入初始数组，当作单点修改
for (int i = 1; i <= n; i++) {
int x = sc.nextInt();
add(i, i, x);
}
// m次区间操作
for (int i = 0; i < m; i++) {
int l = sc.nextInt();
int r = sc.nextInt();
long v = sc.nextLong();
add(l, r, v);
}
// 前缀和还原，同时输出
long[] res = new long[n + 1];
for (int i = 1; i <= n; i++) {
res[i] = res[i - 1] + diff[i];
System.out.print(res[i] + " ");
}
sc.close();
}
}
这段代码里有几个细节值得说。
第一，diff 数组长度开 n+2 而不是 n。因为 add 方法在 r 等于 n 时会访问 diff[r+1]，也就是 diff[n+1]，长度 n+1 才刚好不越界，开 n+2 是给自己多留一点安全余量。
第二，下标从 1 开始而不是 0。很多人写算法题喜欢下标 0 开始，这在差分里会带来一堆特判，比如 r+1 等于 n 时怎么办。下标从 1 开始之后，add 代码干净利落，强烈建议养成这个习惯。
第三，差值数组用 long 而不是 int。区间操作次数一多，累加值很容易超过 int 的最大值，尤其当 v 可能是负数时，绝对值的累加更危险。用 long 是成本最低的保险。
2.4 关于输入性能的补充
上面模板用了 Scanner，写起来省事，但在大数据量下 Scanner 是明显的性能瓶颈。蓝桥杯和笔试里，如果 n 和 m 都是 10^5 以上，建议换 BufferedReader 加 StringTokenizer，读取速度能快好几倍。
java复制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());
Scanner 的便利性和性能不可兼得，比赛场景选性能。这个替换同样适用于二维差分的输入。
3. 二维差分：矩阵批量更新的利器
3.1 从一维到二维：多了一个方向
一维处理数组的区间，二维处理矩阵的子矩形。常见的题目长这样：一个 n 行 m 列的矩阵，初始全为 0，k 次操作，每次把左上角 (x1, y1) 到右下角 (x2, y2) 的子矩形内所有元素加 v，最后输出整个矩阵。
如果暴力双重循环，单次操作 O(nm)，k 次就是 O(kn*m)，数据一大一样必挂。二维差分可以把单次子矩形修改变成四个点的修改，最后做二维前缀和还原。
二维差分矩阵 diff 的定义和一维类似：原矩阵 a 是 diff 的二维前缀和。也就是说，对 diff 求一遍二维前缀和，得到的就是最终矩阵。
3.2 四个点操作背后的容斥原理
想理解二维差分，得先理解二维前缀和的容斥公式：
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]
这个公式的含义是：从 (1,1) 到 (i,j) 的矩形和，等于上方矩形加左方矩形，减掉左上角被重复计算的部分，再加上当前点的值。
二维差分的区间修改，反着用这个思想。要在 (x1, y1) 到 (x2, y2) 的子矩阵上加 v，操作是：
java复制diff[x1][y1] += v;
diff[x1][y2 + 1] -= v;
diff[x2 + 1][y1] -= v;
diff[x2 + 1][y2 + 1] += v;
记忆口诀是“左上加、右上减、左下减、右下加”。为什么是这四个位置：在 (x1, y1) 加 v，会向右下方向影响所有后续位置；需要在第 y2+1 列的边界上减掉向右多出来的部分，在第 x2+1 行的边界上减掉向下多出来的部分；但右上和左下分别减掉时，右下角 (x2+1, y2+1) 被减了两次，所以要再加回来一次。这和二维前缀和中的容斥完全一致。
3.3 二维差分 Java 模板与原地还原
直接给可以用的模板：
java复制import java.io.*;
public class DiffTemplate2D {
static long[][] diff;
static int n, m;
// 子矩阵(x1,y1)到(x2,y2)整体加v
static void add(int x1, int y1, int x2, int y2, long v) {
diff[x1][y1] += v;
diff[x1][y2 + 1] -= v;
diff[x2 + 1][y1] -= v;
diff[x2 + 1][y2 + 1] += v;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] parts = br.readLine().split(" ");
n = Integer.parseInt(parts[0]);
m = Integer.parseInt(parts[1]);
int q = Integer.parseInt(parts[2]);
diff = new long[n + 2][m + 2];
// 如果初始矩阵不是0，读入时调用add(i, j, i, j, val)
for (int i = 0; i < q; i++) {
parts = br.readLine().split(" ");
int x1 = Integer.parseInt(parts[0]);
int y1 = Integer.parseInt(parts[1]);
int x2 = Integer.parseInt(parts[2]);
int y2 = Integer.parseInt(parts[3]);
long v = Long.parseLong(parts[4]);
add(x1, y1, x2, y2, v);
}
// 原地做二维前缀和，diff[i][j]就是最终矩阵位置(i,j)的值
for (int i = 1; i <= n; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 1; j <= m; j++) {
diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
sb.append(diff[i][j]);
if (j < m) {
sb.append(' ');
}
}
System.out.println(sb);
}
}
}
“原地还原”是二维差分一个非常好用的技巧：做完所有 add 操作后，直接在 diff 数组自身上做二维前缀和，不需要额外开原矩阵数组。遍历顺序必须是从上到下、从左到右，因为当前位置依赖 diff[i-1][j]、diff[i][j-1] 和 diff[i-1][j-1]，这三者必须已经计算完毕。
3.4 手推验证：3x3 小矩阵测试法
二维差分的四个 add 位置特别容易写错，我每次写完模板都会拿一个 3x3 的矩阵手工验一遍。比如对 (2,2) 到 (3,3) 的子矩阵加 1：
add 之后 diff 在 (2,2) 加 1，(2,4) 减 1（如果 m=3 则这里就是 (2,4)，数组要够大），(4,2) 减 1，(4,4) 加 1。手动做二维前缀和，你会发现矩阵 (2,2)、(2,3)、(3,2)、(3,3) 四个位置都变成了 1，其余位置全是 0。
这个方法几乎能杜绝所有“符号写反”类错误。每学一个新模板，先在草稿纸上验一个最小规模的例子，比背十遍公式都有用。
4. 差分算法的高频应用场景：竞赛、面试与工程思考
4.1 蓝桥杯 Java 组：识别“差分信号”
在蓝桥杯真题和模拟题里，差分相关的题目出现频率不低，而且有一个明显的识别特征：题目描述里同时出现“多次区间操作”和“最终统一输出/查询”。
我总结过几类常见的出题套路：
- 初始全 0，q 次区间加，问所有操作后最大值、最小值或某个位置的值。
- 给定一个数组，q 次操作把 [l, r] 整体加 v，最后求前缀和的极限值，或者和排序结合做区间覆盖统计。
- 二维矩形涂色、矩形加权，最后输出整个矩阵。
这些题表面上是“覆盖”“涂色”“累计值”，剥掉外壳全是差分。关键在于别被花哨的题目背景带偏，看到“区间加”和“最后再输出”这两个信号，就直接考虑差分。
蓝桥杯 Java 组有个优势：可以随意使用 java.util 包下的工具类，不需要像 C++ 那样自己造轮子。但输入性能要提前注意，Scanner 在十万级数据量下会拖慢整个程序，建议在模板里就内置 BufferedReader 版本。
4.2 面试题的常见变体与追问
差分在 Java 后端面试中通常不是单独一道大题，而是作为“数组优化”的手段藏在小题目里。比如面试官问：“一段代码要处理 1 亿个 0，给你 1 万次操作，每次把 [l, r] 内的数都加 1，最后统计值为 0 的位置有多少个。你怎么做？”
这就是典型的差分应用题，只是换了一个业务马甲。候选人如果能立刻说出“用差分数组，每次 O(1) 修改，最后一遍前缀和统计”，就能顺利进入下一轮。
面试官还喜欢追问几个点：
- add 方法里为什么是 r+1 减而不是 r 减？
- 用 int 存差分数组会不会溢出？
- 如果操作过程中要实时查询某个位置的值，该怎么办？
前两个问题，前面章节已经覆盖。第三个问题需要你理解差分的时间特性，能说出“边修改边查询应该换树状数组配合差分或线段树”，基本就算过关了。
4.3 工程与业务中的差分思想
很多人觉得差分算法只属于刷题，工程里用不到。实际上它有更泛化的思想：把“批量变更”转化为“变更点的记录”，延迟到某个时间点统一结算。
一个常见案例是日志统计。你需要按分钟统计某段时间的请求量，但事件是陆续到达的，如果每个事件都实时更新数据库对应分钟记录，压力会很大。更聪明的做法是先把所有事件按时间戳放进一个增量数组，最后扫描一遍累加生成统计报表。
还有游戏业务里的活动积分、任务的进度累计，很多也是“记录开始和结束时的变动量，结束阶段统一扫描”的模型。这种设计模式本质上就是差分。
工程中最接近差分数组的数据结构，是 Unix 系统里“从文件位置偏移量”的角度去理解变更前后关联，但那个太底层了。日常开发中，只要你能看出“修改多、查询少且查询集中在最后”的特征，就说明差分思想能用上。
4.4 树上差分：进阶扩展
树上差分是一维差分在树结构上的推广，解决的是“在一棵树的路径上做批量修改，最后统计每个点或每条边的值”这类问题。
核心操作是：对路径 u 到 v 上的所有点加 1，用差分维护，需要操作 diff[u]++、diff[v]++、diff[lca]--、diff[parent(lca)]--，最后 DFS 一遍累加还原。
这个知识点属于进阶内容，蓝桥杯和面试不一定考，但树上差分的思路和一维差分一脉相承，理解成本不高。建议先把一维差分练熟，再来看树上差分会轻松很多。
5. 差分、前缀和、树状数组、线段树：到底怎么选
5.1 四类方案复杂度对比
很多人学完差分后反而更纠结：这东西和前缀和、树状数组、线段树到底啥关系？我什么时候该用哪个？
| 方案 | 单点修改 | 区间修改 | 单点查询 | 区间查询 | 代码量 |
|---|---|---|---|---|---|
| 前缀和数组 | O(n) | O(n) | O(1) | O(1) | 低 |
| 差分数组 | O(1) | O(1) | O(n) 还原 | O(n) 还原 | 低 |
| 树状数组 | O(log n) | O(log n)（配差分） | O(log n) | O(log n) | 中 |
| 线段树 | O(log n) | O(log n) | O(log n) | O(log n) | 高 |
差分和前缀和互补，这一点前面聊过。差分和树状数组则是另一种关系：树状数组单点修改是 O(log n)，但如果配合差分数组，就能支持“区间修改 + 单点查询”，这也是常见玩法。线段树则直接支持“区间修改 + 区间查询”，代价是代码量明显增大。
5.2 决策三步法
每拿到一道区间操作题，我会按三个问题做决策。
第一步：是“先改后查”还是“边改边查”？如果所有修改都在前面，查询在最后，差分是最优选。如果修改和查询交替出现，差分离线优势就没了，要转向树状数组或线段树。
第二步：查询是单点还是区间？只查单个位置，树状数组配合差分就能解决；要查区间和或区间最值，线段树更直接。
第三步：数据规模到什么量级？n、q 都在 10^5 以下，O(n log n) 完全可接受，树状数组和线段树都没问题。n、q 到 10^6，常数就很重要了，能用差分尽量差分，树状数组的 log 常数也是成本。
这三个问题一步想完，选型基本不会跑偏。
5.3 我的建议：三个模板都要背
作为一个 Java 方向的算法学习者，我建议把差分、树状数组、线段树这三个模板都存一份，哪怕平时只用到其中一个。
原因很实际：笔试和比赛的时间压力很大，现推公式容易出错。模板是先验过的，能直接照着写。差分是其中最轻量、容错率也最高的，适合作为绝大多数区间题的默认起点。树状数组代码不算长，但理解门槛略高。线段树代码长，可调试成本大，一般只有在前面两个明确不合适的题里才拿出来用。
在工程环境里，能不用手写数据结构就不要手写。Java 生态里有很多成熟的框架和数据库方案可以做区间聚合、增量统计，手动实现线段树在生产代码里是少数情况。
6. 踩坑实录：差分算法最常见的 5 个错误
6.1 数组越界：diff 长度开错
症状是运行时报 ArrayIndexOutOfBoundsException。原因多半是 diff 长度只开了 n，但 add 方法访问了 r+1，当 r 等于 n 时越界。
解决方式很简单：数组长度统一开 n+2，下标从 1 开始。这多出来的两个位置，一个是给 r+1 用的，另一个是保险。二维差分同理，开 (n+2) 行 (m+2) 列。
6.2 只标记不结算：忘了前缀和还原
我记得第一次写差分，add 调完了直接输出 diff 数组，结果全是 0 和几个散落的数字，调了半天才发现没做前缀和。
差分是“标记阶段”和“结算阶段”分离的。add 只是在做标记，diff 本身不是答案。结算阶段必须执行 res[i] = res[i-1] + diff[i] 这个还原操作。忘记这一条的典型症状是输出全是 0，因为初始 diff 数组本来就是 0。
6.3 二维差分的符号写反
二维差分的四个 add 位置，新手经常把 (x1, y2+1) 和 (x2+1, y1) 的符号写反，或者把右下角的“补偿加回”漏掉。
我自己的排查方法很简单：拿一个 3x3 的小矩阵，手动执行一遍二维前缀和，看非目标区域有没有被错误修改。只要花两分钟验证，这类错误基本当场就能发现。口诀“左上加、右上减、左下减、右下加”也帮我避免过很多次手滑。
6.4 int 溢出：区间叠加多了会炸
差分数组里一个位置可能累积很多次操作的值。如果 v 最大到 10^9，操作一万次，累加值就是 10^13，int 根本装不下。
用 int 存的第一个信号是结果出现“奇怪的大负数”。这个 bug 很难查，因为暴力跑小规模数据完全正常，一上大数据就翻车。最省心的做法是模板里一律用 long，从源头上避免。
6.5 多组测试数据复用：残留值污染答案
竞赛题目经常一个程序处理多组测试用例。如果 diff 是全局数组，上一组数据留下的值没清干净，第二组答案会错得莫名其妙。
处理方式有两种：每组数据开始时直接 new 一个全新数组，或者在每组开头用 Arrays.fill(diff, 0) 清零。我偏好前者，因为 new 数组的同时也把长度重新确定了，不容易残留上一轮的越界记忆。
6.6 把“区间加”和“区间覆盖”搞混
差分天然支持“把 [l, r] 整体加 v”或“整体减 v”，但不支持“把 [l, r] 统一设成某个值”。覆盖是非叠加操作，差分的加减法模型不适用。
遇到“设为某值”“区间取最值”“区间赋值”这类要求，应该转向线段树，而不是硬套差分。这个区分在面试里经常被问到，作为候选人能主动说出来，说明你真正理解了差分的能力边界。
7. 从模板到实战：两道经典题目拆解
7.1 一维差分实战：区间加法后的最值与单点查询
题目描述：长度为 n 的数组，初始全为 0。m 次操作，每次输入 l、r、v，表示对 [l, r] 区间内所有元素加 v。所有操作结束后，输出整个数组的最大值、最小值，以及指定位置 p 的值。
数据规模：n、m 最大到 10^5，v 的绝对值最大到 10^9。
思路：直接差分。所有 add 结束后做一次前缀和，边还原边统计最值。
java复制import java.io.*;
import java.util.StringTokenizer;
public class DiffPractice1D {
static long[] diff;
static void add(int l, int r, long v) {
diff[l] += v;
diff[r + 1] -= v;
}
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 p = Integer.parseInt(st.nextToken());
diff = new long[n + 2];
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int l = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
long v = Long.parseLong(st.nextToken());
add(l, r, v);
}
long[] a = new long[n + 1];
long maxV = Long.MIN_VALUE;
long minV = Long.MAX_VALUE;
for (int i = 1; i <= n; i++) {
a[i] = a[i - 1] + diff[i];
maxV = Math.max(maxV, a[i]);
minV = Math.min(minV, a[i]);
}
System.out.println("max=" + maxV + ", min=" + minV + ", a[p]=" + a[p]);
}
}
这里我特意用 BufferedReader 替代 Scanner，因为 m 到 10^5 时输入行很多，StringTokenizer 的解析速度优势更明显。整道题的时间复杂度是 O(n + m)。
7.2 二维差分实战：矩形涂色输出
题目描述：n 行 m 列的矩阵，初始全为 0。k 次操作，每次输入 x1、y1、x2、y2、c，表示把左上角 (x1, y1)、右下角 (x2, y2) 的矩形区域全部加上数值 c。全部操作结束后，输出整个矩阵。
数据规模：n、m 都到 10^3，k 到 10^5，c 的绝对值到 10^9。
思路：二维差分模板直接套。先 add 标记所有操作，再原地做二维前缀和还原并输出。
java复制import java.io.*;
public class DiffPractice2D {
static long[][] diff;
static void add(int x1, int y1, int x2, int y2, long v) {
diff[x1][y1] += v;
diff[x1][y2 + 1] -= v;
diff[x2 + 1][y1] -= v;
diff[x2 + 1][y2 + 1] += v;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] parts = br.readLine().split(" ");
int n = Integer.parseInt(parts[0]);
int m = Integer.parseInt(parts[1]);
int k = Integer.parseInt(parts[2]);
diff = new long[n + 2][m + 2];
for (int i = 0; i < k; i++) {
parts = br.readLine().split(" ");
int x1 = Integer.parseInt(parts[0]);
int y1 = Integer.parseInt(parts[1]);
int x2 = Integer.parseInt(parts[2]);
int y2 = Integer.parseInt(parts[3]);
long c = Long.parseLong(parts[4]);
add(x1, y1, x2, y2, c);
}
StringBuilder out = new StringBuilder();
for (int i = 1; i <= n; i++) {
StringBuilder row = new StringBuilder();
for (int j = 1; j <= m; j++) {
diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
row.append(diff[i][j]);
if (j < m) {
row.append(' ');
}
}
out.append(row).append('\n');
}
System.out.print(out);
}
}
这里有个输出优化的细节：不用 System.out.println 一行行打印，而是先拼到 StringBuilder 里一次性输出。n*m 到 10^6 时，逐行打印也是一个不小的开销。
7.3 场景边界：操作中间穿插查询怎么办
上面的题目都满足“先修改、后查询”，这是差分最舒服的场景。如果题目变成“每次修改完立刻输出某个位置的值”，差分就不合适了。
最朴素的思路是每轮操作后都重新做一遍前缀和还原，但那样复杂度是 O(q*n)，比不用差分还差。正确做法是树状数组配合差分：区间修改变成两个点的树状数组更新，单点查询变成前缀和查询，单次操作和查询都是 O(log n)。
了解这个边界很重要，否则容易在实际题目中误用差分。面试和竞赛里，能主动说出“这种情况我应该换树状数组”，是一个很加分的信号。
最后说点个人体会。我刚开始练差分的时候，最常犯的错不是不会写 add，而是看到题目没意识到“先统一修改、最后统一查询”的时间特征，结果绕去写线段树，代码量翻了几倍。后来养成一个习惯：每道数组区间题看完题面先问自己三个问题——修改是加还是覆盖？查询在修改中间还是最后？数据规模多大？只要答案是“加、最后、10^5 以上”，就直接上差分模板。这个习惯帮我省下了大量时间。另外一个小技巧：比赛前把一维、二维差分的 add 方法和还原循环默写在草稿纸上，正式比赛直接照抄，省去临时推导的慌乱。希望这篇文章能让你少走几步弯路。