Prefix Sums

Imagine you are asked the same kind of question over and over: "what is the sum of the array between index 1 and 3? Between 0 and 4? Between 2 and 3?" Adding up the slice each time is slow. A prefix sum does the adding once, up front, so every later range query is a single subtraction.

Intuition

Think of a road trip with mile markers. At each town you write down the total distance from home so far. Later, to find the distance between town 1 and town 3, you do not re-drive the road — you just subtract the two mile markers: marker at town 3 minus marker at town 1. The prefix array is exactly that list of "distance from the start" totals, and a range sum is the gap between two markers.

Walk through it

The animation on the right shows two rows. The top row is nums = [3, 1, 4, 1, 5]. The bottom row is the prefix array, which is one cell longer and starts with prefix[0] = 0 (the sum of nothing).

First we build the prefix row left to right. The pointer i walks the input, and each new prefix cell fills in as prefix[i + 1] = prefix[i] + nums[i] — you can see the running total carry forward: 0, then 3, then 4, then 8, then 9, then 14. Once it is built, we ask a query: the sum of nums[1..3]. The pointers l and r+1 land on prefix[1] and prefix[4], and the answer is simply prefix[4] - prefix[1] = 8 - 3 = 5. That subtraction cancels everything before index l and leaves exactly the slice we wanted.

The code, line by line

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

• prefix has length n + 1, and prefix[0] = 0 — the sum of zero elements. That extra leading zero is what lets the query formula stay clean (no special case for l = 0).
• Line 4 is the build step: each prefix cell is the previous one plus the current input value. This is one pass, so building costs O(n).
• Line 8 is the query: prefix[r + 1] - prefix[l]. We use r + 1 because prefix[k] is the sum up to but not including index k, so prefix[r + 1] includes element r.
• Subtracting prefix[l] removes the sum of everything before l, leaving exactly nums[l] + ... + nums[r].

Complexity

The win shows up when you have many queries. Re-summing each slice is O(n) per query, so q queries cost O(n * q). Prefix sum pays O(n) once, then O(1) per query — total O(n + q). The cost is O(n) extra space for the prefix array.

When to use / pitfalls

For the flip side — fast range updates instead of range queries — a difference array is the mirror image. To add a value v to every element in l..r, you do diff[l] += v and diff[r + 1] -= v in O(1), then take a prefix sum of diff at the end to recover the final array. Prefix sum answers ranges; difference array updates them.

Practice