DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Range Sum Query - Immutable

easyPrefix sum Must-do

Problem statement

Design a class NumArray that is built once from an integer array nums and then answers many queries of the form sumRange(left, right): the sum of nums[left] through nums[right], inclusive.

The array never changes after construction, and 0 <= left <= right < len(nums) for every query. Make the queries fast, since there may be many of them.

Examples

Example 1

Input: NumArray([3, -1, 4, 0, 2]) sumRange(0, 2) sumRange(1, 4)

Output: 6 5

Explanation: 3 + (-1) + 4 = 6, and (-1) + 4 + 0 + 2 = 5.

Example 2

Input: NumArray([10, 20]) sumRange(1, 1)

Output: 20

Explanation: A range of one element is just that element.

Hints

Approach

Precompute prefix sums. Let pre[i] be the sum of the first i elements, so pre[0] = 0 and pre[i + 1] = pre[i] + nums[i]. The sum of nums[left..right] is everything up to right minus everything before left:

sumRange(left, right) = pre[right + 1] - pre[left]

  1. In the constructor, build pre with n + 1 entries.
  2. Each query is one subtraction.

The leading 0 means left = 0 needs no special case.

ComplexityTime O(n) build, O(1) per querySpace O(n)
Python
class NumArray:
def __init__(self, nums: list[int]):
self.pre = [0] # pre[i] = sum of the first i elements
for x in nums:
self.pre.append(self.pre[-1] + x)
def sumRange(self, left: int, right: int) -> int:
return self.pre[right + 1] - self.pre[left]

Follow-up questions

  • Support update(index, value) as well as range sums.
  • Extend it to a 2D grid: return the sum of any rectangle in O(1).

Frequently asked questions

Then the prefix array would need rebuilding after every update, which is O(n). The usual answer is a Fenwick tree (binary indexed tree) or a segment tree, which give O(log n) for both updates and range queries.

With pre[0] = 0, the formula pre[right + 1] - pre[left] works for every range, including ones that start at index 0. Without it you need an if left == 0 branch.

Metrics backends store counters as running totals so that "how many requests between 10:00 and 10:15" is one subtraction of two samples. It is the same trade: pay once when writing, answer range questions in constant time.