Range Sum Query - Immutable


#1

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

Example:

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

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

Note:

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

#2

Pre-compute the sum until each index and return the difference until the index start.

class NumArray {
    int[] dp;
    public NumArray(int[] nums) {
        int sum = 0;
        this.dp = new int[nums.length];
        for(int i=0;i<nums.length;i++){
            sum += nums[i];
            dp[i] = sum;
        }
    }
    
    public int sumRange(int i, int j) {
        if(i==0) return dp[j];
        return dp[j]-dp[i-1];
    }
}