二维差分

· · 算法·理论

定义

对于一个二维数组 a 构造出一个二维数组 b 使得：

a[n][m]=\sum_{i=1}^n\sum_{j=1}^mb[i][j]

则称 b 是 a 的二维差分数组。

可以发现，差分和前缀和是逆运算。

应用

应用二维差分可以 O(1) 完成对原数组的矩形加。

具体地：

若要将 a 中 (x_1,y_1) 到 (x_2,y_2) 的矩形整体加 x。

对于 b 需要对 (x_1,y_1) 和 (x_2,y_2) 加 x，对 (x_2+1,y_1) 和 (x_1,y_2+1) 加 -x。