解題說明
題目描述
給定一個二維矩陣 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)。
C++ 解法
複雜度分析
時間複雜度
- 建構子：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) 時間。
虛擬碼
Constructor NumMatrix(matrix):
1. Let m = rows, n = cols
2. Create P of size (m+1) x (n+1), initialized to 0
3. For i from 1 to m:
For j from 1 to n:
P[i][j] = matrix[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]
sumRegion(row1, col1, row2, col2):
1. Return P[row2+1][col2+1] - P[row1][col2+1] - P[row2+1][col1] + P[row1][col1]其他解法
替代方案
方案一：對每行做一維前綴和
對矩陣每一行分別建立前綴和陣列。查詢時，對區域內每行用 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)）更有效率。
- 缺點：對本題（矩陣不可變）屬於過度設計，程式碼複雜度遠高於二維前綴和，且常數因子更大。
延伸思考
延伸問題
-
如果矩陣允許更新怎麼辦？ 若
matrix[i][j]可被修改，使用二維樹狀陣列（2D Fenwick Tree）可以在 O(log m × log n) 時間內完成單點更新和矩形查詢，是二維可更新區間查詢的標準解法。 -
最大子矩陣和：給定矩陣，找到和最大的子矩陣。一種解法是固定上下行，用二維前綴和壓縮為一維陣列，再用 Kadane's algorithm 求最大子陣列和；總時間複雜度 O(m² × n)。
-
計算等於 target 的子矩陣數：給定矩陣和目標值 target，找有多少個子矩陣的和等於 target（LC 1074）。可固定上下行壓縮為一維，再用 HashMap 統計前綴和，時間複雜度 O(m² × n)，是二維前綴和的進階應用。