DP-10. Range Sum Query - Immutable

Problem

LeetCode 303. Range Sum Query - Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:

You may assume that the array does not change.
There are many calls to sumRange function.

Explanation

This is a simple problem. As we would like to get the sum quickly, so we would better calculate them once and save them. So, we can take use of the memoization of dp. When we initialize the dp, we save all the sum ended at the index. When we need to get the range sum, we can easily use subtraction. Take care the border. Both side are included.

Solution

Time complexity: O(1) each query, precomputation is O(n)
Space complexity: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
class NumArray {
int[] dp;
public NumArray(int[] nums) {
dp = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
dp[i + 1] = dp[i] + nums[i];
}
}

public int sumRange(int i, int j) {
return dp[j + 1] - dp[i];
}
}