212. Range Sum Query - Immutable

Precompute a prefix-sum array once in the constructor. Any range sum is then the difference of two prefix values, answered in O(1) — perfect since the array never changes.

Precompute once, answer instantly

The array is immutable, so pay a one-time O(n) cost in the constructor and make every query O(1).

Build prefix where prefix[i] = sum of the first i elements (prefix[0] = 0):

prefix[0] = 0
prefix[i+1] = prefix[i] + nums[i]

Then the sum of nums[left..right] is:

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

Worked example

nums = [-2, 0, 3, -5, 2, -1] → prefix = [0, -2, -2, 1, -4, -2, -3].

• sumRange(0, 2) = prefix[3] - prefix[0] = 1 - 0 = 1.
• sumRange(2, 5) = prefix[6] - prefix[2] = -3 - (-2) = -1.
• sumRange(0, 5) = prefix[6] - prefix[0] = -3.

Complexity

• Time: O(n) to build, O(1) per query.
• Space: O(n) for the prefix array.

import java.util.*;

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];
    }
}