Range Sum Query - Immutable

Step 1: Adding up each range is wasteful

Summing nums[left..right] on every call costs O(n) per query, and the same additions are repeated across queries.

Step 2: Store running totals once

In the constructor, build prefix where prefix[i] is the sum of the first i elements. It has one extra slot: prefix[0] = 0, the sum of nothing.

Step 3: A range is a difference of two totals

The sum up to right includes everything before left, which we do not want. Subtract it:

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

The extra slot at the front means left = 0 needs no special case.

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

All the work happens once in the constructor; each query is a single subtraction.

public class RangeSumQueryImmutable {

    private final int[] prefix;               // prefix[i] = nums[0] + ... + nums[i-1]

    public RangeSumQueryImmutable(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];   // everything up to right, minus before left
    }

    public static void main(String[] args) {
        RangeSumQueryImmutable q = new RangeSumQueryImmutable(new int[] {-2, 0, 3, -5, 2, -1});
        System.out.println(q.sumRange(0, 2));   // 1
        System.out.println(q.sumRange(2, 5));   // -1
        System.out.println(q.sumRange(0, 5));   // -3
    }
}

The original implementation, RangeSumQueryImmutable.java, is on GitHub.

• Constructor: O(n) time, O(n) space.
• sumRange: O(1).

For a 2D grid, see Range Sum Query 2D - Immutable. If the array can change between queries, prefix sums no longer work well and a Fenwick tree or segment tree is used instead.