该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

二维差分 - 课堂笔记

1. 基本概念

1.1 什么是二维差分

• 二维差分是一种用于快速修改二维数组中子矩阵值的技术
• 类似于一维差分在二维空间的扩展
• 主要应用场景：需要频繁对二维数组的矩形区域进行批量加减操作

1.2 核心思想

通过维护一个差分数组，将区间修改转化为单点修改，从而优化时间复杂度。

2. 二维差分数组的定义与计算

2.1 差分数组定义公式

c[i][j] = a[i][j] + a[i-1][j-1] - a[i-1][j] - a[i][j-1]

2.2 公式说明

3. 区间修改操作

3.1 修改范围定义

• 要修改的子矩阵范围：从点 (x, y) 到点 (xx, yy)
• 修改值：所有元素 +k

3.2 差分数组的修改点

只需要修改差分数组的4个关键点：

c[x][y]     += k
c[x][yy+1]  -= k
c[xx+1][y]  -= k
c[xx+1][yy+1] += k

3.3 修改原理图示

坐标示意图：
    y        yy+1
x   +k       -k
    ↓        ↓
xx+1 -k       +k

4. 还原原数组

4.1 还原公式

a[i][j] = c[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1]

4.2 还原过程说明

通过二维前缀和的方式从差分数组还原出原数组。

5. 完整算法流程

步骤1：通过原数组计算差分数组

// 假设原数组为 a，差分数组为 c
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        c[i][j] = a[i][j] + a[i-1][j-1] - a[i-1][j] - a[i][j-1];
    }
}

步骤2：通过差分数组完成区间修改

// 修改子矩阵 [x, xx] × [y, yy]，所有元素 +k
void update(int x, int y, int xx, int yy, int k) {
    c[x][y] += k;
    c[x][yy+1] -= k;
    c[xx+1][y] -= k;
    c[xx+1][yy+1] += k;
}

步骤3：通过差分数组还原原数组

// 从差分数组还原原数组
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        a[i][j] = c[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
    }
}

步骤4：在原数组中统计答案

在还原后的原数组上进行所需的统计和计算。

6. 时间复杂度分析

优势：当需要进行大量区间修改时，二维差分将时间复杂度从 O(m×k) 优化到 O(m + n×m)，其中 k 是平均区域大小。

7. 具体例子演示

初始原数组 a：

1 1 1
1 1 1  
1 1 1

计算差分数组 c：

1  0  0
0  0  0
0  0  0

修改子矩阵 [1,2] × [1,2] 所有元素 +2：

在差分数组上修改4个点：

c[1][1] += 2   → 3
c[1][3] -= 2   → -2  
c[3][1] -= 2   → -2
c[3][3] += 2   → 2

还原后的原数组：

3 3 1
3 3 1
1 1 1

8. 注意事项

1. 边界处理：数组通常从下标 1 开始，方便处理边界情况
2. 数组大小：差分数组需要比原数组多一行一列
3. 数据类型：注意数据范围，防止整数溢出
4. 多次操作：可以累积多次修改后再统一还原

总结

二维差分通过巧妙的数学变换，将区间修改的复杂度从 O(n²) 降到 O(1)，是处理二维区间更新问题的重要技巧。

核心要点：

1. 差分数组：c[i][j] = a[i][j] + a[i-1][j-1] - a[i-1][j] - a[i][j-1]
2. 区间修改：只改4个点
3. 还原原数组：二维前缀和思想

掌握其原理和实现方法对于解决相关算法问题非常有帮助。