二維差分

推薦事前閱讀：二維差分數組

思路

在寫的過程要注意，差分數組裡面不能存放原始資料，
否則會在計算每一格的數值變動時，錯誤的把原始數值也傳遞下去，導致一系列的錯誤。

程式碼

二維前綴和

#include <iostream>
#include <array>
using namespace std;
const int MX = 1005;
array<array<long long, MX>, MX> diff;
array<array<long long, MX>, MX> nums;
int main() {
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 0; i < n; i++) { // 輸入原始資料
        for(int j = 0; j < m; j++) {
            cin >> nums[i + 1][j + 1];
        }
    }
    int x1, y1, x2, y2, k;
    for(int i = 0; i < q; i++) { // 差分操作，題目是 1-indexed 的，不需要轉換
        cin >> x1 >> y1 >> x2 >> y2 >> k;
        diff[x1][y1] += k;
        diff[x1][y2 + 1] -= k;
        diff[x2 + 1][y1] -= k;
        diff[x2 + 1][y2 + 1] += k;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
            nums[i][j] += diff[i][j]; // 原始數組加上偏移量
            cout << nums[i][j] << (j == m ? "" : " "); 
        }
        cout << "\n";
    }
}

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$