A girl and a robot thinking together

Think it through · Start with a story

The girl keeps asking how many pages she read over several consecutive days. The robot first records the total up to each day, so later it can answer by subtracting.

Break Down the Process

Follow the numbered steps, then explain them in your own words
  1. Original data2, 3, 4
  2. Prefix sums0, 2, 5, 9
  3. Ask for days 2 to 39 minus 2
  4. Answer7 pages

A prefix sum stores the cumulative total from the beginning of the data up to a position.

Here we use an array P with P[0] = 0. The sum of items 2 through 3 is P[3] − P[1]: subtract the portion before the first item we want.

01What If We Keep Asking for Range Sums?

Consider this array:

2  5  3  7  4

If we ask only once for the sum of the second through fourth numbers, adding them directly is fine.

But if we ask thousands of times, adding each range from scratch repeats a lot of work.

02What Is a Prefix Sum?

First calculate the cumulative sum from the beginning through each position.

First i elements012345
prefix[i]027101721

03Why Add prefix[0] = 0?

This is a very common design:

prefix[0] = 0;   prefix[i] = prefix[i - 1] + a[i];

With 1-based indexing for the original data, prefix[i] represents the sum of the first i elements.

04Why Can a Range Sum Be Found by Subtraction?

To find the sum from l to r:

sum(l,r) = prefix[r] - prefix[l-1]

prefix[r] includes the first r numbers. Subtract the first l−1 numbers, and only the values from l through r remain.

05Why Do Queries Get Faster?

Add Everything Each Time

A long range requires visiting many elements.

Use Prefix Sums

Each query needs only a fixed number of array accesses and a subtraction.

Building the prefix sums takes O(n). After that, each ordinary range-sum query takes O(1).

06Can a Prefix Sum Overflow?

Yes. Even if each element fits in an int, the cumulative total may exceed the range of an int.

std::vector<long long> prefix(n + 1);

In competitive programming, estimate the largest possible total before choosing a type.

07What If the Array Changes?

Ordinary prefix sums are useful when the data stays mostly unchanged and there are many queries.

If the original array changes frequently, many later prefix values may be affected. In that case, structures such as Fenwick trees or segment trees may be more suitable.

What You Have Learned

  • Prefix sums store cumulative totals from the beginning through each position.
  • A common definition sets prefix[0]=0.
  • A range sum over [l,r] can be found by subtracting two prefix sums.
  • Preprocessing takes O(n), and an ordinary range-sum query takes O(1).
  • Watch out for integer overflow in cumulative totals.

Next: Greedy Algorithms: Make the Best Choice at Each Step

Your Turn to Try

Why is the total for days 1 through 2 equal to 5 − 0?

Have you decided? Open to see the explanation

P[2] includes the first two days, and P[0] means that no days have been included yet. Subtracting 0 leaves 5. This extra zero makes boundary cases consistent.