Range Sum Query - Immutable

Easy#303subarray sum

Build a class that gets an array of numbers once and then answers many queries: the sum of the numbers from index left to index right, both included. The array never changes. Our example: [4, -2, 3, 5, -1, 2] and three queries — sumRange(2, 4) = 7, sumRange(0, 3) = 10 and sumRange(1, 1) = -2.

303 Range Sum Query - ImmutableWalkthrough · 1×

Example: [4, -2, 3, 5, -1, 2], then sumRange(2, 4), sumRange(0, 3), sumRange(1, 1). Under the numbers are the prefix sums: prefix[j] stands before nums[j] and holds the sum of everything to its left.

numsprefix4-235-12
not filled in yetready prefix sumcurrentprefix[left], subtractedthe queried range

NumArray([4, -2, 3, 5, -1, 2]) is created: init runs once

01/20
restart · back · play · step
Speed
1class NumArray:
2 function init(nums):
3 prefix = array of len(nums) + 1 zeros
4 for i from 0 to len(nums) - 1:
5 prefix[i + 1] = prefix[i] + nums[i]
6 function sumRange(left, right):
7 return prefix[right + 1] - prefix[left]
state
prefix
–
i
–
left
–
right
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. prefix[j] is the sum of the first j numbers. The numbers from left to right are the first right + 1 numbers without the first left ones, so their sum is prefix[right + 1] − prefix[left].
  2. The extra slot prefix[0] = 0 is the sum of no numbers: a query from index 0 subtracts it and needs no special case.
  3. The array never changes, so the table built once stays right for every query, and each query is two lookups however long its range is.

Complexity

init: time O(n) and memory O(n) for n + 1 sums. Each sumRange: time O(1), two lookups and a subtraction.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.