Range Sum Query - Immutable

Problem Description

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 with the following methods:

• 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.

Key Insights

• The problem requires efficient computation of the sum over multiple queries on a static array.
• A naive approach would result in O(n) time complexity per query, which is inefficient for larger arrays and multiple queries.
• A prefix sum array can be utilized to allow each sumRange query to be answered in O(1) time after an initial O(n) preprocessing step.

Space and Time Complexity

Time Complexity: O(n) for initialization and O(1) for each sumRange query.
Space Complexity: O(n) for storing the prefix sum array.

Solution

To efficiently compute the range sums, we can use a prefix sum array. This array is built such that each element at index i contains the sum of the elements from the start of the nums array up to index i. This allows us to compute the sum of any subarray from index left to right using the formula:

• sumRange(left, right) = prefixSum[right + 1] - prefixSum[left]

The prefix sum array can be built in a single pass through the nums array, ensuring that subsequent queries can be answered in constant time.

Code Solutions