304. Range Sum Query 2D - Immutable

題目描述

給定一個二維矩陣 matrix，實作 NumMatrix 類別：

• NumMatrix(int[][] matrix) — 以二維整數矩陣初始化物件
• int sumRegion(int row1, int col1, int row2, int col2) — 回傳矩形區域（左上角 (row1, col1)、右下角 (row2, col2)）的元素總和

sumRegion 可能被呼叫非常多次。

解題思路

二維前綴和（2D Prefix Sum）

將一維前綴和推廣到二維：定義 P[i][j] 為矩陣左上角 (0,0) 到 (i-1, j-1) 的所有元素總和（即前 i 行、前 j 列的矩形和）。特別地，P[0][j] = P[i][0] = 0（邊界為零）。

建構公式（容斥原理）：

P[i][j] = matrix[i-1][j-1]
         + P[i-1][j]   （上方矩形）
         + P[i][j-1]   （左方矩形）
         - P[i-1][j-1] （左上角重複計算，需扣除）

查詢矩形 (r1, c1) 到 (r2, c2) 的和：

sumRegion(r1, c1, r2, c2)
  = P[r2+1][c2+1]
  - P[r1][c2+1]   （扣除上方多餘部分）
  - P[r2+1][c1]   （扣除左方多餘部分）
  + P[r1][c1]     （左上角被扣了兩次，補回一次）

視覺化理解

想像把整個矩陣分成四塊：

• 大矩形 P[r2+1][c2+1]（從原點到右下角）
• 減去上方矩形 P[r1][c2+1]
• 減去左方矩形 P[r2+1][c1]
• 加回被重複扣除的左上角 P[r1][c1]

這就是二維版本的容斥原理，將每次查詢降為 O(1)。

時間複雜度

• 建構子：O(m × n)，需要遍歷整個矩陣一次來建立二維前綴和表。
• sumRegion 查詢：O(1)，每次查詢只需 4 次陣列存取和 3 次加減法。

若共有 q 次查詢，總時間為 O(m×n + q)，而暴力法為 O(m×n×q)。

空間複雜度

O(m × n)，額外儲存大小為 (m+1) × (n+1) 的前綴和表。這個空間開銷是必要的，用空間換取每次查詢的 O(1) 時間。

替代方案

方案一：對每行做一維前綴和

對矩陣每一行分別建立前綴和陣列。查詢時，對區域內每行用 O(1) 求行內的列範圍和，再將這些行和累加。

• 優點：建構時間仍 O(m×n)；對「整行跨度」的查詢有優化效果。
• 缺點：查詢時間 O(r2-r1+1) = O(m)，不如二維前綴和的 O(1)；對大量查詢效率較差。

方案二：暴力求和

每次 sumRegion 都雙重迴圈累加矩形內所有元素。

• 優點：O(1) 額外空間，不需要預處理。
• 缺點：每次查詢 O(m×n)，大量查詢時效率極差，無法通過本題的時間限制。

方案三：2D 線段樹或 2D 樹狀陣列（BIT）

若矩陣元素可以更新，2D BIT 可以 O(log m × log n) 時間完成點更新和矩形查詢。

• 優點：支援動態更新，比重建前綴和（O(m×n)）更有效率。
• 缺點：對本題（矩陣不可變）屬於過度設計，程式碼複雜度遠高於二維前綴和，且常數因子更大。

延伸問題

1. 如果矩陣允許更新怎麼辦？ 若 matrix[i][j] 可被修改，使用二維樹狀陣列（2D Fenwick Tree）可以在 O(log m × log n) 時間內完成單點更新和矩形查詢，是二維可更新區間查詢的標準解法。

2. 最大子矩陣和：給定矩陣，找到和最大的子矩陣。一種解法是固定上下行，用二維前綴和壓縮為一維陣列，再用 Kadane's algorithm 求最大子陣列和；總時間複雜度 O(m² × n)。

3. 計算等於 target 的子矩陣數：給定矩陣和目標值 target，找有多少個子矩陣的和等於 target（LC 1074）。可固定上下行壓縮為一維，再用 HashMap 統計前綴和，時間複雜度 O(m² × n)，是二維前綴和的進階應用。