VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 01: Arrays and strings

Lesson 1.2 of 16 in this moduleFree

Prefix sums: answer range questions in O(1)

Pay O(n) once to answer any range question in O(1): window accuracy from prefix counts, rectangle sums in 2-D with inclusion–exclusion, and the reverse trick, difference arrays, for many range updates. Each from brute force, with the constraint that breaks it.

about 10 min 5 Python examples 3 quick checks

Lesson 0.2 introduced prefix sums for range-sum queries. This lesson turns them into a full tool you can apply to any "how much between here and there?" question: counts instead of sums, two dimensions instead of one, and the mirror-image trick, difference arrays, for when the problem is many range updates instead of many range queries. Each part starts from a brute force, shows the constraint that makes it too slow, and derives the optimisation.


1. The core idea, in one line

Store running totals once: P[k] = a[0] + … + a[k−1], with P[0] = 0. Then any range total is a difference of two running totals:

text
a[l] + … + a[r]  =  P[r + 1] − P[l]

Build: O(n). Each query: O(1). Space: O(n). The trick works for any quantity you can add and subtract: sums, counts, and anything you can encode as 0/1 per element.


2. Counting with prefix sums: accuracy over any window

Problem. A model made n predictions; correct[i] is 1 if prediction i was right, 0 otherwise. Answer q queries "what fraction was correct between positions l and r?"

ML context. Evaluating a model over many time windows (per day, per week, per drift period) from one log of predictions.

Brute force

python
def window_accuracy_brute(correct, queries):
    out = []
    for l, r in queries:
        out.append(sum(correct[l:r + 1]) / (r - l + 1))     # O(r − l) per query
    return out


correct = [1, 0, 1, 1, 0, 0, 1, 1]
assert window_accuracy_brute(correct, [(2, 6), (0, 7)]) == [3 / 5, 5 / 8]
print("brute force works")

Cost: O(n · q) worst case. With 10⁶ predictions and 10⁴ windows that's 10¹⁰: too slow. The constraint that forces the change is many queries over the same data.

Optimised: prefix counts

a 0/1 array of correct predictions and its prefix counts; correct predictions in a[2..6] = P[7] − P[2] = 4 − 1 = 3, so window accuracy is 3/5.
Diagram— a 0/1 array of correct predictions and its prefix counts; correct predictions in a[2..6] = P[7] − P[2] = 4 − 1 = 3, so window accuracy is 3/5.
python
from itertools import accumulate


def window_accuracy_prefix(correct, queries):
    P = [0, *accumulate(correct)]                         # O(n) once
    return [(P[r + 1] - P[l]) / (r - l + 1) for l, r in queries]   # O(1) each


import random

rng = random.Random(2)
correct = [rng.randint(0, 1) for _ in range(500)]
queries = [(l, rng.randint(l, 499)) for l in (rng.randint(0, 499) for _ in range(300))]
fast = window_accuracy_prefix(correct, queries)
slow = [sum(correct[l:r + 1]) / (r - l + 1) for l, r in queries]
assert all(abs(a - b) < 1e-12 for a, b in zip(fast, slow))
print("prefix counts agree with brute force")

Cost: O(n + q) time, O(n) space.

Quick check

You want the number of times the label 'spam' appears in any range of a long label list. How do prefix sums apply?

  1. They don't; prefix sums only work on numbers
  2. Convert each label to 1 if it's 'spam' else 0, prefix-sum those indicators, and each range count is a difference of two prefix values
  3. Sort the labels first
  4. Use a set of positions
Show the answer

B. Convert each label to 1 if it's 'spam' else 0, prefix-sum those indicators, and each range count is a difference of two prefix values — Any per-element property becomes countable once encoded as 0/1, and counts add and subtract like sums.


3. Two dimensions: rectangle sums

Problem. Given an R × C grid of numbers (an image, an attention map, a heat map of activity), answer q queries: the sum inside a rectangle with rows r1..r2 and columns c1..c2.

ML context. Classic face detectors computed box features over images in constant time with exactly this structure (an "integral image"); today the same idea gives fast region statistics over activation or attention maps.

Brute force

Loop over every cell in the rectangle: O(area) per query, O(R · C · q) worst case. A 1000 × 1000 image with 10⁴ queries is 10¹⁰ operations.

First principles: extend running totals to 2-D

Let S[r][c] be the sum of everything above and to the left of (r, c) (exclusive), so S has one extra row and column of zeros. Then a rectangle is the big top-left block, minus the strip above it, minus the strip to its left, plus the corner that was subtracted twice:

