2536. 子矩陣元素加 1

思路

二維差分數組的經典題目。

假設有一個數列是$[1, 2, 5, 1, 7]$，
因為 0 + 1 = 1, 1 + 1 = 2, 2 + 3 = 5, 5 - 4 = 1, 1 + 6 = 7,
所以這個數列的差分數組是 $[1, 1, 3, -4, 6]$，也就是上一個數字加上多少會變成下一個數字。
如果要用差分數組還原出原本的數組，就對他做前綴和即可。

差分數組的好處在於，能將區域遞增固定數值 $O(n)$ 操作轉化為 $O(1)$ 操作。
假設想要讓$[2, 5, 1]$同時增加 10，數組會變成 $[1, 12, 15, 11, 7]$，差分數組會變成$[1, 11, 3, -4, -4]$
跟原本的差分數組相比，在2所在的位置，差分數組數值增加 10，在7所在的位置減去10，
也就是說，想要將nums[i] ~ nums[j]的數字統一增加x，
在差分數組中，只要將diff[i] += x，diff[j + 1] -= x就可以了。

二維的差分同理，每次讓diff[i][j] += x，相當將在 (i, j) 右下的所有區塊增加x，
因此，在二維差分時，如果要將區塊統一增加x，需要四段操作，分別在區塊的四個角落（左上閉區間、其他開區間）

在操作時，需要避免出界（除非你開足夠的空間）

程式碼

1. 二維差分

class Solution {
public:
    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
        vector<vector<int>> diff(n, vector<int>(n, 0));
        for(auto q : queries) {
            ++diff[q[0]][q[1]];  // 左上增加
            if(q[3] + 1 < n) { 
                --diff[q[0]][q[3] + 1];
            }
            if(q[2] + 1 < n) {
                --diff[q[2] + 1][q[1]];
            }
            if(q[2] + 1 < n && q[3] + 1 < n) {
                ++diff[q[2] + 1][q[3] + 1];
            }
        }
        for(int i = 0; i < n; ++i) {
            for(int j = 0;  j < n; ++j) {
                // diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
                if(i > 0) diff[i][j] += diff[i - 1][j];
                if(j > 0) diff[i][j] += diff[i][j - 1];
                if(i > 0 && j > 0) diff[i][j] -= diff[i - 1][j - 1];
            }
        }
        return diff;
    }
};

2. 足夠空間（易懂）

class Solution {
public:
    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
        vector<vector<int>> diff(n + 2, vector<int>(n + 2, 0));
        for(auto q : queries) {
            int r1 = q[0], c1 = q[1], r2 = q[2], c2 = q[3];
            ++diff[r1 + 1][c1 + 1];
            --diff[r1 + 1][c2 + 2];
            --diff[r2 + 2][c1 + 1];
            ++diff[r2 + 2][c2 + 2];
        }
        vector<vector<int>> res(n, vector<int>(n, 0));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
                res[i - 1][j - 1] = diff[i][j];
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(q + n^2)$，q 是 queries 的長度
• 空間複雜度：$O(n^2)$