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.
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.
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
nums with n elements, indexed from 0 to n − 1. This is your raw input data.Prefix Sum 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
l to index r (inclusive)?" Prefix sums answer this in O(1) time.O(1) vs O(n)
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.
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.
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.
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.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.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.
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.
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.
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: 9The 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.
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.
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."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]sum(2, 5). Apply the formula: prefix[5 + 1] − prefix[2] = prefix[6] − prefix[2]. That gives us 38 − 14 = 24.prefix[7] − prefix[0] = 42 − 0 = 42. This is simply the last element of the prefix array, which is the total of all scores.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 |
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 |
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.
Practice Problems
nums = [4, 1, 3, 2, 6], build the prefix sum array and then compute sum(1, 4).[l, r]) and returns a list of results. Use prefix sums to make it efficient. What is the time complexity of your solution?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.Lesson 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.