https://leetcode.com/problems/range-sum-query-immutable/description/
可以直接 二维 DP 来解决。题解巧妙使用了 Range Sum 的特点：sumRange(i -> j) = sumRange(0 -> j) - sumRange(0 -> i-1)，从而实现了降维。
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]
