上一篇：【演算法新手村】[初階]筆記06 - 差分(一維)

同樣引入一個問題，給定一個 N × M 的矩陣，有 Q 次操作，每次將左上 (x1, y1) 到右下 (x2, y2) 的子矩陣全部加上 k。最後輸出整個矩陣。

暴力解

最簡單的當然是直接遍歷

for(int i = x1 ; i <= x2 ; i++){
    for(int j = y1 ; j <= y2 ; j++){
        d[i][j] += k;
    }
}

非常簡單的寫法，我相信就算剛學程式都看得懂。

同樣分析一下：
最糟情況，就是對整個陣列進行Q次修改，所以會執行Q × N × M次。只要 Q、N、M 到 10³，就會執行 10⁹，基本上到 OJ 就是TLE 。

二維差分

由於直接講他的定義有點不太好懂，我們以一維差分當作切入點。
一維差分定義為：D[i] = A[i] - A[i-1]，也就是 D[i] 表示 當前項跟前一項差了多少 ，同樣 D[i][j] 表示在這個位置(也就是 (i,j) )「獨立新增」的數值。

我們可以把它想像成在計算「這一格比起周圍增加了多少」。
一維差分：D[i]=A[i]−A[i−1]
二維差分：
拿走當前格子的總值：A[i][j]
減掉上面那一整塊的總值：−A[i−1][j]
減掉左邊那一整塊的總值：−A[i][j−1]
注意：當你減掉上面和左邊時，左上角那一塊（A[i−1][j−1]）被扣了兩次
所以最終要補回扣兩次的部分：+A[i−1][j−1]
以上是如何得出二維差分陣列，但是坦白說不常用到，常用到的應該是修改的部分。

你會發現其跟 二維前綴和 公式的符號是相反的。

上篇有提到：差分可以理解為前綴和的逆運算
同樣，二維差分是二維前綴和的逆運算。
為了在 O(1) 時間內標記一個矩形的變化，我們需要在四個座標點上做記號：

1. D[x1][y1] += k：讓右下角所有格子都加上 k。

當我們對二維差分 D[x1][y1] += k 會影響一個以 (i,j) 為左上角，一直延伸到矩陣右下角的矩形，也就是所有座標同時滿足 x≥i 且 y≥j 的點（即 (i,j) 的右下角區域），在最後計算前綴和時都會加到。

2. D[x1][y2+1] -= k：把多加的部分在右側邊界外扣掉。
3. D[x2+1][y1] -= k：把多加的部分在下方邊界外扣掉。
4. D[x2+1][y2+1] += k：因為左上角多扣了一次，要補回來。

這邊原理其實也是在【演算法新手村】[初階]筆記05 - 前綴和(二維)提到的容斥原理。

程式碼實作 (C++)

#include <iostream>
#include <vector>
using namespace std;

long long d[1005][1005]; 

int main() {
    int n, m, q;
    cin >> n >> m >> q;

    // 1. 進行 Q 次區間修改
    while (q--) {
        int x1, y1, x2, y2, k;
        cin >> x1 >> y1 >> x2 >> y2 >> k;
        d[x1][y1] += k;
        d[x1][y2 + 1] -= k;
        d[x2 + 1][y1] -= k;
        d[x2 + 1][y2 + 1] += k;
    }

    // 2. 還原矩陣 (對差分矩陣求二維前綴和)
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // 使用二維前綴和公式還原
            d[i][j] = d[i][j] + d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
            cout << d[i][j] << (j == m ? "" : " ");
        }
        cout << endl;
    }
    return 0;
}

注意事項

陣列大小

二維差分會動到 x2 + 1 和 y2 + 1，所以陣列大小一定要開得比題目要求的 N, M 至少大 2（例如題目給 1000，你至少要開 1002）。

初始值

如果原矩陣不是全 0，你可以先對原矩陣做一次「差分化」；或者最簡單的方法：再建立一個新陣列進行差分，直接把修改後的差分矩陣還原後，再加回原矩陣即可。

練習

1. 基礎：LeetCode 2536. Increment Submatrices by One
   • 這題是純粹的二維差分練習，要求對多個子矩陣進行 +1 操作。
2. 基礎：洛谷 P3397 地毯
   • 題目描述非常直觀：在 N × N 的區域鋪上多塊地毯，求每個格子被幾層地毯覆蓋。

這個主題到這邊也就差不多完成啦~ 差分跟前綴和是息息相關的，新手可以慢慢練習、理解，如果不懂可以嘗試畫圖，這邊畫圖會好理解很多喔。
還在想下一個筆記的主題，有點難取捨呢