Problem statement

Given an integer array nums, answer many queries of the form: what is the sum of the elements of nums between indices left and right, inclusive? The array never changes.

Write the class NumArray:

• NumArray(int[] nums) initialises the object with the array nums.
• int sumRange(int left, int right) returns nums[left] + nums[left + 1] + … + nums[right].

The judge calls the constructor and then sumRange with the arguments listed in the second input line; the expected output holds each call's result, null for the constructor.

Example 1

Input: ["NumArray","sumRange","sumRange","sumRange"]
[[[-3,5,0,2,-6,4]],[0,2],[2,5],[0,5]]
Output: [null,2,0,2]
Explanation: -3 + 5 + 0 = 2; 0 + 2 + (-6) + 4 = 0; the whole array sums to 2.

Example 2

Input: ["NumArray","sumRange","sumRange"]
[[[7]],[0,0],[0,0]]
Output: [null,7,7]
Explanation: A one-element array answers every query with that element.

Constraints

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

Hints for Range Sum Query - Immutable

1. Hint 1

   Summing the range on every query costs O(n) per call — up to 10^8 work. Precompute something once instead.

2. Hint 2

   If you knew the sum of every prefix nums[0..i-1], how would you get the sum of nums[left..right]?

3. Hint 3

   Store prefix[i] = nums[0] + … + nums[i-1] (with prefix[0] = 0). Then sumRange(left, right) = prefix[right + 1] - prefix[left].

How to solve Range Sum Query - Immutable

Precompute prefix sums once in the constructor; every range sum is then the difference of two prefix sums, answered in O(1).

Approach

1. In the constructor build prefix of length n + 1: prefix[0] = 0 and prefix[i + 1] = prefix[i] + nums[i].
2. sumRange(left, right) returns prefix[right + 1] - prefix[left].

Why it works

prefix[right + 1] is the sum of nums[0..right] and prefix[left] the sum of nums[0..left-1]; their difference leaves exactly nums[left..right]. The extra leading zero makes left = 0 need no special case.

Complexity

• Time — O(n) to build, O(1) per query
• Space — O(n)

Pitfalls

• Off-by-one: with the leading zero the right end is prefix[right + 1], not prefix[right].
• The prefix sums stay within ±10^9 under the constraints, so 32-bit integers are enough.

Reference solution

Python

from typing import List

class NumArray:

    def __init__(self, nums: List[int]):
        self.prefix = [0]
        for x in nums:
            self.prefix.append(self.prefix[-1] + x)

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

Java

class NumArray {
    private int[] prefix;

    public NumArray(int[] nums) {
        prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
    }

    public int sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

C++

class NumArray {
    vector<int> prefix;
public:
    NumArray(vector<int>& nums) : prefix(nums.size() + 1, 0) {
        for (size_t i = 0; i < nums.size(); i++) prefix[i + 1] = prefix[i] + nums[i];
    }

    int sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
};

JavaScript

var NumArray = function(nums) {
    this.prefix = [0];
    for (var i = 0; i < nums.length; i++) this.prefix.push(this.prefix[i] + nums[i]);
};

NumArray.prototype.sumRange = function(left, right) {
    return this.prefix[right + 1] - this.prefix[left];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Convert Sorted Array to Binary Search Tree Easy