303. Range Sum Query - Immutable

T: sumRange: O(1)

S: O(n)

class NumArray {

    int[] presum;
    public NumArray(int[] nums) {
        presum = new int[nums.length+1];
        presum[0] = 0;
        for (int i = 1; i <= nums.length; i++) {
            presum[i] = presum[i-1] + nums[i-1];
        }
    }
    
    public int sumRange(int left, int right) {
        return presum[right+1] - presum[left];
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(left,right);
 
     0. 1. 2.  3. 4.  5
 [[[-2, 0, 3, -5, 2, -1]], 
           1         -3
           
           
 
     [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]


[2,5] = [0, 5] - [0, 1] = -3 - (-2) = -1
      = prefixsum[6] - prefixsum[2]

  -2, 0, 3, -5, 2, -1
0 -2  -2 1  -4  -2 -3
   
    
  sum[2,5] = presum[6] - presum[2] = -3 -(-2) = -1  
   */