給定 2D 矩陣
matrix，設計一個類別NumMatrix，支援查詢子矩陣(row1, col1)到(row2, col2)的元素和。sumRegion會被多次呼叫。
Example:
Input: matrix = [[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]] sumRegion(2,1,4,3) = 8
Intuition
TIP
核心思路：預計算 2D 前綴和矩陣，查詢時用容斥原理（Inclusion-Exclusion）O(1) 算出任意子矩陣的和。
prefix[i][j]= 從(0,0)到(i-1,j-1)的矩形元素和- 查詢
(r1,c1)到(r2,c2)的和：prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1] - 預處理 O(m*n)，每次查詢 O(1)
Approaches
1. Brute Force (scan per query) — Query O(m*n) / O(1)
- Idea: 每次
sumRegion都遍歷子矩陣的所有元素求和 - Time: 初始化
O(1)，查詢O(m * n)最壞 - Space:
O(1)- 不需額外空間
class NumMatrix(private val matrix: Array<IntArray>) {
fun sumRegion(row1: Int, col1: Int, row2: Int, col2: Int): Int {
var sum = 0
for (r in row1..row2) {
for (c in col1..col2) {
sum += matrix[r][c]
}
}
return sum
}
}⭐ 2. 2D Prefix Sum — Init O(m*n), Query O(1) / O(m*n)
- Idea: 預計算 2D 前綴和，查詢時用容斥原理 O(1) 計算
- Time: 初始化
O(m * n)，查詢O(1) - Space:
O(m * n)- 前綴和矩陣
class NumMatrix(matrix: Array<IntArray>) {
private val prefix: Array<IntArray>
init {
val m = matrix.size
val n = matrix[0].size
prefix = Array(m + 1) { IntArray(n + 1) }
for (r in 1..m) {
for (c in 1..n) {
prefix[r][c] = matrix[r - 1][c - 1] +
prefix[r - 1][c] + prefix[r][c - 1] - prefix[r - 1][c - 1]
}
}
}
fun sumRegion(row1: Int, col1: Int, row2: Int, col2: Int): Int {
return prefix[row2 + 1][col2 + 1] -
prefix[row1][col2 + 1] -
prefix[row2 + 1][col1] +
prefix[row1][col1]
}
}WARNING
容斥原理圖示：要求區域 D 的和，用「大矩形 - 上方 - 左方 + 左上角（被減兩次）」。前綴和矩陣多一行一列（padding），避免邊界判斷。
🔑 Takeaways
- Pattern: 2D 區間查詢 -> 2D 前綴和 + 容斥原理
- Key trick: 前綴和矩陣加 padding（大小
(m+1) x (n+1)）簡化邊界處理；容斥公式prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]要熟記