核心逻辑与数学原理
差分是前缀和的逆运算，其物理本质是将全局区间修改转化为局部端点修正，实现对区间操作的降维打击。
设原序列为 $A$，差分序列为 $D$。两者满足以下代数关系：
$$D[i] = \begin{cases} A[i] & i = 1 \\ A[i] - A[i-1] & i > 1 \end{cases}$$
由定义可知，原序列 $A$ 实际上是差分序列 $D$ 的前缀和序列：
$$A[i] = \sum_{k=1}^{i} D[k]$$
当需要对原序列的区间 $[l, r]$ 全体加上增量 $v$ 时，若直接暴力修改，时间复杂度为 $O(N)$。观察差分结构的内部性质：对于 $l < i \le r$ 的任意位置，由于 $A[i]$ 与 $A[i-1]$ 同时加上了 $v$，其相对差值 $A[i] - A[i-1]$ 保持不变，即 $D[i]$ 无需任何改动。真正发生跃变的只有两个边界：
- $A[l]$ 比 $A[l-1]$ 多增了 $v$，故 $D[l]$ 增加 $v$。
- $A[r+1]$ 比 $A[r]$ 相对少增了 $v$，故 $D[r+1]$ 减少 $v$。
通过将区间问题退化为两点修改，单次操作复杂度被压制到 $O(1)$。
算法推导
1. 一维差分维护与还原
对于 $M$ 次独立的区间修改 $(l, r, v)$，直接在差分数组 $D$ 上进行：
$$D[l] \leftarrow D[l] + v$$
$$D[r+1] \leftarrow D[r+1] - v$$
修改完毕后，利用前缀和递推关系公式 $A[i] = A[i-1] + D[i]$，可在 $O(N)$ 时间内离线还原出最终的整个原序列 $A$。
2. 二维矩阵差分推导
在二维矩阵中，若要对以 $(x_1, y_1)$ 为左上角、$(x_2, y_2)$ 为右下角的子矩阵全加上 $v$，利用二维容斥原理，我们在二维差分矩阵 $D$ 上的两点修正演变为四点修正。根据二维前缀和的逆向拓扑结构，修改方程为：
$$D[x_1][y_1] \leftarrow D[x_1][y_1] + v$$
$$D[x_2+1][y_1] \leftarrow D[x_2+1][y_1] - v$$
$$D[x_1][y_2+1] \leftarrow D[x_1][y_2+1] - v$$
$$D[x_2+1][y_2+1] \leftarrow D[x_2+1][y_2+1] + v$$
恢复原矩阵时，利用二维前缀和状态转移方程进行 $O(N \times M)$ 的状态扫描。
C++ 标准源码
#include <iostream>
#include <vector>
using namespace std;
// 演示二维差分矩阵的修改与还原过程
void solveMatrixDifference() {
int n, m, p;
if (!(cin >> n >> m >> p)) return;
// 1-indexed 边界，防止 x2+1 或 y2+1 发生越界崩溃，多开 2 行 2 列作为安全缓冲
vector<vector<long long>> d(n + 2, vector<long long>(m + 2, 0));
// P 次区间增量修改
for (int i = 0; i < p; ++i) {
int x1, y1, x2, y2;
long long v;
cin >> x1 >> y1 >> x2 >> y2 >> v;
// 关键点：基于容斥原理的 4 点修正，错一个符号直接爆 0
d[x1][y1] += v;
d[x2 + 1][y1] -= v;
d[x1][y2 + 1] -= v;
d[x2 + 1][y2 + 1] += v;
}
// O(N*M) 前缀和还原矩阵
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[i][j];
cout << d[i][j] << (j == m ? "" : " ");
}
cout << "\n";
}
}
int main() {
// 斩断标准流同步常数
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solveMatrixDifference();
return 0;
}NOIP 实战避坑指南
- 右端点加一（$r+1$）造成的内存越界访问
差分修正时必然涉及 $D[r+1]$ 或二维的 $D[x_2+1][y_2+1]$。当输入的修改边界恰好等于数据范围上限 $N$ 时，$r+1$ 会直接指向 $N+1$。如果数组刚好只开了 $N$ 大小，会触发段错误（Segmentation Fault）或者极其隐蔽的内存邻接越界写，导致其他变量值被诡异覆盖。必须养成习惯：差分数组的空间至少开到 $N + 2$。 - 前缀和还原时的累加溢出
即使单次修改增量 $v$ 较小，如果修改操作 $M$ 达到 $10^5$ 级别，频繁区间叠加后的最终原元素值极易冲破int的 $2 \times 10^9$ 上限。如果图省事将差分数组定义为int，在前缀和累加阶段就会发生整型溢出，导致还原出的数据变成负数。所有的差分数组和还原变量一律使用long long存储。
经典 NOIP/洛谷 真题
1. 洛谷 P3397 地毯
- 题意描述：在一个 $N \times N$ 的网格上铺 $M$ 块地毯，每块地毯用左上角坐标 $(x_1, y_1)$ 和右下角坐标 $(x_2, y_2)$ 表示。求最后网格中每个点被多少块地毯覆盖。
- 问题本质：纯粹的二维矩阵区间批量自增 1 运算。
- 核心解题思路：
若暴力模拟，时间复杂度为 $O(M \times N^2)$，面对 $N \le 1000, M \le 10000$ 的数据必然超时。由于属于典型的离线区间批量修改，直接建立一个二维差分矩阵 $D$。对每块地毯执行四点修正令该区域权值加 1。所有地毯处理完毕后，从 $(1,1)$ 开始执行一次标准的二维前缀和扫描，将差分矩阵还原。总时间复杂度被成功压制在 $O(M + N^2)$，属于一维/二维差分算法的基准物理模型。
2. 洛谷 P1083 [NOIP2012 提高组] 借教室
- 题意描述：有 $N$ 天，每天有固定的教室可租借量。现有 $M$ 个订单，每个订单要求在第 $s$ 天到第 $t$ 天租借 $d$ 间教室。订单必须按先后顺序满足，求从第几个订单开始由于教室不够而无法分配。
- 问题本质：区间减法修改 + 临界合法性判定。
- 核心解题思路：
订单具有先后顺序且要求找出第一个不满足的订单，具备显著的单调性，优先考虑二分答案。二分能够安全通过的前 $mid$ 个订单。对于检验函数check(mid)：我们需要在 $O(N)$ 时间内验证前 $mid$ 个区间修改叠加后，是否存在某一天所需的教室总量超过了当天的可用教室天花板。此时使用一维差分数组对前 $mid$ 个订单进行区间操作（$D[s] \leftarrow D[s] + d$, $D[t+1] \leftarrow D[t+1] - d$），随后利用前缀和恢复出前 $mid$ 天每天的教室总需求。若发现任意一天的需求大于当天供给，则说明 $mid$ 偏大，调整二分右边界。总时间复杂度由暴力的 $O(N \times M)$ 优化至 $O(N \log M)$，直接秒杀该题。