Prefix sums for instant range totals

A prefix sum array holds the running totals of a list, with a 0 in front: prefix[0] = 0 and prefix[i + 1] = prefix[i] + a[i], so prefix[i] is the total of the first i items. The total of any stretch, from item first to item last, is then one subtraction, prefix[last + 1] - prefix[first], however long the stretch is. Building the array takes one pass over the list, O(n), and every range total after that costs O(1). Reach for it when a list that does not change is asked many questions of the form “what is the total from here to there?”. This lesson builds the array, solves one problem completely (the brute force, the fast version, why it is right, a dry run, code that runs in four languages, a stress test and the overflow trap), then finds the same idea inside a problem that never mentions ranges.

Running totals, with a 0 in front

A small shop writes down what it took each day. Here are 14 days of its ledger, with the prefix list built by a loop and again by itertools.accumulate, and four questions about it:

from itertools import accumulate

# What a small shop took on each of 14 days, day 0 first.
sales = [420, 380, 0, 515, 610, 290, 700, 455, 390, 660, 0, 530, 480, 625]

# prefix[i] is the total of the first i days: prefix[0] = 0, and prefix has one entry more than sales.
prefix = [0]
for amount in sales:
    prefix.append(prefix[-1] + amount)

print("sales: ", sales)
print("prefix:", prefix)
print("the same list from accumulate:", list(accumulate(sales, initial=0)) == prefix)


def total(first, last):
    """The sales from day `first` to day `last`, both days included."""
    return prefix[last + 1] - prefix[first]


for first, last in [(2, 4), (7, 13), (0, 10), (3, 3)]:
    print(f"days {first} to {last}: {total(first, last)}")

# Without the 0 in front, running[i] covers days 0 to i, and a range starting on day 0 needs a special case.
# Forget it, and running[first - 1] is running[-1]: Python reads the last entry instead of failing.
running = list(accumulate(sales))
print("days 0 to 2 without the 0 in front:", running[2] - running[0 - 1])

sales:  [420, 380, 0, 515, 610, 290, 700, 455, 390, 660, 0, 530, 480, 625]
prefix: [0, 420, 800, 800, 1315, 1925, 2215, 2915, 3370, 3760, 4420, 4420, 4950, 5430, 6055]
the same list from accumulate: True
days 2 to 4: 1125
days 7 to 13: 3140
days 0 to 10: 4420
days 3 to 3: 515
days 0 to 2 without the 0 in front: -5255

The prefix list has 15 entries for 14 days. prefix[5] is 1,925, the total of the first five days, days 0 to 4, and prefix[2] is 800, the total of days 0 and 1. Their difference is what days 2 to 4 add on top of the first two days, and that is the answer to the first question:

The same subtraction answers every question, from the second week to a single day. “Month to date on day 10” is the range from day 0 to day 10, and it needs no special case: prefix[0] is 0, so nothing is taken away.

accumulate(sales, initial=0) builds the same list in one call. The initial argument arrived in Python 3.8, and the documentation says that with it the output has one more element than the input, which is exactly the 0 in front. Without it, accumulate gives the totals of days 0 to i, and a range that starts on day 0 needs an if. The last line of the output shows what happens when that if is forgotten: running[0 - 1] is running[-1], which Python reads as the last entry of the list, so the program prints a negative total and raises no error.

A worked problem: totals for many ranges

The problem below is the one this module’s pattern was made for. Here it is worked in full, in the order a coding round asks for: the brute force, what to notice, the fast version, why it is correct, a dry run, the cost, code, a stress test, edge cases and follow-up questions.

For the first week of the ledger above, sales = [420, 380, 0, 515, 610, 290, 700], and the queries (2, 4), (0, 6), (3, 3), (0, 0) and (6, 6) have the answers 1,125, 2,915, 515, 420 and 700.

Brute force first

Add up the days of each query again:

def range_totals_brute(sales, queries):
    """Adds up the days of every query again: up to n additions per query."""
    answers = []
    for first, last in queries:
        total = 0
        for day in range(first, last + 1):
            total += sales[day]
        answers.append(total)
    return answers


if __name__ == "__main__":
    sales = [420, 380, 0, 515, 610, 290, 700]
    print(range_totals_brute(sales, [(2, 4), (0, 6), (3, 3), (0, 0), (6, 6)]))

[1125, 2915, 515, 420, 700]

