AlgoMaster Logo

Range Sum Query - Immutable

easyFrequency4 min readUpdated June 23, 2026

Understanding the Problem

We need to build a data structure that preprocesses an integer array so we can answer range sum queries efficiently. Each query gives us two indices, left and right, and asks for the sum of all elements between those positions (inclusive).

The array is immutable: it never changes after construction. That means we can precompute data once during initialization and reuse it across all queries. The design question is what to precompute so each query runs as fast as possible.

Key Constraints:

  • nums.length <= 10^4 and at most 10^4 calls to sumRange → If each query scans the range in O(n), total work reaches O(n * q) = O(10^8). That is enough to matter, so O(1) per query is the target.
  • nums[i] can be negative → Sums are not monotonic, so we cannot prune ranges based on partial sums. Prefix sums still work because subtraction handles negatives correctly.
  • -10^5 <= nums[i] <= 10^5 with up to 10^4 elements → The largest possible total sum is about 10^9, which fits in a signed 32-bit integer. No overflow handling is needed.

Approach 1: Brute Force

Intuition

Do exactly what the problem says: for each sumRange call, loop from left to right and add up the elements. No preprocessing is needed.

This holds up for a small number of queries, but it repeats work. A query for sumRange(0, 5) followed by sumRange(0, 3) re-adds elements that were already summed in the first call. Every query starts over from the beginning of its range.

Algorithm

  1. Store the input array as-is during construction.
  2. For each sumRange(left, right) call, initialize a running sum to 0.
  3. Loop from index left to right, adding each element to the running sum.
  4. Return the running sum.

Example Walkthrough

1sumRange(0, 2): Start with sum = 0
0
left
-2
1
0
2
right
3
3
-5
4
2
5
-1
1/4

Code

Every query still loops through its range. Since the array never changes, the next approach precomputes cumulative sums once and answers each query with a single subtraction in O(1).

Approach 2: Prefix Sum

Intuition

If we know the sum of elements from index 0 up to any index, we can compute the sum of any subarray by subtracting two of those running totals.

Define prefix[i] as the sum of all elements from index 0 to index i - 1. Then:

  • sum(left, right) = prefix[right + 1] - prefix[left]

prefix[right + 1] is the sum of elements from 0 to right. We don't want elements 0 through left - 1, so we subtract prefix[left], which is exactly that unwanted portion. What remains is the sum from left to right.

We build this prefix array once during construction, and every query becomes one subtraction.

Algorithm

  1. Create a prefix array of size n + 1, where n is the length of nums.
  2. Set prefix[0] = 0 (sum of zero elements).
  3. For each index i from 0 to n - 1, set prefix[i + 1] = prefix[i] + nums[i].
  4. For each sumRange(left, right) call, return prefix[right + 1] - prefix[left].

Example Walkthrough

1Build prefix: prefix[0] = 0
0
0
0
1/10

Code