二维差分算法详解：模板题与地毯问题实战

二维差分算法详解

一、二维差分原理

我们可以类比一维差分数组的性质，推导出二维差分矩阵的核心逻辑：

• 标记修改：在差分数组的特定位置记录增量，表示后续区域统一被修改；
• 还原数组：对差分数组求前缀和，即可还原出原始矩阵。

假设我们需要将原始矩阵 a 中，以 (x1, y1) 为左上角、(x2, y2) 为右下角的子矩阵每个元素都加上 k。操作后的效果如下所示：

核心结论：

利用差分矩阵的性质，只需在四个关键点进行操作：

f[x1][y1] += k
f[x1][y2 + 1] -= k
f[x2 + 1][y1] -= k
f[x2 + 1][y2 + 1] += k

这样就能保证只有目标子矩阵内的元素增加了 k，而外部不受影响。

二、经典算法题实战

1. 【模板】差分

题目描述

给定一个 n 行 m 列的整数矩阵，初始全为 0。有 q 次操作，每次操作将某个子矩阵的元素加上一个值。最后输出整个矩阵。

思路解析

这道题是二维差分的基础应用。我们需要先根据初始输入构建差分矩阵，然后处理所有的区间更新操作，最后通过前缀和还原出最终结果。

注意这里有个细节：初始输入时，每个点本身也是一个子矩阵（左上角和右下角相同），所以也要调用更新函数。

代码实现

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 1100;
LL f[N][N];

// 更新函数：将 (x1,y1) 到 (x2,y2) 的区域加上 k
void calc(LL x1, LL y1, LL x2, LL y2, LL k) {
    f[x1][y1] += k;
    f[x1][y2 + ] -= k;
    f[x2 + ][y1] -= k;
    f[x2 + ][y2 + ] += k;
}

{
     n, m, q;
    cin >> n >> m >> q;

    
     ( i = ; i <= n; i++) {
         ( j = ; j <= m; j++) {
            LL x;
            cin >> x;
            
            (i, j, i, j, x);
        }
    }

    
     (q--) {
        LL x1, y1, x2, y2, k;
        cin >> x1 >> y1 >> x2 >> y2 >> k;
        (x1, y1, x2, y2, k);
    }

    
     ( i = ; i <= n; i++) {
         ( j = ; j <= m; j++) {
            f[i][j] += f[i - ][j] + f[i][j - ] - f[i - ][j - ];
        }
    }

    
     ( i = ; i <= n; i++) {
         ( j = ; j <= m; j++) cout << f[i][j] << ;
        cout << endl;
    }
     ;
}