It is correct by construction, and it is slow. A query can cover the whole ledger, so each one costs up to n additions and all of them cost O(n × q). At the limits that is up to 200,000 × 200,000 = 4 × 10¹⁰ additions. Even compiled code, budgeted at 10⁸ simple steps a second as in the lesson on reading constraints, would need about 400 seconds, against a time limit of a second or two. Keep the brute force anyway: it checks the fast version below.

What to notice

The ledger never changes between queries, yet the brute force adds the same days again and again: every query that covers day 3 adds sales[3] once more. That is the cue for prefix sums. Look for three things together: many queries, each asking for a total (or a count) over a contiguous range, on data that stays the same while the queries run. Do the shared work once, as running totals, and each query becomes a lookup.

The fast version, step by step

1. Make a list prefix of n + 1 zeros.
2. In one pass over the days, set prefix[day + 1] = prefix[day] + sales[day].
3. Answer each query (first, last) with prefix[last + 1] - prefix[first].

Here it is in Python and JavaScript, which you can run on this page, and in Java and C++:

def range_totals(sales, queries):
    """Builds the prefix totals once, in one pass, then answers each query with one subtraction."""
    prefix = [0] * (len(sales) + 1)  # prefix[0] stays 0
    for day, amount in enumerate(sales):
        prefix[day + 1] = prefix[day] + amount
    return [prefix[last + 1] - prefix[first] for first, last in queries]


if __name__ == "__main__":
    sales = [420, 380, 0, 515, 610, 290, 700]
    print(range_totals(sales, [(2, 4), (0, 6), (3, 3), (0, 0), (6, 6)]))

    # The largest ledger the limits allow: 200,000 days of 1,000,000,000 each.
    big = [1_000_000_000] * 200_000
    print(range_totals(big, [(0, 199_999)])[0])

[1125, 2915, 515, 420, 700]
200000000000000

// Builds the prefix totals once, in one pass, then answers each query with one subtraction.
function rangeTotals(sales, queries) {
  const prefix = new Array(sales.length + 1).fill(0);
  for (let day = 0; day < sales.length; day++) prefix[day + 1] = prefix[day] + sales[day];
  return queries.map(([first, last]) => prefix[last + 1] - prefix[first]);
}

const sales = [420, 380, 0, 515, 610, 290, 700];
console.log(JSON.stringify(rangeTotals(sales, [[2, 4], [0, 6], [3, 3], [0, 0], [6, 6]])));

// The largest total the limits allow, 2 × 10^14, is still an exact JavaScript number (below 2^53 - 1).
const big = new Array(200_000).fill(1_000_000_000);
const total = rangeTotals(big, [[0, 199_999]])[0];
console.log(`${total} is a safe integer: ${Number.isSafeInteger(total)}`);

[1125,2915,515,420,700]
200000000000000 is a safe integer: true

import java.util.Arrays;

public class RangeTotals {
    /** Builds the prefix totals once, in one pass, then answers each query with one subtraction. */
    static long[] rangeTotals(long[] sales, int[][] queries) {
        long[] prefix = new long[sales.length + 1]; // Java fills it with zeros, so prefix[0] = 0
        for (int day = 0; day < sales.length; day++) {
            prefix[day + 1] = prefix[day] + sales[day];
        }
        long[] answers = new long[queries.length];
        for (int q = 0; q < queries.length; q++) {
            int first = queries[q][0], last = queries[q][1];
            answers[q] = prefix[last + 1] - prefix[first];
        }
        return answers;
    }

    public static void main(String[] args) {
        long[] sales = {420, 380, 0, 515, 610, 290, 700};
        int[][] queries = {{2, 4}, {0, 6}, {3, 3}, {0, 0}, {6, 6}};
        System.out.println(Arrays.toString(rangeTotals(sales, queries)));

        // The largest ledger the limits allow: 200,000 days of 1,000,000,000 each.
        long[] big = new long[200_000];
        Arrays.fill(big, 1_000_000_000L);
        System.out.println(rangeTotals(big, new int[][] {{0, 199_999}})[0]);
    }
}

#include <iostream>
#include <numeric>
#include <utility>
#include <vector>

