Prefix Sums — Use prefix sums for range queries (intro) |...

SECTION 1

Historical Context & Motivation

Imagine you are building a weather app that stores the daily rainfall for an entire year. A user asks, "How much rain fell between March 15 and June 30?" The brute-force approach would loop through every day in that range and add up the values. That works, but what if thousands of users each ask about different date ranges every second? Looping each time quickly becomes too slow.

The idea of prefix sums — also called cumulative sums — has roots in early computing and mathematics. Mathematicians have long used cumulative totals in statistics and calculus, and computer scientists adopted the technique as soon as array-based computation became practical. The pattern is so fundamental that it appears in database engines, image processing, and competitive programming alike.

1940s

Cumulative Distribution Functions

Statisticians formalize cumulative sums to quickly compute probabilities over ranges of data, laying the mathematical groundwork for prefix sums.

1960s

Early Array Algorithms

As mainframe computers adopt array-based storage, engineers begin pre-computing running totals to speed up repeated range queries in scientific applications.

1984

Summed-Area Table (SAT)

Franklin Crow publishes the summed-area table for texture mapping in computer graphics — a 2-D extension of prefix sums that computes rectangular region sums in constant time.

2000s

Competitive Programming Boom

Online judges like USACO and Codeforces popularize prefix sum problems, making the technique a must-know pattern for students learning algorithms.

The central question prefix sums answer is: How can we answer many range-sum queries on the same array without re-adding elements each time? By spending a small amount of work up front, we can reduce every future query to a single subtraction.

SECTION 2

Core Principles & Definitions

A prefix sum array is a helper array where each element stores the sum of all original elements from the start up to (and including) that index. Once built, you can find the sum of any contiguous sub-range in constant time — no loop required. The core ideas break down into a few simple principles.

Pre-computation

Build the prefix sum array in a single pass through the original data. This costs O(n) time and O(n) space, but it only happens once.

Range Query Formula

The sum from index L to R equals prefix[R] − prefix[L − 1]. This subtraction gives you the answer in O(1) time, no matter how large the range.

Trade-off: Space for Speed

You use extra memory (the prefix array) to avoid repeated work. This is a classic time–space trade-off that shows up throughout computer science.

Static Data Assumption

Basic prefix sums work best when the original array does not change between queries. If elements are updated frequently, more advanced structures are needed.

✦ KEY TAKEAWAY

Think of a prefix sum array like a running odometer on a car. To find the distance driven between two checkpoints, you don't re-drive the route — you simply subtract the earlier odometer reading from the later one. The prefix sum array records the "odometer" at every index, so any range total is just one subtraction.

SECTION 3

Visual Explanation

The diagram below shows how an original array is transformed into its prefix sum array, and then how a range query is answered by a single subtraction.

The top row is the original array. The purple row is the prefix sum array where each cell holds the cumulative total from index 0. The highlighted cyan region shows a range query answered by subtracting pre[0] from pre[4].

Notice how the prefix array at index i always equals the sum of arr[0] through arr[i]. To get the sum from index L to R, you take pre[R] − pre[L − 1]. If L is 0, you just use pre[R] directly since there is nothing to subtract. This single subtraction replaces what could be a loop over thousands of elements.

SECTION 4

Mathematical Framework

Let's formalize the two operations — building the prefix array and querying a range — with clear formulas and their Big-O complexities.

PREFIX ARRAY CONSTRUCTION

pre[i] = pre[i − 1] + arr[i] (for i ≥ 1, with pre[0] = arr[0])

Where arr is the original array of length n, and pre is the prefix sum array. Building this takes O(n) time.

RANGE SUM QUERY

sum(L, R) = pre[R] − pre[L − 1] (if L > 0) sum(0, R) = pre[R]

L is the left index and R is the right index (both inclusive). Each query takes O(1) time — constant, regardless of range size.

TOTAL COMPLEXITY

O(n) pre-processing + O(1) per query → O(n + Q) for Q queries

Compare this to brute force, which costs O(n × Q) in the worst case. For large n and Q, the prefix sum approach is dramatically faster.

⚠️ Common Pitfall: Off-by-One Errors

Many students accidentally compute pre[R] − pre[L] instead of pre[R] − pre[L − 1]. This excludes arr[L] from the sum. A popular trick is to define pre with length n + 1, where pre[0] = 0 and pre[i] = pre[i − 1] + arr[i − 1]. Then the query becomes simply pre[R + 1] − pre[L], which is cleaner and avoids the special case when L = 0.

SECTION 5

Java Implementation & Walk-Through

Below is a complete Java implementation showing both the construction of the prefix sum array and range queries. We use the size n + 1 trick so that every query follows the same formula with no special cases.

The prefix array has length n + 1. Index 0 is always 0, so the range query formula pre[R+1] − pre[L] works uniformly, even when L is 0.

Notice the key detail: the prefix array pre has n + 1 elements. The extra slot at index 0 holds 0, which represents the sum of zero elements. This means pre[i+1] equals the sum of arr[0] through arr[i]. When you compute pre[R+1] − pre[L], the formula naturally handles every case including L = 0. You never need an if-statement to check for the boundary.

Complete mapping between original array indices and the size n+1 prefix sum array

Index i	arr[i]	pre[i] (size n+1)	Meaning of pre[i]
0	—	`0`	Sum of 0 elements
1	2 (arr[0])	`2`	Sum of arr[0..0]
2	5 (arr[1])	`7`	Sum of arr[0..1]
3	1 (arr[2])	`8`	Sum of arr[0..2]
4	8 (arr[3])	`16`	Sum of arr[0..3]
5	3 (arr[4])	`19`	Sum of arr[0..4]
6	7 (arr[5])	`26`	Sum of arr[0..5]