text
rect(r1..r2, c1..c2) = S[r2+1][c2+1] − S[r1][c2+1] − S[r2+1][c1] + S[r1][c1]
a grid with a green query rectangle, blue strips above and to its left that are subtracted, and an amber corner subtracted twice and added back; any rectangle sum costs four lookups.
Diagram— a grid with a green query rectangle, blue strips above and to its left that are subtracted, and an amber corner subtracted twice and added back; any rectangle sum costs four lookups.

Building S uses the same inclusion–exclusion: S[r+1][c+1] = grid[r][c] + S[r][c+1] + S[r+1][c] − S[r][c].

python
import random


def build_2d_prefix(grid):
    R, C = len(grid), len(grid[0])
    S = [[0] * (C + 1) for _ in range(R + 1)]
    for r in range(R):
        for c in range(C):
            S[r + 1][c + 1] = grid[r][c] + S[r][c + 1] + S[r + 1][c] - S[r][c]
    return S


def rect_sum(S, r1, c1, r2, c2):
    return S[r2 + 1][c2 + 1] - S[r1][c2 + 1] - S[r2 + 1][c1] + S[r1][c1]


def rect_sum_brute(grid, r1, c1, r2, c2):
    return sum(grid[r][c] for r in range(r1, r2 + 1) for c in range(c1, c2 + 1))


rng = random.Random(3)
for _ in range(100):
    R, C = rng.randint(1, 12), rng.randint(1, 12)
    grid = [[rng.randint(-9, 9) for _ in range(C)] for _ in range(R)]
    S = build_2d_prefix(grid)
    for _ in range(30):
        r1, r2 = sorted(rng.randrange(R) for _ in range(2))
        c1, c2 = sorted(rng.randrange(C) for _ in range(2))
        assert rect_sum(S, r1, c1, r2, c2) == rect_sum_brute(grid, r1, c1, r2, c2)
print("2-D prefix sums agree with brute force")

Cost: O(R · C) to build, O(1) per query, O(R · C) space.


4. The reverse problem: many range updates, then read everything

Problem. Start with n zeros. Apply q updates "add v to every position from l to r". Then return the final array.

ML context. Given many user sessions as (start minute, end minute), count how many sessions are active in each minute: each session is a +1 range update. The same shape appears when marking token spans for labels, or summing overlapping GPU reservations per hour.

Brute force

python
def apply_updates_brute(n, updates):
    a = [0] * n
    for l, r, v in updates:
        for i in range(l, r + 1):        # O(r − l) per update
            a[i] += v
    return a


assert apply_updates_brute(6, [(1, 3, 5), (2, 5, 2)]) == [0, 5, 7, 7, 2, 2]
print("brute force works")

Cost: O(n · q) worst case. 10⁵ sessions spanning a 10⁶-minute timeline would be 10¹¹ steps.

First principles: record only where things change

A range update changes the array's differences in just two places: at l the value jumps up by v, and just after r it drops back by v. So record those two edges in a difference array D, then one prefix sum over D rebuilds the values. (This is prefix sums run backwards.)

updates +5 on [1..3] and +2 on [2..5] become marks D = [0, 5, 2, 0, −5, 0, −2]; one prefix sum over D gives the final values [0, 5, 7, 7, 2, 2].
Diagram— updates +5 on [1..3] and +2 on [2..5] become marks D = [0, 5, 2, 0, −5, 0, −2]; one prefix sum over D gives the final values [0, 5, 7, 7, 2, 2].
python
import random
from itertools import accumulate


def apply_updates_diff(n, updates):
    D = [0] * (n + 1)                      # one extra slot so r + 1 is always valid
    for l, r, v in updates:
        D[l] += v                          # the value steps up at l
        D[r + 1] -= v                      # and steps back down after r
    return list(accumulate(D))[:n]         # one O(n) sweep rebuilds every value


def apply_updates_brute(n, updates):
    a = [0] * n
    for l, r, v in updates:
        for i in range(l, r + 1):
            a[i] += v
    return a


assert apply_updates_diff(6, [(1, 3, 5), (2, 5, 2)]) == [0, 5, 7, 7, 2, 2]
rng = random.Random(4)
for _ in range(300):
    n = rng.randint(1, 30)
    ups = []
    for _ in range(rng.randint(0, 20)):
        l = rng.randrange(n)
        ups.append((l, rng.randrange(l, n), rng.randint(-5, 5)))
    assert apply_updates_diff(n, ups) == apply_updates_brute(n, ups)
