Range Sum Query - Immutable

Range Sum Query - Immutable

What is this problem about?

The Range Sum Query - Immutable problem asks you to design a class supporting multiple range sum queries on an immutable array: given [l, r], return the sum of arr[l..r]. This easy design problem uses prefix sums for O(1) query time after O(n) preprocessing. The array, design, and prefix sum interview pattern is the foundational skill tested.

Why is this asked in interviews?

Apple, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this as the gateway prefix sum problem. It validates understanding of the prefix sum technique — the most important array optimization pattern. Every candidate should know this.

Algorithmic pattern used

Prefix sum array. Build prefix[i] = sum of arr[0..i-1]. Initialize prefix[0]=0. For query(l,r): return prefix[r+1] - prefix[l].

Example explanation

arr=[-2,0,3,-5,2,-1]. prefix=[0,-2,-2,1,-4,-2,-3]. Query(0,2): prefix[3]-prefix[0]=1-0=1 (-2+0+3=1 ✓). Query(2,5): prefix[6]-prefix[2]=-3-(-2)=-1 ✓.

Common mistakes candidates make

• Not building prefix array during initialization.
• Off-by-one: prefix[r+1] - prefix[l], not prefix[r] - prefix[l].
• Recomputing sum for each query (O(n) per query instead of O(1)).
• 0-indexed confusion when building prefix array.

Interview preparation tip

Range Sum Query - Immutable is the most fundamental prefix sum problem. Master the formula: sum(l,r) = prefix[r+1] - prefix[l]. This pattern is the foundation for: "subarray sum equals k," "maximum subarray sum," "count subarrays with condition," "2D submatrix sum." Build prefix arrays fluently as a first step for any array range query problem.