SECTION 6

Worked Example

A teacher records daily quiz scores for a student over one week: int[] scores = {88, 92, 75, 95, 83, 90, 78}. She wants to quickly answer questions like "What was the total score from Tuesday (index 1) to Friday (index 4)?" Let's solve this step by step using a prefix sum array.

Range Sum of Quiz Scores

Step 1 — Identify the DataThe original array is scores = {88, 92, 75, 95, 83, 90, 78} with n = 7. We need the sum from L = 1 to R = 4 (Tuesday through Friday).

Step 2 — Build the Prefix Sum Array (size n + 1 = 8)Start with pre[0] = 0. Then: pre[1] = 0 + 88 = 88, pre[2] = 88 + 92 = 180, pre[3] = 180 + 75 = 255, pre[4] = 255 + 95 = 350, pre[5] = 350 + 83 = 433, pre[6] = 433 + 90 = 523, pre[7] = 523 + 78 = 601.

pre = [0, 88, 180, 255, 350, 433, 523, 601]

Step 3 — Apply the Range Query Formulasum(L, R) = pre[R + 1] − pre[L]. Substituting L = 1 and R = 4: sum(1, 4) = pre[5] − pre[1] = 433 − 88.

sum(1, 4) = 345

Step 4 — Verify by Direct AdditionAdding scores[1] through scores[4] directly: 92 + 75 + 95 + 83 = 345. The answer matches, confirming the prefix sum approach is correct.

✓ Verified: 345

Step 5 — Answer a Second Query for FreeNow the teacher asks for the total from Wednesday (index 2) to Sunday (index 6). Using the same prefix array: sum(2, 6) = pre[7] − pre[2] = 601 − 180 = 421. No extra loops needed — we reused the prefix array.

sum(2, 6) = 421

SECTION 7

Strengths, Limitations & Comparisons

Prefix sums are a powerful tool, but every tool has its limits. The table below compares the brute-force approach with prefix sums across several dimensions so you can see when each one is appropriate.

Brute-force vs. prefix sum comparison

Feature	Brute-Force Loop	Prefix Sum Array
Pre-processing time	None (O(0))	O(n) — one pass
Per-query time	O(n) worst case	O(1)
Total for Q queries	O(n × Q)	O(n + Q)
Extra memory	None	O(n)
Handles updates?	Yes — always reads fresh data	No — must rebuild after changes
Best when...	Only 1 or 2 queries needed	Many queries on static data

💡 WHEN TO USE PREFIX SUMS

Use prefix sums whenever the problem asks for multiple range sum queries on data that doesn't change. If the data is frequently updated between queries, look ahead to structures like a Fenwick tree (Binary Indexed Tree) or a segment tree, which handle updates efficiently.

SECTION 8

Connection to Advanced Techniques

The prefix sum pattern is a stepping stone toward several more advanced data structures and algorithms. Understanding this foundation makes learning those topics far easier.

Where prefix sums lead — related data structures

Technique	What It Adds	Use Case
2-D Prefix Sums	Extends the idea to a grid (matrix). Each cell stores the sum of the rectangle from (0,0) to (r,c).	Image processing, sub-rectangle sum queries
Difference Array	The inverse of prefix sums. Stores differences between consecutive elements; a prefix sum of the difference array recovers the original.	Efficiently applying range updates (add k to every element from L to R)
Fenwick Tree (BIT)	A tree structure that supports both point updates and prefix queries in O(log n) time.	Dynamic data where both queries and updates happen frequently
Segment Tree	A balanced binary tree that answers arbitrary range queries (min, max, sum, GCD, etc.) in O(log n) with updates.	Competitive programming, database engines

Each of these more advanced tools builds on the intuition you now have: pre-compute cumulative information so that queries become fast. Mastering the basic prefix sum array is your first step into this powerful family of techniques. If you go on to take AP Computer Science A or participate in competitive programming, you will see these ideas again and again.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

In your own words, explain why a prefix sum array lets you answer range sum queries in O(1) time. What information does each element of the prefix array encode?

PROBLEM 2 — BASIC CALCULATION

Given arr = {4, 7, 2, 5, 9}, build the prefix sum array (using the n + 1 convention) and compute rangeSum(1, 3).

PROBLEM 3 — INTERMEDIATE

You are given an integer array of length n and Q range-sum queries. If n = 100,000 and Q = 200,000, how many total operations does the brute-force approach require in the worst case? How many does the prefix sum approach require? Express each as a number.

PROBLEM 4 — APPLIED

A fitness tracker records your daily step count for 30 days in an array steps[]. Write a Java method averageSteps(int[] steps, int L, int R) that uses prefix sums to return the average daily steps between day L and day R (inclusive). Assume the prefix array is already built and passed in. Return a double.

PROBLEM 5 — CRITICAL THINKING

Suppose you have an array of 1,000,000 integers and you need to answer range sum queries. However, between every 10 queries, one element in the array gets updated. Should you use a basic prefix sum array, rebuild it after every update, or consider a different data structure? Justify your answer with Big-O reasoning.

SUMMARY

Lesson Summary

A prefix sum array stores cumulative totals so that any range sum query can be answered in O(1) time with a single subtraction. Building the array takes O(n) pre-processing and O(n) extra space. The core formula using the n + 1 convention is sum(L, R) = pre[R + 1] − pre[L], which avoids off-by-one errors and handles every boundary case cleanly.

This technique excels when the data is static (unchanging) and many queries are needed. For dynamic data, consider a Fenwick tree or segment tree. The prefix sum pattern also extends to two dimensions (2-D prefix sums) and has a natural inverse in the difference array technique. Master this foundational pattern, and you'll have a reliable tool for a wide variety of array problems.