本笔记内容来源于算法基础课

差分

对于给定的数组$a_1, a_2, …, a_n$

则差分数组为$b_1, b_2, …, b_n$, 其中$a_i = b_1 + b_2 + … + b_i$

$b$为$a$的差分，$a$为$b$的前缀和

$b_i$的作用

对于数组中的任意区间[l, r], 都进行操作$+C$

$a_l + C, a_{l+1} + C, …, a_r + C$

若$b_l + C$, 则$a_l$之后的项都会$+C$, 因为它们的前缀和都会包括项$b_l$，即作用于区间$[l, +\infty)$
同时还需要保证$b_{r+1}$之后的项不会$+C$, 因此$b_{r+1} - C$

因此两种方法比较：

1. 遍历区间数组，时间复杂为$O(n)$
2. 操作差分数组，$b_l + C, b_{r+1} - C$，时间复杂度为$O(1)$

注意：

最后要求数组$b$的前缀和，来重新得到$a$

边界问题

构造$b_i$

实际上并不需要构造

考虑$a$数组初始全为0，进行$n$次插入操作，对区间$[i, i]$操作$+a_i$

二维差分

对于原矩阵$a_{ij}$，则差分矩阵$b_{ij}$，使得$a_{ij} = \sum\limits_{x=1 \sim i, y=1 \sim\ j}b_{xy}$

同样先不需要考虑如何构造，而只需要考虑如何更新

二维矩阵中任意个子矩阵以$(x_1, y_1)$ $(x_2, y_2)$为对角线进行操作$+C$

而差分数组操作$b_{ij} + C$，作用于子矩阵$[(i,j), (+\infty,+\infty)]$

因此进行如下操作：
$b_{x_1y_1} + C, b_{x_1y_2+1} - C, b_{x_2+1y_1} - C, b_{x_2+1y_2+1} + C$

构造差分则进行$n*m$次插入操作，对$[(x_iy_j), (x_iy_j)]$执行操作$+C$

最后求$b$的二维前缀和即可得到$a$

例题

Acwing 4195 只维护差分的端点