// Builds the prefix totals once, in one pass, then answers each query with one subtraction.
std::vector<long long> range_totals(const std::vector<long long>& sales,
                                    const std::vector<std::pair<int, int>>& queries) {
    std::vector<long long> prefix(sales.size() + 1, 0);  // prefix[0] stays 0
    std::partial_sum(sales.begin(), sales.end(), prefix.begin() + 1);
    std::vector<long long> answers;
    answers.reserve(queries.size());
    for (auto [first, last] : queries) answers.push_back(prefix[last + 1] - prefix[first]);
    return answers;
}

int main() {
    std::vector<long long> sales{420, 380, 0, 515, 610, 290, 700};
    std::vector<std::pair<int, int>> queries{{2, 4}, {0, 6}, {3, 3}, {0, 0}, {6, 6}};
    const char* gap = "";
    for (long long total : range_totals(sales, queries)) {
        std::cout << gap << total;
        gap = " ";
    }
    std::cout << '\n';

    // The largest ledger the limits allow: 200,000 days of 1,000,000,000 each.
    std::vector<long long> big(200'000, 1'000'000'000);
    std::cout << range_totals(big, {{0, 199'999}})[0] << '\n';
}

The Java and C++ versions, compiled and run:

from session import run

run("""
g++-16 --version | head -n 1
g++-16 -std=c++23 -O2 -Wall -Wextra range_totals.cpp -o range_totals && ./range_totals
java -version 2>&1 | head -n 1 | cut -d ' ' -f 1-3
java RangeTotals.java
""")

$ g++-16 --version | head -n 1
g++-16 (Homebrew GCC 16.2.0) 16.2.0
$ g++-16 -std=c++23 -O2 -Wall -Wextra range_totals.cpp -o range_totals && ./range_totals
1125 2915 515 420 700
200000000000000
$ java -version 2>&1 | head -n 1 | cut -d ' ' -f 1-3
openjdk version "27"
$ java RangeTotals.java
[1125, 2915, 515, 420, 700]
200000000000000

All four print the same five answers, then the total of the largest ledger the limits allow, 200,000 days of 10⁹, which is 2 × 10¹⁴. Java and C++ keep the prefix totals in 64-bit integers (long and long long); the section on overflow below shows why. The C++ version builds the list with std::partial_sum from <numeric>, writing from prefix.begin() + 1 so that prefix[0] stays 0. In Go, the same loop needs int64 for the totals: the language specification allows int to be 32 or 64 bits wide.

Why it is correct

The loop keeps one fact true, its invariant: after it has handled day d, prefix[d + 1] is the total of days 0 to d. It holds at the start, where prefix[0] is the total of no days at all, 0, and each step adds exactly the next day. So once the loop ends, prefix[i] is the total of the first i days for every i from 0 to n.

A query then subtracts two such totals. prefix[last + 1] is the total of days 0 to last, and prefix[first] is the total of days 0 to first − 1. The days before first are in both, so they cancel, and what is left is the total of days first to last, which is the answer. When first is 0, nothing is taken away, and the formula still holds.

A dry run

For the first week, prefix is [0, 420, 800, 800, 1315, 1925, 2215, 2915], and each query reads two entries:

• (2, 4): prefix[5] - prefix[2] = 1,925 − 800 = 1,125
• (0, 6): prefix[7] - prefix[0] = 2,915 − 0 = 2,915
• (3, 3): prefix[4] - prefix[3] = 1,315 − 800 = 515
• (0, 0): prefix[1] - prefix[0] = 420 − 0 = 420
• (6, 6): prefix[7] - prefix[6] = 2,915 − 2,215 = 700

Day 2 had no sales, so prefix[2] and prefix[3] are equal, and the query (3, 3) returns sales[3] alone.

The cost

At the limits, the prefix version does 200,000 additions and 200,000 subtractions instead of up to 4 × 10¹⁰ additions. The price is memory: n + 1 extra numbers, 1.6 MB as 64-bit integers for 200,000 days.

Check it against the brute force

A stress test, as in the lesson on brute force to optimal, compares the fast version with the brute force on many small random ledgers, the shortest first. It also tries a version with a plausible slip, prefix[last] - prefix[first]:

import random

from brute import range_totals_brute
from range_totals import range_totals


def range_totals_short(sales, queries):
    """A plausible slip: prefix[last] - prefix[first] stops one day early."""
    prefix = [0]
    for amount in sales:
        prefix.append(prefix[-1] + amount)
    return [prefix[last] - prefix[first] for first, last in queries]


def first_failure(candidate, cases=1_000, seed=6):
    """Runs candidate and the brute force on small random ledgers, shortest first, until they disagree."""
    rng = random.Random(seed)
    for case in range(cases):
        days = 1 + case * 8 // cases  # 1 to 8 days
        sales = [rng.randint(0, 9) for _ in range(days)]
        queries = []
        for _ in range(3):
            first = rng.randrange(days)
            queries.append((first, rng.randrange(first, days)))
        got, expected = candidate(sales, queries), range_totals_brute(sales, queries)
        if got != expected:
            return f"fails on sales {sales}, queries {queries}: got {got}, expected {expected}"
    return f"agrees with the brute force on {cases:,} random ledgers"


print("range_totals:      ", first_failure(range_totals))
print("range_totals_short:", first_failure(range_totals_short))

range_totals:       agrees with the brute force on 1,000 random ledgers
range_totals_short: fails on sales [9], queries [(0, 0), (0, 0), (0, 0)]: got [0, 0, 0], expected [9, 9, 9]

The correct version agrees on all 1,000 ledgers. The slip fails on the first ledger with a day that sold something: a single day of 9 and the query (0, 0). It returns 0, because prefix[last] - prefix[first] is the total of days first to last − 1, which stops one day early, and for a one-day range that leaves no day at all.

Edge cases and common bugs

• A range starting on day 0 needs no special case, thanks to the 0 in front.
• A range of one day, first == last, returns prefix[first + 1] - prefix[first], which is sales[first].
• Days numbered from 1 in the input: convert each query once, or use prefix[last] - prefix[first - 1]. Settle this in the clarifying step, before you write the formula.
• Negative values, such as refunds, change nothing: prefix sums never needed the numbers to be positive.
• A ledger that changes after the prefix list is built makes every later prefix out of date. Prefix sums suit data that stays the same while the queries run.
• Totals that outgrow their type, the bug that tests with small numbers never catch. It has its own section below.

Variants

The same list answers more than totals:

• Month to date is the range from the first day of the month to today.
• An average over a range is the range total divided by last - first + 1, the number of days.
• A count of days that match a condition is a prefix sum of ones and zeros, one for each day that matches. The exercise below counts days with no sales this way.
• Any operation that can be undone works like addition. XOR is one: x ^ x is 0, so a range’s XOR is prefix[last + 1] ^ prefix[first]. A minimum or a maximum cannot be undone, so range minimums need a different structure, which a later module builds.

Follow-up questions

Can you answer the queries with O(1) extra memory? Yes, by turning sales itself into running totals (sales[day] += sales[day - 1] from day 1 on). A range is then sales[last], minus sales[first - 1] when first is above 0. You lose the original figures, and the special case for day 0 comes back.

The shop adds a new day to the ledger. Do you rebuild everything? No: append prefix[-1] + new_day to the prefix list. It costs O(1), and the old prefixes stay correct, because a new day only ever comes after them.

When the total does not fit

The largest number the prefix list holds is its last entry, the total of the whole ledger: up to 200,000 × 10⁹ = 2 × 10¹⁴. The largest Java int is 2,147,483,647 (section 4.2.1 of the Java Language Specification), and the specification adds that integer operators give no sign of an overflow (section 4.2.2) and that an addition never throws an exception (section 15.18.2). Here is the largest ledger the problem allows, added up into an int[] and into a long[]:

from session import run

run("""
java Overflow.java
""")

$ java Overflow.java
int prefix,  days 0 to 199999: 552894464
long prefix, days 0 to 199999: 200000000000000

The int version prints 552,894,464: the true total minus 46,566 × 2³², a positive number that looks plausible. The fix is a 64-bit type for the prefix list and the answers: a Java long, a C++ long long (or std::int64_t), a Go int64. Java can keep each day’s sales in an int, as Overflow.java does, because each day fits and Java widens it when it is added to a long. The C++ version above stores the sales as long long as well, so that std::partial_sum adds in 64 bits. In JavaScript every whole number up to 2⁵³ − 1, about 9 × 10¹⁵, is exact, so 2 × 10¹⁴ is safe, which the JavaScript version above checks with Number.isSafeInteger. Python’s integers have unlimited precision. The lesson on edge cases compares how each of five languages behaves when a sum overflows.

Prefix sums inside other problems: the balance day

Prefix sums often appear in problems that never say “range”. Take this one: find the first day on which the sales of all the days before it equal the sales of all the days after it, the day itself counting on neither side, or return −1 if there is no such day.

The brute force adds up both sides again for every day, which is O(n²). Now notice what the two sides are. The days before day d total prefix[d], and the days after it total the whole ledger minus prefix[d] minus sales[d]. So one running total of the days so far, together with the total of the whole ledger, checks each day in O(1):

import random


def balance_day_brute(sales):
    """Adds up both sides again for every day: O(n²)."""
    for day in range(len(sales)):
        if sum(sales[:day]) == sum(sales[day + 1:]):
            return day
    return -1


def balance_day(sales):
    """One running total: the days after `day` hold the whole total minus the days before it minus `day` itself."""
    whole = sum(sales)
    before = 0
    for day, amount in enumerate(sales):
        if before == whole - before - amount:
            return day
        before += amount
    return -1


for sales in ([3, 8, 2, 6, 5], [4, -1, 9, 3], [0, 6, -6], [5, 5], [7]):
    print(sales, balance_day_brute(sales), balance_day(sales))

rng = random.Random(4)
ledgers = [[rng.randint(-3, 3) for _ in range(rng.randint(1, 7))] for _ in range(2_000)]
agree = sum(balance_day(s) == balance_day_brute(s) for s in ledgers)
print(f"same answer on {agree:,} of {len(ledgers):,} random ledgers")

[3, 8, 2, 6, 5] 2 2
[4, -1, 9, 3] 2 2
[0, 6, -6] 0 0
[5, 5] -1 -1
[7] 0 0
same answer on 2,000 of 2,000 random ledgers

Both versions agree on the five ledgers and on 2,000 random ones. The cases worth saying aloud in a round: the first day can balance, because the side before it is empty and totals 0 ([0, 6, -6]); a ledger of one day balances on that day; negative values are fine ([4, -1, 9, 3]); and a ledger with no balance day returns −1 ([5, 5]). This version keeps a single running total instead of a list, because it reads the prefixes in order and never needs one twice.

The signal is a condition that compares what comes before a position with what comes after it: “left and right”, “before and after”, “every way to split”. Running totals from the left, and the whole total, usually make each check O(1).

Prefix sums in each language

How each language builds the prefix list, and the type its totals need:

• Python: accumulate(sales, initial=0) or a loop; an int has no upper limit.
• JavaScript: a loop; a number is exact up to 2⁵³ − 1, and BigInt goes beyond it.
• Java: a loop, or Arrays.parallelPrefix; totals in long.
• C++: std::partial_sum; long long for the totals and for the sales.
• Go: a loop; totals in int64.

Two library calls need a word of care. Arrays.parallelPrefix(a, Long::sum) turns a Java array into its own running totals, in place, so the result has no 0 in front. std::partial_sum writes wherever its third argument points, which is why the C++ version above passes prefix.begin() + 1 and leaves prefix[0] at 0.

Exercise

range_report([420, 0, 515, 0, 0, 290], [(0, 2), (1, 4), (5, 5)])
# [(935, 1), (515, 3), (290, 0)]

def range_report(sales, queries):
    """For each query (first, last): the total sales of those days and how many of them had no sales."""
    # Replace this line with your code.
    return []

import random

from report import range_report


def trusted(sales, queries):
    """Answers the tests trust: add up each range again, and count its zeros."""
    return [(sum(sales[first:last + 1]), sales[first:last + 1].count(0)) for first, last in queries]


def as_pairs(result):
    """Accept tuples or lists for the pairs."""
    return [tuple(pair) for pair in result]


class Ledger(list):
    """A list of sales that counts the values read from it, and stops a solution that reads too many."""

    def __init__(self, values, limit):
        super().__init__(values)
        self.reads = 0
        self.limit = limit

    def _read(self, count):
        self.reads += count
        if self.reads > self.limit:
            raise AssertionError(
                f"too slow: more than {self.limit:,} values were read from a ledger of {len(self):,} days; "
                "build the prefix lists once and answer each query without reading the ledger again"
            )

    def __getitem__(self, index):
        self._read(len(range(*index.indices(len(self)))) if isinstance(index, slice) else 1)
        return super().__getitem__(index)

    def __iter__(self):
        for day in range(len(self)):
            self._read(1)
            yield super().__getitem__(day)


def test_prompt_example():
    """the example from the prompt"""
    assert as_pairs(range_report([420, 0, 515, 0, 0, 290], [(0, 2), (1, 4), (5, 5)])) == [(935, 1), (515, 3), (290, 0)]


def test_single_days():
    """ranges of one day, first == last, quiet and not"""
    sales = [7, 0, 12]
    assert as_pairs(range_report(sales, [(0, 0), (1, 1), (2, 2)])) == [(7, 0), (0, 1), (12, 0)]


def test_whole_ledger():
    """a range from the first day to the last"""
    sales = [5, 0, 9, 0, 3]
    assert as_pairs(range_report(sales, [(0, 4)])) == [(17, 2)]


def test_only_quiet_days():
    """a ledger in which nothing was sold"""
    assert as_pairs(range_report([0, 0, 0, 0], [(0, 3), (1, 2), (3, 3)])) == [(0, 4), (0, 2), (0, 1)]


def test_largest_values():
    """200,000 days of 10^9, with one quiet day: totals far above 2^31"""
    sales = [1_000_000_000] * 200_000
    sales[150_000] = 0
    queries = [(0, 199_999), (100_000, 199_999), (150_000, 150_000)]
    assert as_pairs(range_report(sales, queries)) == [(199_999_000_000_000, 1), (99_999_000_000_000, 1), (0, 1)]


def test_random_small_ledgers():
    """300 random ledgers of up to 10 days, against answers the tests trust"""
    rng = random.Random(8)
    for _ in range(300):
        days = rng.randint(1, 10)
        sales = [rng.choice([0, 0, 1, 5, 40]) for _ in range(days)]
        queries = []
        for _ in range(4):
            first = rng.randrange(days)
            queries.append((first, rng.randrange(first, days)))
        assert as_pairs(range_report(sales, queries)) == trusted(sales, queries), f"range_report({sales}, {queries})"


def test_many_long_queries():
    """20,000 days and 20,000 long queries, reading at most four values per day"""
    rng = random.Random(3)
    days = 20_000
    values = [rng.choice([0, rng.randint(1, 1_000_000_000)]) for _ in range(days)]
    queries = [(rng.randrange(10), rng.randrange(days - 10, days)) for _ in range(20_000)]
    prefix, quiet = [0], [0]
    for amount in values:
        prefix.append(prefix[-1] + amount)
        quiet.append(quiet[-1] + (amount == 0))
    expected = [(prefix[last + 1] - prefix[first], quiet[last + 1] - quiet[first]) for first, last in queries]
    assert as_pairs(range_report(Ledger(values, limit=4 * days), queries)) == expected

Interview questions

What is a prefix sum array, and how does it give the total of a range in O(1)? It is the list of running totals of an array, with a 0 in front: prefix[0] = 0 and prefix[i + 1] = prefix[i] + a[i], so prefix[i] is the total of the first i items. Building it takes one pass, O(n) time and n + 1 numbers of memory. The total of a[first] to a[last] is prefix[last + 1] - prefix[first]: both prefixes contain the items before first, so they cancel, and exactly the range is left. That is one subtraction, whatever the length of the range. It fits an array that does not change and is asked many range totals: for q queries over n items it turns O(n × q) into O(n + q).

Why do many prefix-sum solutions put a 0 at the start, so that the array has n + 1 entries? With the 0, prefix[i] is the total of the first i items, and every range has the same formula, prefix[last + 1] - prefix[first], including ranges that start at item 0, where nothing is taken away. Without it, the array holds the totals of items 0 to i, and a range starting at 0 needs a special case, because the formula would read the entry before index 0. In Python that mistake does not even fail: index −1 is the last entry, so the answer is silently wrong. The extra entry costs one number of memory and removes a whole family of off-by-one errors.

Key takeaways

• A prefix list holds running totals with a 0 in front: prefix[i] is the total of the first i items.
• The total of items first to last is prefix[last + 1] - prefix[first]: O(n) to build, then O(1) per query.
• The cue is many range totals or counts over data that does not change while the queries run.
• The invariant, “prefix[i] is the total of the first i items”, is the whole proof: the shared prefix cancels.
• Check the fast version against the brute force with a stress test; an off-by-one slip fails on the smallest input.
• Size the type from the largest prefix: 2 × 10⁵ days of 10⁹ need 64-bit totals in Java, C++ and Go.
• Conditions that compare what comes before a position with what comes after it are prefix sums in disguise.