Range Sum Query Immutable

To solve this coding challenge, we can utilize a technique known as prefix sum, which allows us to preprocess the given array in such a way that it facilitates efficient querying of subarray sums. The prefix sum array stores cumulative sums of the elements from the beginning of the array up to each index. This way, any subarray sum can be quickly computed using the difference between two prefix sums.

Explanation

Concept

1. Prefix Sum Array :
• Create a prefix sum array where each element at index
  i
  represents the sum of all elements from the beginning of the array up to index
  i-1
  .
• For example, if the input array is
  [a, b, c, d]
  , the prefix sum array will be
  [0, a, a+b, a+b+c, a+b+c+d]
  .
2. Querying Sum :
• To find the sum of elements between indices
  left
  and
  right
  , compute the difference between the prefix sums at
  right+1
  and
  left
  .
• This works because the prefix sum at
  right+1
  includes the sum of all elements up to
  right
  , and the prefix sum at
  left
  includes the sum of all elements up to
  left-1
  . Hence, the difference gives the sum of elements in the range
  [left, right]
  .

Steps in Pseudocode

Step-by-Step Explanation

3. Initialization :
• Initialize an empty list called
  prefix_sum
  .
• Set the first element of
  prefix_sum
  to
  0
  since there is no element before the start of the array.
4. Building Prefix Sum Array :
• Iterate through each element of the input array.
• Append the sum of the current element and the last element of the
  prefix_sum
  to the
  prefix_sum
  list.
5. Query Function (
   sumRange
   ) :
• For each query, return the difference between the elements at indices
  right + 1
  and
  left
  in the
  prefix_sum
  array.

Detailed Steps in Pseudocode

                                            
# Class definition for NumArray
class NumArray:
    
    # Constructor to initialize the object with the given integer array
    method __init__(nums):
        # Initialize an empty prefix_sum list with an initial value of 0
        prefix_sum = [0]
        
        # Loop through each element in the given nums array
        for each num in nums:
            # Append the current prefix sum + current number to the prefix_sum list
            prefix_sum.append(prefix_sum[-1] + num)
    
    # Method to calculate the sum of elements between indices left and right (inclusive)
    method sumRange(left, right):
        # Return the difference between prefix_sum at index right+1 and prefix_sum at index left
        return prefix_sum[right + 1] - prefix_sum[left]

                                        

Explanation

Initialization

• The
  __init__
  method receives the integer array
  nums
  and constructs the
  prefix_sum
  array.
• By starting the
  prefix_sum
  array with 0, it simplifies the calculation of prefix sums, as the initial value represents an empty sum.

Building Prefix Sum Array

• For each element in
  nums
  , add its value to the last element of
  prefix_sum
  and append this new sum to
  prefix_sum
  .
• This continuous accumulation ensures that each subsequent index in
  prefix_sum
  represents the cumulative sum of elements of
  nums
  up to that point.

Query Function (`sumRange`)

• The
  sumRange
  method takes two arguments,
  left
  and
  right
  , representing the indices of the subarray whose sum we need.
• By calculating the difference
  prefix_sum[right + 1] - prefix_sum[left]
  , it gives the sum of the elements from
  left
  to
  right
  , inclusive.
• This difference works because
  prefix_sum[right + 1]
  includes all elements up to
  right
  , and subtracting
  prefix_sum[left]
  removes the elements before
  left
  .

This approach ensures that both initialization and query operations are efficient. The preprocessing step (building the prefix sum array) takes O(n) time, and each query is answered in O(1) time.