Prefix sums and difference arrays

A prefix sum array stores running totals: prefix[0] = 0, and prefix[i] is the total of the first i items of an array. Building it takes one pass, O(n). After that, the total of any range a[first..last] is one subtraction, prefix[last + 1] − prefix[first], because both prefixes contain the items before first and they cancel. A difference array runs the idea backwards. To add v to every item of a range, record +v where the range starts and −v just after it ends; once all the updates are recorded, one running total turns the marks into the final values, so q range updates cost O(n + q) instead of up to n × q. Prefix sums suit many range questions about data that does not change; difference arrays suit many range updates made before anyone reads the values.

Range totals in one subtraction

A year of daily rainfall makes a good test: 365 numbers and endless questions such as “how much fell between day 151 and day 242?”. Adding up the range each time costs up to 365 additions per question. With prefix sums the year is added up once, and every question after that is answered by one subtraction:

"""Rainfall totals for any range of days, from a prefix array of a year of synthetic daily readings.

prefix[i] is the total of the first i days, with prefix[0] = 0, so the total of days first to last (counting from 0,
both included) is prefix[last + 1] - prefix[first]. The program also counts the additions each method needs.
"""

import random

rng = random.Random(365)
rain_mm = [rng.choice([0, 0, 0, 1, 2, 4, 7, 12, 25, 40]) for _ in range(365)]  # synthetic daily rainfall in mm

prefix = [0] * (len(rain_mm) + 1)
for i, mm in enumerate(rain_mm):
    prefix[i + 1] = prefix[i] + mm
print("first ten days:", rain_mm[:10])
print("prefix[0..10]: ", prefix[:11])

queries = [(0, 364), (151, 242), (10, 10), (300, 330)]
for first, last in queries:
    total = prefix[last + 1] - prefix[first]
    assert total == sum(rain_mm[first : last + 1])
    print(f"days {first:>3} to {last:>3}: {total:>5} mm  = prefix[{last + 1}] - prefix[{first}]")

q = 100_000
print(f"{q:,} random range queries: up to {q * 365:,} additions one by one, {365 + q:,} operations with the prefix array")

first ten days: [2, 0, 2, 40, 1, 25, 7, 40, 7, 25]
prefix[0..10]:  [0, 2, 2, 4, 44, 45, 70, 77, 117, 124, 149]
days   0 to 364:  3065 mm  = prefix[365] - prefix[0]
days 151 to 242:   668 mm  = prefix[243] - prefix[151]
days  10 to  10:     0 mm  = prefix[11] - prefix[10]
days 300 to 330:   266 mm  = prefix[331] - prefix[300]
100,000 random range queries: up to 36,500,000 additions one by one, 100,365 operations with the prefix array

Each answer is checked against adding up the range directly. The last line puts the saving in numbers: 100,000 questions would cost up to 36.5 million additions one by one, against 100,365 operations with the prefix array. Python can build the array in one call, list(itertools.accumulate(rain_mm, initial=0)); the loop shows what that call does.

The zero in front and half-open ranges

The leading 0 is what keeps the formula free of special cases. With it, prefix[i] is the total of the half-open range a[0:i], the first i items, and a range that starts at day 0 is simply prefix[last + 1] − prefix[0]. Without it, the array would hold the totals of a[0..i], and a range starting at 0 would need prefix[−1], which Python does not reject: it quietly reads the last entry and returns a wrong answer. Thinking in half-open ranges, start included and end excluded, removes the other classic slip: the total of a[first..last] uses last + 1.

Many range updates with a difference array

Now turn the problem round. A hall has 8 seats, bookings reserve ranges of seats, and at the end you need the number of bookings covering each seat. Adding 1 to every seat of every booking costs as much as the bookings are long. Difference arrays record each booking with two marks instead:

"""Applies range bookings to seats with a difference array, then checks the result against doing them one by one.

A booking (first, last) adds 1 to every seat from first to last. The difference array records only its two ends:
+1 at first and -1 just after last. One prefix sum over the marks then gives every seat's count.
"""

SEATS = 8
bookings = [(1, 4), (3, 6), (0, 7), (5, 5)]

diff = [0] * (SEATS + 1)  # one extra slot, so that last + 1 is always a valid index
for first, last in bookings:
    diff[first] += 1
    diff[last + 1] -= 1
    print(f"booking seats {first} to {last}: marks {diff[:SEATS]} (and {diff[SEATS]} past the end)")

count, running = [], 0
for i in range(SEATS):
    running += diff[i]
    count.append(running)
print("prefix sum of the marks:", count)

one_by_one = [0] * SEATS
for first, last in bookings:
    for seat in range(first, last + 1):
        one_by_one[seat] += 1
print("the same, seat by seat: ", one_by_one)

booking seats 1 to 4: marks [0, 1, 0, 0, 0, -1, 0, 0] (and 0 past the end)
booking seats 3 to 6: marks [0, 1, 0, 1, 0, -1, 0, -1] (and 0 past the end)
booking seats 0 to 7: marks [1, 1, 0, 1, 0, -1, 0, -1] (and -1 past the end)
booking seats 5 to 5: marks [1, 1, 0, 1, 0, 0, -1, -1] (and -1 past the end)
prefix sum of the marks: [1, 2, 2, 3, 3, 3, 2, 1]
the same, seat by seat:  [1, 2, 2, 3, 3, 3, 2, 1]

