#126

Range Sum Query - Immutable

easy

arrayprefix-sumdesign

Given an integer array nums that is never modified, answer a batch of range-sum queries. Each query is a pair [i, j] (0-based, with i <= j) asking for the sum of the elements from index i to index j inclusive of both ends.

Return an array whose k-th entry is the answer to the k-th query. Because the array is immutable, the expectation is that you precompute once and then answer every query in constant time.

Example

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

Output: [1,-1,-3]

nums[0..2] = -2+0+3 = 1; nums[2..5] = 3-5+2-1 = -1; nums[0..5] = -3.

Constraints

0 <= nums.length <= 10^4
-10^5 <= nums[i] <= 10^5
0 <= queries.length <= 10^4
0 <= i <= j < nums.length for every query [i, j]

Intuition

The most direct approach answers each query on its own: walk from index i to index j, adding up the elements, and report the total. Correct, but every query re-walks its whole range.

function rangeSum(nums, queries) {
  // For every query, re-add the elements between its two endpoints.
  return queries.map(([i, j]) => {
    let total = 0;
    for (let k = i; k <= j; k++) {
      total += nums[k]; // inclusive of both i and j
    }
    return total;
  });
}

Brute force — sum each query's range from scratch: O(n) per query, O(n·q) overall.

With q queries this is O(n·q) — and since the array never changes, we keep re-summing the same overlapping stretches. Can we do better?

The key observation: a range sum is a difference of two running totals. If prefix[k] holds the sum of the first k elements (with prefix[0] = 0), then the inclusive range [i, j] is prefix[j + 1] - prefix[i] — the total through j, minus everything strictly before i. That's the core Prefix sums idea.

So pay O(n) once to build the prefix array, then answer each query in O(1). The leading zero and the +1 offset are what keep the subtraction boundary-safe — prefix[j + 1] includes nums[j], and prefix[i] excludes nums[i].

Walking the build then a query through:

nums = [2, 4, 6, 8] → prefix = [0, 2, 6, 12, 20]; query [1, 2]

k↓

prefix[1] = prefix[0] + 2 = 2

Start the build. prefix[0] = 0 is the empty prefix; fold in nums[0] = 2.

k↓

prefix[2] = 2 + 4 = 6

Each step carries the running total forward by one element.

k↓

prefix[4] = 12 + 8 = 20

Build finished: prefix = [0, 2, 6, 12, 20]. One O(n) pass, done once.

i↓

j↓

prefix[3] − prefix[1] = 12 − 2 = 10

Query [1, 2]: total through index 2 (12) minus everything before index 1 (2). Answer 10 = 4 + 6.

i↓

j↓

prefix[4] − prefix[0] = 20 − 0 = 20

Any later query is the same O(1) subtraction — here the full range sums to 20.

Optimization

Prefix sums (precompute once)

Build a prefix-sum array prefix of length n + 1 where prefix[k] holds the sum of the first k elements (so prefix[0] = 0). The sum of any inclusive range [i, j] is then prefix[j + 1] - prefix[i]: the running total up to and including j, minus everything strictly before i.

Building the prefix array is one O(n) pass; after that each query is O(1), so a batch of q queries costs O(n + q) — far better than re-summing each range, which would be O(n·q).

function rangeSum(nums, queries) {
  // prefix[k] = sum of nums[0..k-1], so prefix[0] = 0 and the array has n + 1 slots.
  const prefix = new Array(nums.length + 1).fill(0);
  for (let k = 0; k < nums.length; k++) {
    prefix[k + 1] = prefix[k] + nums[k];
  }
  // Each inclusive range [i, j] is the running total through j minus everything before i.
  return queries.map(([i, j]) => prefix[j + 1] - prefix[i]);
}

Complexity analysis

Time complexity: O(n + q). Here's why:

Building the prefix array is one pass over nums — O(n).
After that, each of the q queries is a single subtraction prefix[j+1] - prefix[i] — O(1) apiece, O(q) in total.

So the whole batch is O(n) + O(q) = O(n + q), versus the brute force's O(n·q) of re-summing each range. The precompute pays for itself as soon as there's more than one query.

Space complexity: O(n). Here's why:

The prefix array holds n + 1 running totals — O(n).
The answer array holds one number per query — O(q), the unavoidable output.

Not counting the output, the extra space is the prefix array, O(n).

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
nums = [], queries = []	[]	Empty array and no queries — nothing to build, nothing to answer.
nums = [42]queries = 00	[42]	Single element; the only valid range returns it.
nums = [3,1,4,1,5]queries = 22	[4]	Single-element range i === j returns just nums[i].
nums = [-5,-5,-5]queries = 02	[-15]	All-negative array — prefix subtraction handles signs.
nums = [2,-1,3,-2]queries = 03 12	[2,2]	Mixed signs; overlapping ranges off one prefix array.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor