Range Sum Query Immutable

Problem Link

303. Range Sum Query – Immutable – LeetCode

Problem Statement

You are given an integer array nums. You need to handle multiple queries of the form:

sumRange(left, right)

which returns the sum of elements between indices left and right (both inclusive).

To optimize repeated queries, implement a class NumArray with:

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

• int sumRange(int left, int right)
  Returns the sum of the elements between left and right inclusive.

Examples

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); // returns -2 + 0 + 3 = 1
numArray.sumRange(2, 5); // returns 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // returns sum of entire array = -3

Constraints

• 1 <= nums.length <= 10⁴

• -10⁵ <= nums[i] <= 10⁵

• 0 <= left <= right < nums.length

• Up to 10⁴ queries for sumRange

Intuition

Calling sumRange(left, right) naively for every query would result in O(n) time per query. But with prefix sums, we can preprocess the input array so that each query can be answered in O(1) time.

This is a classic case of Prefix Sum Optimization, where we compute the cumulative sum of elements up to each index, allowing for fast range sum queries.

Approach

1. Preprocess the nums array into a prefix sum array during construction:

   • nums[i] = nums[i - 1] + nums[i] for all i >= 1

2. To calculate the sum from index left to right:

   • If left == 0: return nums[right]

   • Else: return nums[right] - nums[left - 1]

Java Code

class NumArray {
    private int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
        for (int i = 1; i < nums.length; i++) {
            nums[i] += nums[i - 1]; // build prefix sum
        }
    }

    public int sumRange(int left, int right) {
        if (left == 0) return nums[right];
        return nums[right] - nums[left - 1];
    }
}

Time and Space Complexity

Optionally, we could store a separate prefix array to avoid modifying the original input. In that case:

• Space Complexity: O(n)

Dry Run

Input:

nums = [-2, 0, 3, -5, 2, -1]
NumArray obj = new NumArray(nums);

Prefix Sum Computed:

[-2, -2+0 = -2, -2+3 = 1, 1+(-5) = -4, -4+2 = -2, -2+(-1) = -3]
Prefix array: [-2, -2, 1, -4, -2, -3]

Queries:

• sumRange(0, 2) → 1

• sumRange(2, 5) → -1

• sumRange(0, 5) → -3

Conclusion

This is a textbook use case for the prefix sum pattern, which allows for constant-time range sum queries after an initial O(n) preprocessing.

You should think of this pattern whenever you're dealing with:

• Static arrays with repeated sum range queries

• Use cases like:

  • Subarray sum

  • Average over subarrays

  • Difference arrays (for reverse updates)