303. Range Sum Query – Immutable – Leetcode Solutions

Example 1:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

class NumArray:
    def __init__(self, nums: List[int]):
        """
        Initialize the NumArray object with the given integer array.
        This constructor precomputes the prefix sum to optimize the sumRange queries.
        
        :param nums: List[int] - List of integers representing the array.
        """
        # Create a list to store the prefix sum.
        # prefix_sum[i] will hold the sum of elements from nums[0] to nums[i-1].
        self.prefix_sum = [0] * (len(nums) + 1)  # Extra element for easier indexing

        # Populate the prefix sum array.
        for i in range(1, len(nums) + 1):
            # Prefix sum at index i is sum up to i-1 in nums
            self.prefix_sum[i] = self.prefix_sum[i - 1] + nums[i - 1]

    def sumRange(self, left: int, right: int) -> int:
        """
        Returns the sum of elements in the array between indices left and right inclusive.
        
        :param left: int - The starting index of the range.
        :param right: int - The ending index of the range.
        :return: int - The sum of elements between indices left and right.
        """
        # Using the prefix sum array, we can calculate the sum of any subarray in O(1) time.
        # The sum between left and right is the difference between the prefix sum at right+1
        # and the prefix sum at left.
        return self.prefix_sum[right + 1] - self.prefix_sum[left]

class NumArray {
public:
    // Vector to store the prefix sum
    vector<int> prefix_sum;
    
    // Constructor to initialize the NumArray object with the given integer array
    NumArray(vector<int>& nums) {
        // Initialize prefix_sum vector with an extra element for easier indexing
        prefix_sum.resize(nums.size() + 1, 0);
        
        // Populate the prefix_sum array
        // prefix_sum[i] will store the sum of elements from nums[0] to nums[i-1]
        for (int i = 1; i <= nums.size(); i++) {
            prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1];
        }
    }
    
    // Function to return the sum of elements between indices left and right (inclusive)
    int sumRange(int left, int right) {
        // The sum of elements from index left to right is the difference between 
        // prefix_sum[right + 1] and prefix_sum[left]
        return prefix_sum[right + 1] - prefix_sum[left];
    }
};

var NumArray = function(nums) {
    // Initialize a prefixSum array to store cumulative sums.
    // The prefixSum array will have one extra element to simplify index calculations.
    this.prefixSum = new Array(nums.length + 1).fill(0);

    // Populate the prefixSum array such that prefixSum[i + 1] contains the sum of elements
    // from nums[0] to nums[i].
    for (let i = 0; i < nums.length; i++) {
        this.prefixSum[i + 1] = this.prefixSum[i] + nums[i];
    }
};

/** 
 * @param {number} left 
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function(left, right) {
    // To get the sum of elements between indices `left` and `right` (inclusive),
    // subtract the cumulative sum at prefixSum[left] from prefixSum[right + 1].
    return this.prefixSum[right + 1] - this.prefixSum[left];
};

class NumArray {
    // Prefix sum array to store cumulative sums
    private int[] prefixSum;

    // Constructor to initialize the prefix sum array
    public NumArray(int[] nums) {
        // Initialize the prefixSum array with an extra element
        prefixSum = new int[nums.length + 1];

        // Populate the prefixSum array
        // prefixSum[i + 1] will store the sum of elements from nums[0] to nums[i]
        for (int i = 0; i < nums.length; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
    }
    
    // Method to calculate the sum of elements between indices left and right (inclusive)
    public int sumRange(int left, int right) {
        // Use the prefixSum array to get the sum in constant time
        // The sum of elements from index 'left' to 'right' is:
        // prefixSum[right + 1] - prefixSum[left]
        return prefixSum[right + 1] - prefixSum[left];
    }
}