Prefix Sums — Use prefix sums to answer range-sum style queries (intro) - Python

SECTION 1

Historical Context & Motivation

Imagine you have a list of daily temperatures for an entire year, and someone asks you to find the average temperature for any given week. Without any clever trick, you would need to add up seven numbers every time someone asks. Now imagine thousands of such questions — your program would grind to a halt. The prefix sum technique solves exactly this kind of problem by doing a small amount of work upfront so that every future query becomes nearly instant.

The idea of precomputing cumulative totals is not new. It draws from a long history of mathematical and computational thinking about how to avoid redundant work. Here are some key milestones in the evolution of this pattern.

1800s • Cumulative Frequency Tables

Statisticians began using cumulative frequency tables to quickly look up running totals in census and survey data, avoiding repetitive addition.

1960s • Early Algorithm Design

Computer scientists formalized the concept of precomputation — doing work ahead of time to speed up repeated queries. This became a core strategy in algorithm design.

1980s • Competitive Programming Emerges

Programming contests like the ACM ICPC popularized prefix sums as a go-to technique for range-query problems, making it a standard tool in every competitive programmer's toolkit.

2000s+ • Industry & Data Science

Prefix sums power real-world applications in databases, image processing (integral images), and data analytics where fast aggregation over ranges is essential.

The central question that prefix sums address is: How can we answer many range-sum queries over the same array without re-adding elements each time? This lesson introduces the technique from scratch, shows how to build and use a prefix sum array in Python, and prepares you to recognize when this pattern applies.

SECTION 2

Core Principles & Definitions

At its core, the prefix sum pattern rests on a simple observation: if you already know the sum of every element from the start of an array up to each position, you can find the sum of any sub-range by subtracting two of these precomputed values. Let's define the key ideas that make this work.

The Original Array

A list of numbers nums with n elements, indexed from 0 to n − 1. This is your raw input data.

Prefix Sum Array

A new array prefix where prefix[i] stores the sum of all elements from index 0 through index i − 1 in the original array. By convention, prefix[0] = 0.

Range-Sum Query

A question of the form: "What is the sum of elements from index l to index r (inclusive)?" Prefix sums answer this in O(1) time.

O(1) vs O(n)

Without prefix sums, each query takes O(n) time (looping through elements). With prefix sums, after O(n) preprocessing, every query is O(1) — just one subtraction.

✦

KEY TAKEAWAY

Think of a prefix sum like a car's odometer. Your odometer records the total distance traveled since the car was new. If you want to know how far you drove on a road trip, you don't need to re-drive the route — you just subtract the reading at the start from the reading at the end. The prefix sum array is your odometer for an array of numbers.

SECTION 3

Visual Explanation

The diagram below shows how a prefix sum array is constructed from an original array, and how a range-sum query is answered using a single subtraction. Study the relationship between the original values and the cumulative totals.

The top row shows the original array nums. The bottom row shows the prefix sum array where each entry is the cumulative total of all preceding elements. To answer the query "sum from index 1 to index 3," we compute prefix[4] − prefix[1] = 11 − 2 = 9.

Notice that the prefix sum array has one more element than the original array. This is intentional. The extra leading zero at prefix[0] makes the subtraction formula work cleanly even when the query starts at index 0. Without it, you would need a special case for queries that begin at the first element.

SECTION 4

Mathematical Framework

Let's formalize the two operations that define the prefix sum pattern. The first is building the prefix sum array, and the second is querying it to find the sum of any sub-range.

BUILDING THE PREFIX ARRAY

prefix[0] = 0, prefix[i] = prefix[i − 1] + nums[i − 1] for i = 1, 2, …, n

Here nums is the original array of length n, and prefix is the new array of length n + 1. Each entry accumulates the running total by adding the next element from nums.

RANGE-SUM QUERY

sum(l, r) = prefix[r + 1] − prefix[l]

To find the sum of elements from index l to index r (inclusive), subtract the prefix value at l from the prefix value at r + 1. This works because prefix[r + 1] contains the sum of elements 0 through r, and prefix[l] contains the sum of elements 0 through l − 1.

TIME COMPLEXITY

Build: O(n) | Each Query: O(1) | Total for q queries: O(n + q)

Building the prefix array requires one pass through nums. After that, each query is a single subtraction. Compare this to the naive approach of O(n × q), which re-sums elements for every query.

