Solution: Range Sum Query - Immutable

Statement

You are given an integer array, nums, and you need to handle multiple queries of the following type:

• Query: Calculate the sum of elements in nums between indices i and j (inclusive), where i <= j.

Implement the NumArray class to support the following operations efficiently:

• Constructor (NumArray(int[] nums): Initializes the object with the integer array nums.

• int sum_range(int i, int j): Returns the sum of the elements of nums between indices i and j (inclusive), i.e., the sum of nums[i] + nums[i + 1] + ... + nums[j].

Constraints:

• $1 \leq$ nums.length $\leq 10^3$

• $-10^5 \leq$ nums[i] $\leq 10^5$

• $0 \leq$ i $\leq$ j $<$ nums.length

• At most, $10^3$ calls will be made to sum_range.

Solution

The algorithm uses a prefix sum array to enable efficient range sum queries. First, it constructs the prefix sum array, where each element at index $i+1$ represents the sum of all elements from the start of the input array nums up to index $i$. With this setup, the sum of any subarray from index $i$ to $j$ can be calculated in constant $O(1)$ time by subtracting the prefix sum at index $i$ from the prefix sum at index $j+1$. This approach avoids recalculating sums for overlapping subarrays, making it highly efficient for multiple queries.

The steps of the algorithm are as follows:

Constructor: The constructor initializes the object with the input list nums and calculates the prefix sum array.

• Initialize an array sum to store the prefix sums. The length of the sum is len(nums) + 1 because we need an extra element to handle the sum of elements from the start (index 0). Initially, sum is filled with zeros.

• The loop iterates through each element of the nums array to calculate the prefix sums. sum[i + 1] = sum[i] + nums[i] updates sum to store the cumulative sum of elements in nums.

  • sum[i + 1] is assigned the sum of all elements from the beginning of nums up to index i.

  • The i + 1 indexing ensures that the prefix sum at index i in sum corresponds to the sum of the first i elements of nums.

sum_range method: This method efficiently calculates the sum of elements in nums between indices i and j (inclusive) using the prefix sum array.

• sum[j + 1]: This gives the cumulative sum of elements up to index j in nums.

• sum[i]: This gives the cumulative sum of elements up to index i - 1.

• The difference sum[j + 1] - sum[i] subtracts the sum of elements before index i, leaving only the sum of elements between indices i and j (inclusive).

Let’s look at the following illustration to get a better understanding of the solution: