https://leetcode.com/problems/range-sum-query-immutable/description/
可以直接 二維 DP 來解決。題解巧妙使用了 Range Sum 的特點(diǎn)：sumRange(i -> j) = sumRange(0 -> j) - sumRange(0 -> i-1)呈昔，從而實(shí)現(xiàn)了降維弃舒。
class NumArray {
private int[] sumSoFar;
public NumArray(int[] nums) {
sumSoFar = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
sumSoFar[i + 1] = sumSoFar[i] + nums[i];
}
}
public int sumRange(int i, int j) {
return sumSoFar[j + 1] - sumSoFar[i];
}
}
Follow up: 304. Range Sum Query 2D - Immutable
https://leetcode.com/problems/range-sum-query-2d-immutable/description/
Similar idea. 二維 DP。
dp[i][j] 為 從(0, 0) --> (i, j) 的sum
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i][j]
sumRange(row1, col1, row2, col2) =
dp[row2][col2] - dp[row1 - 1][col2] - dp[row2][col1 - 1] + dp[row1 - 1][col1 - 1]
