303. Range Sum Query - Immutable Easy

Given an integer array nums, handle multiple queries of the following type:

Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

• NumArray(int[] nums) Initializes the object with the integer array nums.
• int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

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

Approach

Input: An integer array nums

Output: An Array class capable of efficiently computing the sum of elements from index left to right (inclusive)

This problem falls under the 1D Prefix Sum category.

We can precompute a prefix sum array pre_sum, where pre_sum[i] represents the sum of elements in nums from index 0 to i-1.

When querying the sum of the interval [left, right], we can use the formula pre_sum[right + 1] - pre_sum[left] to quickly calculate the total sum from nums[left] to nums[right].

Implementation

python

class NumArray:
    def __init__(self, nums: List[int]):
        # Initialize the prefix sum array with the first element as 0 (representing the sum of an empty array)
        self.pre_sum = [0]
        # Iterate over the input array to calculate prefix sums
        for num in nums:
            # Current prefix sum = previous prefix sum + current number
            self.pre_sum.append(self.pre_sum[-1] + num)

    def sumRange(self, left: int, right: int) -> int:
        # Use the prefix sum formula to calculate the interval sum: pre_sum[right+1] - pre_sum[left]
        # Returns the sum from nums[left] to nums[right]
        return self.pre_sum[right + 1] - self.pre_sum[left]

javascript

// Constructor: passed the original array nums upon initialization
const NumArray = function(nums) {
    // Create the prefix sum array, initially [0]
    // preSum[i] represents the total sum from nums[0] to nums[i - 1]
    this.preSum = [0];

    // Build the prefix sum array, making sure to populate starting from index 1
    for (let num of nums) {
        // Current item = previous item's prefix sum + current number
        this.preSum.push(this.preSum.at(-1) + num);
    }
};

// Implement sumRange(left, right): Returns the sum of the interval [left, right]
NumArray.prototype.sumRange = function(left, right) {
    // Interval sum = preSum[right + 1] - preSum[left]
    return this.preSum[right + 1] - this.preSum[left];
};

Complexity Analysis

• Time Complexity: O(n) for initialization, O(1) for each query
• Space Complexity: O(n)

Links

303. Range Sum Query - Immutable (English)303. 区域和检索 - 数组不可变 (Chinese)