{x}
blog image

Range Sum Query - Immutable

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

  1. 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]

Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

 

Constraints:

  • 1 <= nums.length <= 104
  • -105 <= nums[i] <= 105
  • 0 <= left <= right < nums.length
  • At most 104 calls will be made to sumRange.

Solution Explanation: Range Sum Query - Immutable

This problem requires designing a data structure that efficiently handles multiple sum queries on a given array. The most efficient approach is to use a prefix sum array.

Prefix Sum Array:

A prefix sum array, s, stores the cumulative sum of elements up to each index in the original array, nums. Specifically, s[i] contains the sum of all elements from nums[0] to nums[i-1]. This allows for constant-time range sum queries.

Algorithm:

  1. Initialization (__init__ or constructor):

    • Create a prefix sum array s with a size one larger than the input array nums.
    • Initialize s[0] to 0.
    • Iterate through nums, calculating the cumulative sum at each index: s[i+1] = s[i] + nums[i].

  2. Sum Range Query (sumRange):

    • Given left and right indices, the sum of the elements in the range [left, right] is simply s[right + 1] - s[left]. This works because s[right + 1] contains the sum up to nums[right], and s[left] contains the sum up to nums[left - 1]. Subtracting these gives the sum of the elements in the desired range.

Time Complexity:

  • Initialization: O(n), where n is the length of the input array nums. This is because we iterate through the array once to compute the prefix sums.
  • Sum Range Query: O(1). Calculating the difference between two elements in the prefix sum array takes constant time.

Space Complexity:

  • O(n). We use an extra array s of size n+1 to store the prefix sums.

Example:

Let's say nums = [-2, 0, 3, -5, 2, -1].

The prefix sum array s would be: [0, -2, -2, 1, -4, -2, -3]

To calculate the sum of the range [0, 2]: s[3] - s[0] = 1 - 0 = 1

To calculate the sum of the range [2, 5]: s[6] - s[2] = -3 - (-2) = -1

To calculate the sum of the range [0, 5]: s[6] - s[0] = -3 - 0 = -3

The provided code in various languages implements this prefix sum approach. Each implementation follows the same basic algorithm, with only minor syntactic differences depending on the language. The core idea is to efficiently precompute the prefix sums to enable fast range sum queries.