Leetcode: 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:

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

Understand the problem:
For the naive solution, each time we call the sumRange(lo, hi), we sum up the numbers and return the result. So the time complexity would be O(n). 

Note that there are many calls to sumRange function, so we can calculate the prefix sum in the constructor. Then each time we call the sumRange(lo, hi), we just need to calculate the prefix[hi] - prefix[lo - 1], in O(1) time. 


Code (Java):

public class NumArray {
    private int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
        
        // Calculate the prefix sum
        for (int i = 1; i < nums.length; i++) {
            nums[i] += nums[i - 1];
        }
    }

    public int sumRange(int i, int j) {
        if (i < 0 || i >= nums.length || 
            j < 0 || j >= nums.length || 
            i > j) {
            return 0;
        }
        
        if (i == 0) {
            return nums[j];
        } else {
            return nums[j] - nums[i - 1];
        }
    }
}