Prefix Sum Queries — Instant Range Sums ⚡ 15 XP Easy

Ctrl+Enter Run Ctrl+S Save

You just learned running sums. Now let's unlock their superpower: answering range sum queries in O(1) time. Yes, constant time. No matter how big the array. 🤯

Imagine a huge spreadsheet with 1 million rows of sales data. Your boss asks: "What's the total sales from row 500 to row 800?" Then five minutes later: "Now rows 100 to 950?" Then again. And again. If you add up numbers each time, that's painful. But if you have a running total column... you just subtract two numbers. Boom. Instant answer. 📊

That running total column? That's a prefix sum array.

Step 1: Build it. Given nums = [2, 4, 3, 3, 5]:

# prefix[i] = sum of nums[0] through nums[i]
# prefix = [2, 6, 9, 12, 17]
#            ^  ^  ^   ^   ^
#            2  2+4 +3  +3  +5

Step 2: Use it. Want the sum from index i to j?

If i == 0: the answer is just prefix[j] (it already holds the sum from the start!)
If i > 0: the answer is prefix[j] - prefix[i - 1] (total up to j, minus the part before i)

Let's trace through with prefix = [2, 6, 9, 12, 17]:

sum(1..3) = prefix[3] - prefix[0] = 12 - 2 = 10 ✓ (that's 4+3+3)
sum(0..4) = prefix[4] = 17 ✓ (entire array)
sum(2..2) = prefix[2] - prefix[1] = 9 - 6 = 3 ✓ (just the element at index 2)

Why is this so powerful? Build the prefix array once in O(n), then answer unlimited range queries in O(1) each. Without it, every query costs O(n). With 1000 queries on a million-element array, that's the difference between 1 million operations and 1 billion. 💡

Prefix vs. Suffix: A prefix array builds from left to right. A suffix array builds from right to left. In the next exercise (Product Except Self), you'll use both — a prefix product and a suffix product. This exercise lays that foundation! 🧱

This concept appears everywhere in competitive programming and interviews. Master it here, and a whole family of problems opens up. Let's build it! 🔨

📋 Instructions

Write two functions: 1. `build_prefix_sum(nums)` — takes a list of integers and returns the prefix sum array, where `prefix[i]` is the sum of all elements from index `0` to `i`. 2. `range_sum(prefix, i, j)` — takes the prefix sum array and two indices, returns the sum of the **original** array from index `i` to `j` (inclusive) in O(1) time. Print the results to match the expected output exactly.

For build_prefix_sum: start with prefix = [nums[0]]. Then for each index from 1 onward, append prefix[-1] + nums[i]. For range_sum: if i is 0, just return prefix[j]. Otherwise return prefix[j] - prefix[i-1]. That subtraction trick is the whole magic! ✨

⚠️ Try solving it yourself first — you'll learn more!

def build_prefix_sum(nums):
    prefix = [nums[0]]
    for i in range(1, len(nums)):
        prefix.append(prefix[-1] + nums[i])
    return prefix

def range_sum(prefix, i, j):
    if i == 0:
        return prefix[j]
    return prefix[j] - prefix[i - 1]

nums = [2, 4, 3, 3, 5]
prefix = build_prefix_sum(nums)
print(f"Prefix: {prefix}")
print(f"Sum [1..3]: {range_sum(prefix, 1, 3)}")
print(f"Sum [0..4]: {range_sum(prefix, 0, 4)}")
print(f"Sum [2..2]: {range_sum(prefix, 2, 2)}")

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›