A booking from first to last adds 1 at diff[first] and subtracts 1 at diff[last + 1], which is why the array has one slot more than there are seats. The running total of the marks rises by 1 where a booking starts and falls by 1 just after it ends, so at every seat it equals the number of bookings covering it, exactly as the seat-by-seat check shows. Recording a booking costs two additions however long it is; reading the result costs one pass.

Prefix sums or difference arrays?

The two are inverses: the running total of a difference array gives the values back, and the differences of neighbouring prefix entries give the original items back. Which one to keep depends on whether the data is mostly asked about or mostly changed.

Three extensions build on the same idea. On a grid, the total of any rectangle comes from four corner values of a two-dimensional prefix table. Totals need a type wide enough for the largest one: 100,000 values of up to 10⁹ add up to 10¹⁴, beyond any 32-bit integer. When updates and queries arrive mixed together, a Fenwick tree gives both in O(log n).

Exercise

A payments dashboard asks the total of many date ranges over daily figures. The starter code is correct and far too slow; one prefix array fixes it.

def range_totals(payments, queries):
    """The total of payments[first..last], both included, for each (first, last) in queries."""
    # This adds up every range again: correct, but O(n) per question.
    return [sum(payments[first : last + 1]) for first, last in queries]

import random

from range_totals import range_totals


def test_small():
    """totals of a few ranges of a week, single days included"""
    week = [120, 0, 75, 300, 0, 45, 210]
    assert range_totals(week, [(0, 6), (1, 3), (4, 4), (6, 6), (0, 0)]) == [750, 375, 0, 210, 120]


def test_no_queries():
    """no questions give an empty list"""
    assert range_totals([5, 6], []) == []


def test_large_values():
    """totals beyond 2**31 come out exact"""
    payments = [1_000_000_000] * 5
    assert range_totals(payments, [(0, 4), (2, 3)]) == [5_000_000_000, 2_000_000_000]


def test_many_questions():
    """200,000 questions about 200,000 days finish in time and match a running total"""
    rng = random.Random(2)
    n = 200_000
    payments = [rng.randrange(0, 1_000_000_001) for _ in range(n)]
    queries = []
    for _ in range(200_000):
        first = rng.randrange(n // 4)
        queries.append((first, rng.randrange(n - n // 4, n)))
    totals = range_totals(payments, queries)
    running = [0]
    for p in payments:
        running.append(running[-1] + p)
    assert totals == [running[last + 1] - running[first] for first, last in queries]

/** The total of payments[first..last], both included, for each [first, last] in queries. */
export function rangeTotals(payments, queries) {
  // This adds up every range again: correct, but O(n) per question.
  return queries.map(([first, last]) => {
    let total = 0;
    for (let day = first; day <= last; day++) total += payments[day];
    return total;
  });
}

import { test, assert } from 'mysmartcopilot:test';
import { rangeTotals } from './range_totals.mjs';

test('totals of a few ranges of a week, single days included', () => {
  const week = [120, 0, 75, 300, 0, 45, 210];
  assert.deepEqual(rangeTotals(week, [[0, 6], [1, 3], [4, 4], [6, 6], [0, 0]]), [750, 375, 0, 210, 120]);
});

test('no questions give an empty list', () => assert.deepEqual(rangeTotals([5, 6], []), []));

test('totals beyond 2**31 come out exact', () => {
  assert.deepEqual(rangeTotals([1e9, 1e9, 1e9, 1e9, 1e9], [[0, 4], [2, 3]]), [5e9, 2e9]);
});

test('200,000 questions about 200,000 days finish in time and match a running total', () => {
  let x = 2;
  const next = (bound) => (x = (x * 48271) % 2147483647) % bound;
  const n = 200000;
  const payments = Array.from({ length: n }, () => next(1000000001));
  const queries = Array.from({ length: 200000 }, () => [next(n / 4), n - n / 4 + next(n / 4)]);
  const totals = rangeTotals(payments, queries);
  const running = [0];
  for (const p of payments) running.push(running[running.length - 1] + p);
  assert.deepEqual(totals, queries.map(([first, last]) => running[last + 1] - running[first]));
});

Grids: two-dimensional prefix sums and difference grids, worked Pro: opens with a Pro, Premium or Ultimate pass

64-bit totals, five languages and measured speed Pro: opens with a Pro, Premium or Ultimate pass

Beyond sums and fixed data: counts, XOR and changing arrays Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• Prefix sums turn range totals into one subtraction: prefix[last + 1] − prefix[first], after O(n) work once.
• Keep prefix[0] = 0 and think in half-open ranges; the off-by-one slips disappear.
• Difference arrays record a range update as two marks; one running total applies them all, O(n + q).
• Prefix sums suit fixed data with many questions; difference arrays suit many updates read once at the end.