The key insight is that the sum from index l to r equals the total sum up to r minus the total sum before l. This is analogous to how you calculate the distance of a road trip: subtract the odometer reading at departure from the reading at arrival.

SECTION 5

Building Prefix Sums in Python

Now let's translate the math into actual Python code. Below is a detailed diagram that traces through the construction step by step, showing exactly how each value in the prefix array is calculated.

Each step appends the previous prefix value plus the next element from nums. After all 5 steps, the prefix array has 6 entries — one more than the original.

Python Implementation

Here is the complete Python code for building a prefix sum array and answering range-sum queries. The function build_prefix(nums) creates the prefix array, and range_sum(prefix, l, r) answers a query.

💡

Python Code

def build_prefix(nums):
    prefix = [0]
    for num in nums:
        prefix.append(prefix[-1] + num)
    return prefix

def range_sum(prefix, l, r):
    return prefix[r + 1] - prefix[l]

# Example
nums = [2, 5, 1, 3, 4]
prefix = build_prefix(nums)
print(range_sum(prefix, 1, 3))  # Output: 9

The build_prefix function uses prefix[-1] to access the last element, which is always the current running total. Each new value is simply the old total plus the next number from nums. This runs in O(n) time and O(n) space.

SECTION 6

Worked Example

Let's walk through a complete problem. Suppose a teacher records daily homework scores for a student over a week: scores = [8, 6, 7, 5, 3, 9, 4]. The teacher wants to quickly find the total score for any range of consecutive days.

Finding Range Sums of Homework Scores

1
Step 1 — Identify the Input

The original array is scores = [8, 6, 7, 5, 3, 9, 4] with 7 elements (indices 0 through 6). We want to answer range-sum queries such as "total score from day 2 to day 5."

n = 7, queries involve indices l and r (inclusive)
2
Step 2 — Build the Prefix Sum Array

Start with prefix = [0]. Then accumulate: 0 + 8 = 8, 8 + 6 = 14, 14 + 7 = 21, 21 + 5 = 26, 26 + 3 = 29, 29 + 9 = 38, 38 + 4 = 42.

prefix = [0, 8, 14, 21, 26, 29, 38, 42]
3
Step 3 — Query: Total from Day 2 to Day 5

We want sum(2, 5). Apply the formula: prefix[5 + 1] − prefix[2] = prefix[6] − prefix[2]. That gives us 38 − 14 = 24.

sum(2, 5) = 24
4
Step 4 — Verify by Manual Addition

Check: scores[2] + scores[3] + scores[4] + scores[5] = 7 + 5 + 3 + 9 = 24. ✓ The prefix sum approach gives the same result instantly.

Manual sum = 24 ✓ — matches the prefix sum query
5
Step 5 — Another Query: Total from Day 0 to Day 6

For the entire week: prefix[7] − prefix[0] = 42 − 0 = 42. This is simply the last element of the prefix array, which is the total of all scores.

sum(0, 6) = 42

SECTION 7

Strengths & Limitations

Prefix sums are a powerful tool, but they aren't the right solution for every problem. Understanding when to use them — and when not to — is just as important as knowing how they work.

Feature	Strength	Limitation
Query Speed	Each range-sum query is O(1) — one subtraction regardless of range size	Only works for sum queries (not min, max, or other aggregations without modification)
Setup Cost	Building the prefix array is O(n) — just one linear pass through the data	Requires O(n) extra memory to store the prefix array
Data Updates	Perfect when the data is fixed (read-only) and you have many queries	If the original array changes, the entire prefix array must be rebuilt (O(n) per update)
Implementation	Very simple code — easy to implement correctly under time pressure	Off-by-one errors in indexing are a common source of bugs

Prefix Sum: Strengths vs. Limitations

🎯

WHEN TO USE PREFIX SUMS

