Problem Description

The Range Sum Query - Immutable problem asks you to design a data structure that, given an integer array nums, efficiently calculates the sum of elements between two given indices left and right (both inclusive).

Specifically, you will implement a 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 in nums between indices left and right (inclusive), i.e., nums[left] + ... + nums[right].

• 1 ≤ nums.length ≤ 10⁴
• -10⁵ ≤ nums[i] ≤ 10⁵
• 0 ≤ left ≤ right < nums.length
• At most 10⁴ calls will be made to sumRange.

Thought Process

The first idea that comes to mind is to simply add up the elements from left to right each time sumRange is called. This is straightforward, but if there are many queries, it will be slow because each query could take up to O(n) time.

Since the array doesn't change after initialization (it's immutable), we can preprocess the data to make queries faster. We want to avoid recomputing sums for overlapping ranges repeatedly. This leads us to consider some form of prefix sum or cumulative sum, which allows us to compute any range sum in constant time after an initial preprocessing step.

Solution Approach

To answer range sum queries efficiently, we use the Prefix Sum technique:

1. Preprocessing:
   • We create an auxiliary array, prefixSums, where prefixSums[i] stores the sum of nums[0] + nums[1] + ... + nums[i-1].
   • We set prefixSums[0] = 0 for convenience, so prefixSums[1] = nums[0], prefixSums[2] = nums[0] + nums[1], and so on.
2. Querying:
   • To get the sum from left to right, we use the formula: prefixSums[right+1] - prefixSums[left].
   • This works because prefixSums[right+1] includes all elements up to right, and subtracting prefixSums[left] removes the sum up to left-1.

Example Walkthrough

Let's use the input nums = [-2, 0, 3, -5, 2, -1] and see how the solution works step by step.

Step 1: Build prefix sums

• prefixSums[0] = 0
• prefixSums[1] = 0 + (-2) = -2
• prefixSums[2] = -2 + 0 = -2
• prefixSums[3] = -2 + 3 = 1
• prefixSums[4] = 1 + (-5) = -4
• prefixSums[5] = -4 + 2 = -2
• prefixSums[6] = -2 + (-1) = -3

• sumRange(0, 2): prefixSums[3] - prefixSums[0] = 1 - 0 = 1
• sumRange(2, 5): prefixSums[6] - prefixSums[2] = -3 - (-2) = -1
• sumRange(0, 5): prefixSums[6] - prefixSums[0] = -3 - 0 = -3

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(n) per query (since you sum from left to right each time)
• Space Complexity: O(1) extra space (no auxiliary data structures)

• Time Complexity:
  • Preprocessing: O(n) to build prefix sums
  • Query: O(1) per query (just two array lookups and a subtraction)
• Space Complexity: O(n) extra space for the prefix sums array

Code Implementation

class NumArray:
    def __init__(self, nums):
        self.prefixSums = [0]
        for num in nums:
            self.prefixSums.append(self.prefixSums[-1] + num)

    def sumRange(self, left, right):
        return self.prefixSums[right + 1] - self.prefixSums[left]
      

class NumArray {
public:
    vector<int> prefixSums;
    NumArray(vector<int>& nums) {
        prefixSums.push_back(0);
        for (int num : nums) {
            prefixSums.push_back(prefixSums.back() + num);
        }
    }
    int sumRange(int left, int right) {
        return prefixSums[right + 1] - prefixSums[left];
    }
};
      

class NumArray {
    private int[] prefixSums;
    public NumArray(int[] nums) {
        prefixSums = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefixSums[i + 1] = prefixSums[i] + nums[i];
        }
    }
    public int sumRange(int left, int right) {
        return prefixSums[right + 1] - prefixSums[left];
    }
}
      

var NumArray = function(nums) {
    this.prefixSums = [0];
    for (let num of nums) {
        this.prefixSums.push(this.prefixSums[this.prefixSums.length - 1] + num);
    }
};

NumArray.prototype.sumRange = function(left, right) {
    return this.prefixSums[right + 1] - this.prefixSums[left];
};
      

Summary

The Range Sum Query - Immutable problem demonstrates how preprocessing (with prefix sums) can drastically improve performance for repeated range queries on immutable data. By storing cumulative sums, we transform each query from linear to constant time, trading a small amount of extra space and one-time preprocessing for much faster queries. This approach is elegant and widely applicable to similar problems involving range queries on static arrays.