EasyArrayDesignPrefix Sum

Range Sum Query - Immutable

1 approach, code in every language

Design a data structure that, given a fixed integer array nums, can answer many range-sum queries efficiently.

Implement a class NumArray that is constructed from nums and supports the operation sumRange(left, right), which returns the sum of the elements between indices left and right inclusive, that is nums[left] + nums[left + 1] + ... + nums[right]. The array never changes after construction, so queries should not require re-scanning the elements each time.

Example 1

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

Output: 1, -1, -3

sumRange(0,2) = -2 + 0 + 3 = 1, sumRange(2,5) = 3 - 5 + 2 - 1 = -1, sumRange(0,5) = -2 + 0 + 3 - 5 + 2 - 1 = -3.

Example 2

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

Output: 9, 1

sumRange(1,3) = 2 + 3 + 4 = 9 and sumRange(0,0) = 1.

Constraints

1 <= nums.length <= 10^4
-10^5 <= nums[i] <= 10^5
0 <= left <= right < nums.length
At most 10^4 calls will be made to sumRange.

Precomputed Prefix Sum Array

Build a prefix-sum array once in the constructor so every sumRange query is answered by a single subtraction in constant time.

Loading animation…

Intuition

Answering a range sum by adding up elements takes time proportional to the range length, which is wasteful when many queries hit the same immutable array. Instead, precompute prefix[i] = nums[0] + nums[1] + ... + nums[i - 1], where prefix[0] = 0. Then the sum of nums[left..right] equals prefix[right + 1] - prefix[left], because the shared prefix up to left cancels out. The one extra leading zero in the prefix array removes any special-casing when left is 0. Building the prefix array is a single linear pass, and afterward each query is a single subtraction.

Algorithm walkthrough

1In the constructor, allocate a prefix array of length n + 1 and set prefix[0] = 0.
2For each index i from 0 to n - 1, set prefix[i + 1] = prefix[i] + nums[i], accumulating the running total.
3Store the prefix array on the instance so it can be reused across queries.
4For sumRange(left, right), return prefix[right + 1] - prefix[left].
5The subtraction cancels the common prefix up to index left, leaving exactly the sum of nums[left..right].

Implementation

class NumArray:
    def __init__(self, nums: list[int]):
        self.prefix = [0] * (len(nums) + 1)
        for i, num in enumerate(nums):
            self.prefix[i + 1] = self.prefix[i] + num

    def sumRange(self, left: int, right: int) -> int:
        return self.prefix[right + 1] - self.prefix[left]

Time

O(n) construction, O(1) per query

Space

O(n)

The prefix array uses n + 1 slots; every sumRange call is a single subtraction.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free