How do you approach Range Sum Query - Immutable?

Build a prefix array where prefix[i] is the sum of the first i elements. Give it length n + 1 so prefix[0] = 0.

What is the time complexity of Range Sum Query - Immutable?

Time complexity: O(n) preprocessing, O(1) per query.. Space complexity: O(n).

What are common mistakes on Range Sum Query - Immutable?

Not seeding the map with a zero-sum prefix, which loses every subarray starting at index 0. Counting the current prefix before checking for its complement, so a zero-sum range matches itself. Mixing inclusive and exclusive bounds between building the array and querying it - a consistent, invisible off-by-one.

Sitelet https://gitgood.dev/coding/range-sum-query-immutable

gitGood.dev

← Back to problems

Range Sum Query - Immutable

EasyAlgorithms

Description

Given an integer array nums that never changes, answer many range sum queries over it.

Each query is a pair [left, right] and asks for the sum of nums[left] ... nums[right], inclusive on both ends.

Implement rangeSumQuery(nums, queries) returning one sum per query, in order. There may be far more queries than elements, so a solution that walks the range for every query is too slow - precompute once and answer each query in constant time.

Example 1

Input: nums = [-2,0,3,-5,2,-1], queries = [[0,2],[2,5],[0,5]]

Output: [1,-1,-3]

Example 2

Input: nums = [1,2,3], queries = [[0,0],[1,2],[0,2]]

Output: [1,5,6]

Example 3

Input: nums = [10,20], queries = [[1,1],[0,1]]

Output: [20,30]

Constraints

- 1 <= nums.length <= 10^4 - -10^5 <= nums[i] <= 10^5 - 0 <= left <= right < nums.length - Up to 10^4 queries. Each query must be answered in O(1) after preprocessing.

Range Sum Query - Immutable: approach, complexity and pitfalls

An easy prefix sum problem, graded against 6 test cases (3 of them hidden).

The pattern: Prefix Sum

Precomputed cumulative totals so any range query becomes one subtraction.

Reach for it when you see: Repeated range-sum queries, or counting subarrays that sum to a target.

If you are stuck

Show the 3-step hint ladder

Build a prefix array where prefix[i] is the sum of the first i elements. Give it length n + 1 so prefix[0] = 0.
With that padding, the sum of [left, right] is prefix[right + 1] - prefix[left] - no special case for left == 0.
If you build prefix with length n instead, you need an if-statement for left == 0. The extra slot exists to delete that branch.

The optimal approach

Show the approach: Precompute prefixes, then subtract

Build `prefix` of length `n + 1` where `prefix[i]` is the sum of the first `i` elements, so `prefix[0] = 0`. Then:

```

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

```

Preprocessing is O(n) once; every query is then two array reads and a subtraction.

The padded slot is the detail worth internalizing. Without it you would write `prefix[right] - (left > 0 ? prefix[left - 1] : 0)` - correct, but the branch is exactly the kind of edge case that gets fumbled under interview pressure. Padding makes the empty prefix a real value instead of a special case.

Time: O(n) preprocessing, O(1) per query.
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Prefix Sum mistakes

These apply to the pattern as a whole, not just this problem.

Not seeding the map with a zero-sum prefix, which loses every subarray starting at index 0.
Counting the current prefix before checking for its complement, so a zero-sum range matches itself.
Mixing inclusive and exclusive bounds between building the array and querying it - a consistent, invisible off-by-one.