書接上回：【演算法新手村】[初階]筆記04 - 前綴和(一維)

接著上篇一維前綴和的概念，我們這篇進入二維空間。
當資料從一條線變成一個平面（矩陣），我們該如何快速算出其中一個「子矩陣」的總和呢？

二維前綴和 (2D Prefix Sum)

給定一個 N × M 的矩陣，現在有 Q 次詢問，每次給定左上角座標 (x1, y1) 與右下角座標 (x2, y2)，求這個子矩陣內所有元素的和。

暴力法

這是最容易想到的，每次詢問都用雙層 for 迴圈跑一遍，for迴圈會跑Q×N×M次(複雜度同樣是 O(Q×N×M)。假設N, M, Q 都為 1000 時，總運算量會到 10⁹，這是很危險的(容易TLE) 。

二維前綴和

1. 定義與預處理

我們可額外建立一個二維陣列S，這邊定義 S[i][j] 為：從矩陣左上角 (1, 1) 到右下角 (i, j) 所圍成的矩形區域總和。
舉例來說就是S[2][2] = (1,1)+(1,2)+(2,1)+(2,2)

這邊也是先以 口語化 用法舉例

如何算出 S[i][j] 呢？我們可以利用上學時學過的容斥原理 (Inclusion-Exclusion Principle)：
這是目標：

由於我們所計算出來的都是矩形，所以我們可以利用先前算出來的前綴和拼湊出新的部分

1. 先拿左邊一塊：S[i][j-1]
   
2. 加上上面一塊：S[i-1][j]
   
3. 扣掉重複計算的左上角：S[i-1][j-1]
   
4. 加上當前格子的值：A[i][j]
   

公式：

2. 查詢區間和

當我們要查詢左上角 (x1, y1) 到右下角 (x2, y2) 的子矩陣和時：
這是目標：

1. 大矩形：S[x2][y2]
   
2. 扣掉左邊多餘部分：S[x2][y1-1]
3. 扣掉上面多餘部分：S[x1-1][y2]
4. 把左上角被多扣的部分補回來：S[x1-1][y1-1]

查詢公式：

3. 比較

預處理 O(N×M)，查詢是常數時間(簡單的加減法，也就是O(1)的複雜度)。

程式碼實作 (C++)

同樣建議從索引 1 開始，以避免處理索引越界。

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

long long a[1005][1005];
long long s[1005][1005];

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            // 預處理前綴和表格
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
        }
    }

    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        // O(1) 查詢子矩陣和
        long long ans = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
        cout << ans << endl;
    }
    return 0;
}

練習

1. 基礎：LeetCode 304. Range Sum Query 2D - Immutable

LeetCode 304. Range Sum Query 2D - Immutable 詳解

2. 小挑戰：最大子矩陣和 (UVa 108: Maximum Sum)

這題雖然用前綴和比較慢，但理解了二維前綴在之後理解這類後續問題時會有幫助。
UVA 108 - Maximum Sum 詳解

3. ：ZeroJudge d206. 00108 - Maximum Sum

寫這篇，畫圖畫死我了...，回到正題，二維相較於一維稍微複雜了一些，主要涉及到一些幾何上的小問題，弄清楚之後應該也還算是簡單啦，務必多練習才能真正鍛鍊自己，Practice make Perfect!