Range Sum Query Immutable: Build a Prefix Array

• Range Sum Query Immutable – a class design problem solved with a prefix sum array.
• Constructor – builds the cumulative-sum array in O(n): prefix[i+1] = prefix[i] + nums[i].
• sumRange(i, j) – returns prefix[j+1] - prefix[i] in O(1).
• Amortization – O(n) once in the constructor so possibly millions of queries are each O(1).
• Immutability – the prefix array is private and final; no mutators exposed.

What is the Range Sum Query Immutable problem?

Design a class that, given an immutable integer array, preprocesses it so that multiple queries for the sum of elements between indices i and j (inclusive) can be answered efficiently. The array never changes after construction.

This tests whether you recognize that preprocessing in the constructor amortizes cost across many queries.

How does the prefix sum array work?

Build an array of length n + 1 with a leading zero. Each position prefix[k] stores the sum of the first k elements. The query sumRange(i, j) is prefix[j+1] - prefix[i].

nums:   [3, 5, 2, 8, 1]
prefix: [0, 3, 8, 10, 18, 19]

sumRange(1, 3) = prefix[4] - prefix[1] = 18 - 3 = 15
Verify: 5 + 2 + 8 = 15 ✓

How do you implement it? (with code)

package com.bank.analytics;

public class RangeSumQuery {

    private final long[] prefix;

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

    public long sumRange(int i, int j) {
        return prefix[j + 1] - prefix[i];
    }

    public static void main(String[] args) {
        int[] amounts = {300, 500, 200, 800, 100};
        RangeSumQuery rsq = new RangeSumQuery(amounts);

        System.out.println("Sum [1,3]: " + rsq.sumRange(1, 3));
        System.out.println("Sum [0,4]: " + rsq.sumRange(0, 4));
        System.out.println("Sum [2,2]: " + rsq.sumRange(2, 2));
    }
}

Sum [1,3]: 1500
Sum [0,4]: 1900
Sum [2,2]: 200

Why is the leading zero important?

The leading zero in prefix[0] = 0 lets you compute the sum starting from index 0 without a special case. sumRange(0, j) = prefix[j+1] - prefix[0] = prefix[j+1], which is just the sum of the first j+1 elements.

Where should you pay the cost?

The design decision is deliberate: pay O(n) once in the constructor so each query is O(1). If you summed on each query instead, the constructor would be trivial but every query would be O(n), which is the wrong trade-off for a query-heavy workload.

| Approach | Constructor | Per query |
|---|---|---|
| No preprocessing | O(1) | O(n) |
| Prefix sum | O(n) | O(1) |
| Fenwick tree (with updates) | O(n) | O(log n) |

What about immutability and encapsulation?

The prefix array is private final. The class exposes no mutator. This matches the problem's immutable contract and prevents accidental corruption. Building the prefix array in the constructor is itself a safe snapshot of the input.

What about overflow?

For large arrays with large values, cumulative sums can exceed int range. Using long for the prefix array avoids overflow. For financial totals at the National Bank of India, long is usually sufficient, but BigDecimal would be used if absolute precision is required.

What are the edge cases?

• Single element – prefix has two entries; sumRange(0, 0) = prefix[1] - prefix[0].
• Entire array – sumRange(0, n-1) = prefix[n].
• i == j – returns the single element at that index.
• Empty array – prefix has only [0]; no valid query exists.

What if the array could be updated?

If updates are needed, the static prefix array would require O(n) rebuild per update. Switch to a Fenwick tree (Binary Indexed Tree) for O(log n) updates and O(log n) queries, or a segment tree for range updates.

What are common interview follow-up questions?

• What if the array changes? – Use a Fenwick tree or segment tree.
• What about 2D range sums? – Use a 2D prefix sum matrix.
• Can you handle negative values? – Yes, prefix sums work with negatives.
• What about modular arithmetic? – Apply mod after each addition to prevent overflow in contest problems.