核心逻辑与数学原理
差分是前缀和的逆运算。其本质在于将“区间上的整体操作”转化为“差分数组上的两点修正”，从而将算法的时间复杂度从 $O(N)$ 降至 $O(1)$。
1. 数学定义
设原序列为 $A$，构造差分序列 $D$ 满足：
$$D[i] = A[i] - A[i-1] \quad (\text{其中定义 } A[0] = 0)$$
相应地，原序列 $A$ 实际上是差分序列 $D$ 的前缀和序列：
$$A[i] = \sum_{k=1}^{i} D[k]$$
2. 区间修改的降维思想
当需要对原序列区间 $[l, r]$ 全体加上增量 $v$ 时，观察 $D$ 的代数跃变：
- 对于 $l$ 位置：$A[l]$ 增加了 $v$，而 $A[l-1]$ 未变，故 $D[l] = A[l] - A[l-1]$ 增加了 $v$。
- 对于 $r+1$ 位置：$A[r+1]$ 未变，但 $A[r]$ 增加了 $v$，故 $D[r+1] = A[r+1] - A[r]$ 减少了 $v$。
- 对于中间位置 $i \in (l, r]$：$A[i]$ 与 $A[i-1]$ 同时增加了 $v$，其相对差值保持不变，故 $D[i]$ 无需任何改动。
结论：区间 $[l, r]$ 的整体操作退化为两点修改：
- $D[l] \leftarrow D[l] + v$
- $D[r+1] \leftarrow D[r+1] - v$
算法推导
1. 一维差分维护与还原
对于 $M$ 次独立的区间修改 $(l, r, v)$，直接在差分数组 $D$ 上进行极速修正：
$$D[l] \leftarrow D[l] + v, \quad 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[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$$
对差分数组 $D[x][y]$ 加上 $v$，等价于在还原出的原数组 $A$ 中，以 $(x, y)$ 为左上角、无限向右下角延伸的无穷区域整体加上 $v$
恢复原矩阵时，利用二维前缀和状态转移方程进行 $O(N \times M)$ 的双重循环扫描。 $$A[i][j] = A[i-1][j] + A[i][j-1] - A[i-1][j-1] + D[i][j]$$
或者， 原地（In-place）复用空间写法，该方程则表现为自左向右、自上而下的状态累加：
$$D[i][j] \leftarrow D[i][j] + D[i-1][j] + D[i][j-1] - D[i-1][j-1]$$
核心代码
// 二维差分矩阵的四点修正
void update(int x1, int y1, int x2, int y2, int v) {
d[x1][y1] += v;
d[x2 + 1][y1] -= v;
d[x1][y2 + 1] -= v;
d[x2 + 1][y2 + 1] += v;
}
// 原地双重循环进行二维前缀和还原
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];
}
}
NOIP 实战避坑指南
- 右端点加一（$r+1$）造成的内存越界写 差分边界修正必然涉及 $D[r+1]$ 或二维的 $D[x_2+1][y_2+1]$。当输入的修改边界恰好等于数据范围上限 $N$ 时，$r+1$ 会直接指向 $N+1$。若数组刚好紧绷着只开了 $MAXN$ 大小，会触发段错误（SIGSEGV）或极隐蔽的内存邻接覆盖。必须养成铁律：差分数组的空间至少开到 $N + 2$。
- 前缀和还原时的整型溢出（Integer Overflow） 即使单次增量 $v$ 在
int范围内，如果修改次数 $M$ 达到 $10^5$ 级别，频繁区间叠加后单点最大值极易冲破 $2 \times 10^9$（int上限）。若差分数组误用int，在前缀和递推累加时会发生数据爆满溢出，导致还原结果变为诡异的负数。记住：一维/二维差分数组、前缀和累加变量，一律强制使用 `long long`。
经典 NOIP/洛谷 真题
1. 洛谷 P3397 地毯
- 题意描述：在一个 $N \times N$ 网格上铺 $M$ 块地毯，求每个点最终被多少块地毯覆盖。（$N \le 1000, M \le 100000$）
- 问题本质：静态离线的二维矩阵区间批量自增 1 运算。
- 核心解题思路：
面对十万级别的修改，若暴力模拟复杂度为 $O(M \times N^2)$ 必然超时。由于修改全部离线，直接建立二维差分全局矩阵
d。对每块地毯执行 $O(1)$ 的四点修正。所有操作结束后，做一次 $O(N^2)$ 的二维前缀和原地递推。总时间复杂度成功压制在 $O(M + N^2)$。
// 1. O(M) 离线差分修改：基于容斥原理的四点修正
for (int i = 1; i <= m; i++) {
// 读入当前地毯左上角 (x1, y1) 与右下角 (x2, y2)
cin >> x1 >> y1 >> x2 >> y2;
d[x1][y1]++;
d[x2 + 1][y1]--;
d[x1][y2 + 1]--;
d[x2 + 1][y2 + 1]++;
}
// 2. O(N^2) 原地递推：利用二维前缀和逆拓扑还原覆盖次数
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
// 此时 d[i][j] 即为该网格点最终被地毯覆盖的层数
}
}
2. 洛谷 P1083 [NOIP2012 提高组] 借教室
- 题意描述：每天有固定可用教室 $r_i$。有 $M$ 个订单，要求在 $[s_i, t_i]$ 每天借 $d_i$ 间。找出第一个导致教室超载的订单编号。（$N, M \le 10^6$）
- 问题本质：动态临界判定（区间减法修改 + 决策单调性分析）。
- 核心解题思路：
订单具有严格的先后时序，且具有“一旦某天教室爆单，后续所有订单全部作废”的单调性，此特征直接指向二分答案。我们二分能够安全通过的前 $mid$ 个订单。
在判定函数
check(mid)中，通过一维差分在 $O(N)$ 时间内快速叠加前 $mid$ 个区间的教室需求，随后通过前缀和扫描判定是否超过可用容量天花板 $r_i$。总时间复杂度由暴力的 $O(N \times M)$ 完美优化至 $O(N \log M)$。
// 核心校验：验证只处理前 mid 个订单时，全量累加后是否会爆容量天花板
bool check(int mid) {
// 每次校验前，干净利落地清空差分数组
for (int i = 1; i <= n; i++) diff[i] = 0;
// 1. 一维差分快速批量修改
for (int i = 1; i <= mid; i++) {
diff[s[i]] += d[i];
diff[t[i] + 1] -= d[i];
}
// 2. 前缀和还原并实施临界合法性判定
long long current_need = 0;
for (int i = 1; i <= n; i++) {
current_need += diff[i];
if (current_need > r[i]) return false; // 一旦供不应求，说明 mid 偏大
}
return true;
}
// ---------------- 主逻辑二分查找分隔线 ----------------
int left = 1, right = m, ans = 0;
while (left <= right) {
int mid = (left + right) >> 1; // NOI 风格位运算右移，规避常规除法开销
if (check(mid)) {
left = mid + 1; // 前 mid 个全部安全，尝试接纳更多订单
} else {
ans = mid; // 记录最早触发崩溃的订单位置
right = mid - 1; // 强行向前逼近，寻找是否有更早的冲突点
}
}
// 最终若 ans == 0 表明全盘安全通过；否则 ans 即为引发灾难的第一个订单编号