二维差分

  • 回顾一维差分

对于数组 A[1..n]，定义差分数组 D

D[0] = 0;
D[i] = A[i] - A[i-1], i >= 1

区间修改：给区间 [L,R] 增加 k

D[L] += k;
D[R+1] -= k;

D[L] += k; 那么计算前缀和数组A时， A[L:]所有元素都会累加一个k;

为了消除A[R+1:]的影响, 需要D[R+1] -= k;

前缀和还原数组

A[i] = D[1] + D[2] + ... + D[i]

但我们写程序时，一般不用上面这种方法还原数组，而是

A[0] = D[0]
for(int i = 1; i < A.size(); ++i){
    A[i] += A[i-1] + D[i];
}
  • 二维差分对于数组A，其差分数组D的定义为其差分表达式并不好理解只需记住，前缀和与差分互为逆操作，A是D数组的前缀和数组:D[i][j] = A[i][j] - A[i-1][j] - A[i][j-1] + A[i-1][j-1] 就可以理解为：A[i][j] : 差分数组D (1,1）到（i,j）的整个矩形区域内元素的和）减去：A[i-1][j] 差分数组D (1,1）到（i-1,j）的整个矩形区域内元素的和减去：A[i][j-1] 差分数组D (1,1）到（i,j-1）的整个矩形区域内元素的和加上：A[i-1][j-1] 差分数组D (1,1）到（i-1,j-1）的整个矩形区域内元素的和, 用于补偿重复扣除的部分

D[i][j] += k的影响：计算(还原)前缀和数组A时，A[i:m][j:n]中所有元素都会增加k（m,n为A矩阵的行号列号）

对A矩阵区域进行操作，例如给子矩阵 (x1,y1) 到 (x2,y2) 增加 k，需要修改差分数组

D[x1][y1]   += k;  // 起点：影响整个右下区域
D[x2+1][y1] -= k;  // 右边界：消除x2右侧影响
D[x1][y2+1] -= k;  // 下边界：消除y2下侧影响
D[x2+1][y2+1] += k; // 交点：补偿重复扣除的区域

再还原前缀和数组A:

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      A[i][j] = D[i][j] + A[i-1][j] + A[i][j-1] - A[i-1][j-1];
    }
  }