考点

二维差分。

思路分析

暴力模拟会超时。

一维差分的思路：对数组 a 构造差分数组 b，其中 b[i] = a[i] - a[i-1]。对区间 [l, r] 加上 c 时，只需 b[l] += c、b[r+1] -= c，最后前缀和还原。

对于二维，在 (x1, y1) 到 (x2, y2) 矩形区域加 1，差分操作是四个点：

1
2
3
4
d[x1][y1]   += 1
d[x1][y2+1] -= 1
d[x2+1][y1] -= 1
d[x2+1][y2+1] += 1

最后对每行做前缀和即可得到最终的矩阵。

代码实现

1
2
3
4
5
6
7
for (int l = 1; l <= n; l++) {
    for (int r = 1; r <= n; r++) {
        map[l][r] += map[l][r-1];
        System.out.print(map[l][r] + " ");
    }
    System.out.println();
}

小结

  • 差分的核心思想：区间修改转化为端点操作，避免暴力
  • 二维差分可以拆成四个单点修改，再前缀和还原