差分矩阵的定义与初始化

差分矩阵的定义

对于原始矩阵 $a$，其差分矩阵 $b$ 的定义如下：

$$b[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]$$

公式含义：
矩阵 $a[i][j]$ 的值由 $b[1][1]$ 到 $b[i][j]$ 的前缀和决定。差分矩阵 $b$ 是 $a$ 的“增量表示”。

insert 操作的定义

函数 insert(x₁, y₁, x₂, y₂, c) 的作用是对差分矩阵 $b$ 进行以下更新：
1. 增加左上角：
$$b[x₁][y₁] \mathrel{+}= c$$
2. 补偿右边界：
$$b[x₂+1][y₁] \mathrel{-}= c$$
3. 补偿下边界：
$$b[x₁][y₂+1] \mathrel{-}= c$$
4. 补偿右下角重叠修正：
$$b[x₂+1][y₂+1] \mathrel{+}= c$$

单元素操作的等价性

当操作范围限定为单元素（即 $x₁ = x₂ = i$ 且 $y₁ = y₂ = j$）时，调用 insert(i, j, i, j, a[i][j]) 等价于：
将b数组中需要用到(+或者-)a[i][j]的进行处理
1. $$b[i][j] \mathrel{+}= a[i][j]$$
2. $$b[i+1][j] \mathrel{-}= a[i][j]$$
3. $$b[i][j+1] \mathrel{-}= a[i][j]$$
4. $$b[i+1][j+1] \mathrel{+}= a[i][j]$$

初始化操作的逻辑

初始状态

• 初始时差分矩阵 $b$ 为全零矩阵：所有 $b[i][j] = 0$。

调用 insert(i, j, i, j, a[i][j]) 后的效果

1. 直接赋值：
   $$b[i][j] = a[i][j] \quad \text{（由 } b[i][j] \mathrel{+}= a[i][j] \text{ 实现）}$$
2. 边界修正：
3. 下方行补偿： $$b[i+1][j] = -a[i][j]$$
4. 右侧列补偿： $$b[i][j+1] = -a[i][j]$$
5. 重叠修正：
   $$b[i+1][j+1] = a[i][j]$$

最终效果

• 局部性保证：
  通过上述操作，$a[i][j]$ 的值仅由 $b[i][j]$ 贡献，其他位置不受影响。
• 数学等价性：
  初始时，矩阵 $a$ 的外部区域（如 $a[0][j]$ 和 $a[i][0]$）默认为 $0$，因此差分矩阵的公式可简化为：
  $$b[i][j] = a[i][j]$$
  这一初始化过程确保了差分矩阵与原始矩阵的等价性。