Range Sum Query Immutable: Prefix Sums Explained

LeetCode #303, Range Sum Query - Immutable, is an easy-level problem that introduces one of the most useful tricks in all of array programming: the prefix sum. You are given an integer array that never changes, and you need to answer potentially thousands of "what is the sum from index left to index right?" queries as fast as possible. The naive approach recalculates the sum every time. The prefix sum approach does the math once upfront and answers every query in constant time.

The problem

You are given an immutable integer array nums. You need to implement a class called NumArray that supports a method sumRange(left, right). This method returns the sum of all elements between indices left and right, inclusive. The key constraint is that sumRange will be called many times on the same array.

nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2)  # -2 + 0 + 3 = 1
sumRange(2, 5)  # 3 + (-5) + 2 + (-1) = -1
sumRange(0, 5)  # -2 + 0 + 3 + (-5) + 2 + (-1) = -3

Each call asks for the sum of a contiguous slice. You can see that the same array gets queried with different ranges, so any work you can do once and reuse across queries is a win.

The brute force

The simplest approach: every time sumRange is called, loop from left to right and add up the values. No preprocessing, no extra memory.

This works, but it is slow. Each query takes O(n) time in the worst case (when the range covers the entire array). If you have q queries, the total time is O(n * q). For large arrays with many queries, this adds up quickly.

The key insight: prefix sums

Build an array prefix where prefix[i] stores the sum of all elements from nums[0] through nums[i-1]. Set prefix[0] = 0 as the base case (the sum of zero elements). Then:

• prefix[1] = nums[0]
• prefix[2] = nums[0] + nums[1]
• prefix[k] = nums[0] + nums[1] + ... + nums[k-1]

To answer sumRange(left, right), you compute prefix[right + 1] - prefix[left]. The prefix[right + 1] value holds the sum of everything from index 0 through index right. Subtracting prefix[left] removes the elements before left. What remains is exactly the sum from left to right.

Step-by-step walkthrough

Let us walk through building the prefix array and then answering three queries on nums = [-2, 0, 3, -5, 2, -1].

Notice how every query is just one subtraction. No loops, no iteration over the range. The entire cost of summing has been shifted into the one-time preprocessing step.

The code

class NumArray:
    def __init__(self, nums):
        self.prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.prefix[i + 1] = self.prefix[i] + nums[i]

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

1. Constructor: Create a prefix array of size n + 1, initialized to zeros. Then fill it in a single pass: each prefix[i + 1] equals prefix[i] + nums[i].
2. sumRange: Return prefix[right + 1] - prefix[left]. The subtraction cancels out everything before left, leaving the sum of the range [left, right].
3. Why right + 1: Because prefix[k] stores the sum of the first k elements (indices 0 through k - 1). To include nums[right], you need prefix[right + 1].

Complexity analysis

Time: O(n) for the constructor (one pass to build the prefix array). O(1) per sumRange call (a single subtraction).

Space: O(n) for the prefix sum array.

Common mistakes

1. Off-by-one in prefix indexing. The most common bug is using prefix[right] - prefix[left] instead of prefix[right + 1] - prefix[left]. This misses nums[right] from the sum. Always remember: prefix[k] represents the sum of the first k elements, so to include element at index right, you need prefix[right + 1].

2. Forgetting the base case. If you skip setting prefix[0] = 0 and instead start building from prefix[0] = nums[0], your subtraction formula breaks for queries where left = 0. The zero at the front is what makes the formula uniform.

3. Modifying the input array. Some people try to overwrite nums in place to store prefix sums. While this saves space, it mutates the original data. The problem says "immutable," but your solution should also be clear about what it changes. Using a separate array avoids confusion.

4. Integer overflow in other languages. In Python, integers grow arbitrarily large, so this is not an issue. But in Java or C++, if the array contains large values and has many elements, the prefix sums can overflow a 32-bit integer. Use long in those languages.

The building blocks

Prefix sum array

def build_prefix(nums):
    prefix = [0] * (len(nums) + 1)
    for i in range(len(nums)):
        prefix[i + 1] = prefix[i] + nums[i]
    return prefix

This pattern appears whenever you need to answer range sum queries on a static array. It also shows up in problems that ask for subarray sums equal to a target (combine prefix sums with a hash map), in 2D matrix sum queries (extend to 2D prefix sums), and in problems involving cumulative frequency counts.

Edge cases

• Single element range. sumRange(i, i) should return nums[i]. With the prefix formula: prefix[i + 1] - prefix[i] = nums[i]. Works correctly.
• Full array range. sumRange(0, n - 1) returns prefix[n] - prefix[0], which is the total sum of the array.
• Array with one element. nums = [5] gives prefix = [0, 5]. The only valid query is sumRange(0, 0) = 5.
• All negative values. Prefix sums handle negative numbers without any special logic. The cumulative sum simply decreases at each step.
• All zeros. Every prefix value is 0, and every query returns 0. The formula still holds.

From understanding to recall

Range Sum Query - Immutable is the gateway problem for prefix sums. The technique itself is simple: build a cumulative sum array, then answer range queries with a subtraction. But the real value is in training your instincts. When you see "sum of a subarray" in a harder problem, you want prefix sums to be the first tool you reach for, not something you have to rediscover.

Solving this problem once teaches you the concept. Revisiting it through spaced repetition turns that concept into a reflex. The next time you face a subarray sum problem in an interview, you will not waste time reinventing the wheel. You will jump straight to the prefix array and spend your energy on whatever twist the harder problem adds on top.

Related posts

• Maximum Subarray - Uses similar prefix sum thinking with Kadane's algorithm
• Product of Array Except Self - Prefix and suffix products, the multiplicative version
• Minimum Size Subarray Sum - Sliding window over cumulative sums

Prefix sums are one of those patterns that punch well above their weight. Learn it here on an easy problem, and you will keep finding uses for it in mediums and hards. The investment in building this reflex now saves you real time later.