Reach for prefix sums when your problem involves a static array (one that doesn't change) and multiple range-sum queries. Think of it like building an index at the back of a textbook — you spend time creating it once, but it saves you huge amounts of time whenever you need to look something up.

SECTION 8

Connection to Advanced Techniques

Prefix sums are the entry point to a family of powerful algorithms. Once you master the basic 1D prefix sum, you'll find that the same idea extends in several exciting directions.

Basic Prefix Sum	Advanced Technique
Works on a 1D array	2D Prefix Sums extend the idea to matrices, enabling O(1) sub-rectangle sum queries (used in image processing)
Static array — no updates	Fenwick Tree (BIT) supports both range-sum queries and element updates in O(log n) time
Only answers sum queries	Segment Tree handles sum, min, max, GCD, and other associative operations with updates in O(log n)
Uses subtraction trick	Difference Array is the inverse of prefix sums and is used to apply range updates efficiently

From Prefix Sums to Advanced Data Structures

For now, focus on mastering the basic 1D prefix sum. As you encounter problems that require updates or non-sum operations, you'll naturally be guided toward these more advanced tools. The intuition you build here — precompute to avoid redundant work — is the common thread that runs through all of them.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Why does the prefix sum array have one more element than the original array? What would go wrong if we didn't include the leading zero?

Show answer

The leading zero at prefix[0] ensures that the formula prefix[r + 1] − prefix[l] works correctly even when l = 0. Without it, a query starting at index 0 would require a special case: you would need to check whether l == 0 and return prefix[r] directly instead of subtracting. The extra element eliminates this special case, making the code simpler and less error-prone.

Question 2: BASIC CALCULATION

Given nums = [4, 1, 3, 2, 6], build the prefix sum array and then compute sum(1, 4).

Show answer

Build the prefix array step by step: prefix = [0, 4, 5, 8, 10, 16]. To compute sum(1, 4), apply the formula: prefix[4 + 1] − prefix[1] = prefix[5] − prefix[1] = 16 − 4 = 12. Verify: 1 + 3 + 2 + 6 = 12. ✓ The prefix sum technique gives the correct result using a single subtraction.

Question 3: INTERMEDIATE

Write a Python function that takes an array of integers and a list of queries (each query is a pair [l, r]) and returns a list of results. Use prefix sums to make it efficient. What is the time complexity of your solution?

Show answer

The solution first builds the prefix array in O(n) time, then answers each of the q queries in O(1) time. The function would be:

def answer_queries(nums, queries):
    prefix = [0]
    for num in nums:
        prefix.append(prefix[-1] + num)
    return [prefix[r+1] - prefix[l] for l, r in queries]

The total time complexity is O(n + q), where n is the length of the array and q is the number of queries. Without prefix sums, the brute force approach would be O(n × q), which is much slower when both n and q are large.

Question 4: APPLIED

A store tracks daily revenue over 30 days in an array revenue. The manager wants to compare total revenue for Week 1 (days 0–6), Week 2 (days 7–13), Week 3 (days 14–20), and Week 4 (days 21–27). Describe how prefix sums help, and write the Python code to find the revenue for each week.

Show answer

Build a prefix sum array from revenue once in O(30) time. Then each week's total is a single subtraction. The code:

prefix = [0]
for r in revenue:
    prefix.append(prefix[-1] + r)
weeks = [(0,6),(7,13),(14,20),(21,27)]
for l, r in weeks:
    print(prefix[r+1] - prefix[l])

This is far more efficient than summing 7 elements four separate times, especially if the manager later asks for custom date ranges. The prefix array lets you answer any range query in O(1) without recalculating.

Question 5: CRITICAL THINKING

Suppose you need to find the subarray of length exactly k that has the maximum sum. Explain how you can solve this in O(n) time using prefix sums. How does this compare to a brute force approach?

Show answer

First, build the prefix sum array in O(n). Then, for every valid starting index i from 0 to n − k, compute prefix[i + k] − prefix[i] and track the maximum. This examines n − k + 1 candidates, each in O(1) time, for a total of O(n). The brute force approach would compute each subarray sum by looping through k elements, giving O(n × k) time. For large arrays and large k values, the prefix sum approach is dramatically faster. This problem illustrates how prefix sums turn what appears to be a nested-loop problem into a single-pass problem. In Python: max_sum = max(prefix[i+k] - prefix[i] for i in range(len(nums) - k + 1)).

SUMMARY

Lesson Summary

Summary

A prefix sum array stores the cumulative total of elements from the beginning of an array up to each position. It is built in O(n) time by iterating once through the original array, and each entry satisfies prefix[i] = prefix[i − 1] + nums[i − 1] with prefix[0] = 0. Once constructed, any range-sum query from index l to index r is answered in O(1) time using the formula prefix[r + 1] − prefix[l].

This technique shines when the data is static and you face many queries, transforming a problem from O(n × q) to O(n + q). Watch for off-by-one errors in indexing — the leading zero and the use of r + 1 are the most common pitfalls. As you advance, the same precomputation mindset extends to 2D prefix sums, Fenwick trees, and segment trees.