LeetCode 筆記：Range Sum Query 2D —— 二維前綴和矩陣區間求和 O(1) 查詢

LeetCode 304：給定不可變二維矩陣，多次查詢子矩陣 (row1, col1) 到 (row2, col2) 的元素和。構建 二維前綴和 輔助矩陣，構造 O(mn)，查詢 O(1)。

一、二維前綴和定義

sum[i][j] = 原矩陣 (0,0) 到 (i-1, j-1) 區域和（擴展一行一列為 0，便於邊界處理）。

遞推：

sum[i][j] = matrix[i-1][j-1] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];

二、區間查詢公式

query(r1, c1, r2, c2) =
    sum[r2+1][c2+1] - sum[r1][c2+1] - sum[r2+1][c1] + sum[r1][c1];

三、完整 C++ 實現

class NumMatrix {
    vector> sum;
public:
    NumMatrix(vector>& matrix) {
        int m = matrix.size();
        int n = m ? matrix[0].size() : 0;
        sum.assign(m+1, vector(n+1, 0));
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                sum[i][j] = matrix[i-1][j-1] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
    }
    int sumRegion(int r1, int c1, int r2, int c2) {
        return sum[r2+1][c2+1] - sum[r1][c2+1] - sum[r2+1][c1] + sum[r1][c1];
    }
};

四、關鍵實現細節

1. 擴展邊界：sum 尺寸 (m+1)×(n+1)，第 0 行/列為 0，避免查詢時判邊界。
2. 下標轉換：原矩陣 [i][j] 對應 sum[i+1][j+1]。
3. 只讀矩陣：構造後不再修改，適合多次查詢場景。

五、複雜度

• 構造：O(mn) 時間、O(mn) 空間。
• 查詢：O(1) 時間。

六、擴展：可更新版本

若矩陣需支持單點更新，改用 二維樹狀數組，更新/查詢均為 O(log m log n)。