print("difference array agrees with brute force: O(n + q)")

Cost: O(1) per update, O(n) for the final sweep: O(n + q) total, O(n) space.

Quick check

Each of 10⁵ user sessions is a (start, end) minute range on a 10⁶-minute timeline. You need the number of active sessions in every minute. What's the efficient approach?

  1. For each minute, scan all sessions: O(minutes × sessions)
  2. For each session, add 1 to every minute it covers: O(total session length)
  3. Difference array: +1 at start, −1 after end, then one prefix sweep: O(minutes + sessions)
  4. Sort the sessions and binary search each minute
Show the answer

C. Difference array: +1 at start, −1 after end, then one prefix sweep: O(minutes + sessions) — Each range update becomes two O(1) marks; one sweep turns the marks into counts.


5. When the constraints change

Prefix sums and difference arrays both rely on the data being fixed while you query (or all updates arriving before any reads). Break that, and you need something else.

If the constraint becomes… Best approach Update Query
One query Brute force — O(n)
Many queries, fixed data Prefix sums O(n) rebuild O(1)
Many range updates, then read all Difference array O(1) O(n) once
Point updates mixed with range queries Fenwick tree O(log n) O(log n)
Range updates mixed with range queries Segment tree with lazy updates O(log n) O(log n)
2-D grid, fixed 2-D prefix sums O(R·C) rebuild O(1)
Range min/max instead of sum Sparse table (static) or segment tree — O(1) / O(log n)
Floats over very long arrays Prefix sums with care (rounding drift) — O(1)

Two rows deserve a sentence each:

  • Min/max: prefix sums need subtraction to "remove" the part before l. There's no subtraction for min or max, so prefix sums can't answer range-minimum queries. (Same lesson as rolling max in lesson 1.1.)
  • Floats: summing 10⁸ floats into one running total accumulates rounding error, so P[r+1] − P[l] can be visibly off for short ranges deep into the array. Use 64-bit floats, or compensated (Kahan) summation, or recompute short ranges directly.

Quick check

Why can't prefix sums answer 'minimum value between l and r' in O(1)?

  1. Prefix sums work by subtracting the part before l, and there's no operation that 'subtracts' a minimum; you need a structure like a sparse table or segment tree
  2. Minimums are too slow to compute
  3. They can, using P[r+1] − P[l]
  4. Only if the array is sorted
Show the answer

A. Prefix sums work by subtracting the part before l, and there's no operation that 'subtracts' a minimum; you need a structure like a sparse table or segment tree — The trick depends on an inverse operation. Sums have subtraction; min and max don't.


6. Preview: prefix sums plus a hash map

One more combination appears constantly in interviews: "count subarrays whose sum is exactly k". A subarray l..r sums to k exactly when P[r+1] − P[l] = k, that is, when an earlier prefix equals P[r+1] − k. Counting earlier prefixes in a hash map turns an O(n²) search into O(n). That's lesson 2.8 (Subarray Sum Equals K); it's the complement idea from Two Sum, applied to prefix sums.


7. Saying it out loud

"Brute force sums each range: O(n · q). Ranges overlap, so I precompute running totals once in O(n), and each query is a difference of two of them, O(1). In 2-D the same idea needs inclusion–exclusion: four lookups. If the problem were many range updates before reading, I'd flip it to a difference array: two marks per update and one sweep, O(n

  • q). If updates and queries interleave, I'd switch to a Fenwick or segment tree at O(log n) each."

Check yourself

  1. Write the formula for a range sum using prefix sums, and say what makes it work.
  2. How do prefix sums count things that aren't numbers?
  3. Derive the 2-D rectangle formula from inclusion–exclusion.
  4. What does a difference array record, and how does it rebuild the final values?
  5. Which constraint breaks prefix sums, and what replaces them?
  6. Why can't prefix sums answer range minimums?
Answers
  1. sum(a[l..r]) = P[r+1] − P[l]; it works because sums can be subtracted to remove the prefix before l.
  2. Encode each element as 0/1 for the property, then prefix-sum the indicators.
  3. Take the block above-left of the bottom-right corner, subtract the strip above and the strip to the left, then add back the top-left corner that was subtracted twice.
  4. Only the edges of each update (+v at l, −v after r); a prefix sum over those marks gives every position's total.
  5. Updates interleaved with queries; a Fenwick tree (point updates) or a segment tree (range updates) keeps both at O(log n).
  6. There's no inverse for min, so you can't remove the part before l.