Prefix Sum

01 / The shared mechanism

Pay O(N) once to build a cumulative table — every range query that follows reduces to a constant-time subtraction. Flip the trick inside-out and you get cheap range updates instead.

01 / The one-sentence essence

Record each range update as a +val at l and a −val at r+1, then sweep once — every interval, no matter how wide, costs O(1) to apply.

Problemmany range-add updates, then read everythingn8updates(1,4,+3) (2,6,+2) (0,3,-1)

diff

final

Empty diff of length 9 on top, empty final of length 8 below. We will apply 3 range updates, then prefix-scan.

step

0 / 17

phase

update

running

0 / 17

u1lrval

u2lrval

u3lrval

u4lrval

02 / The pattern signature

# update: add val to arr[l..r] in O(1)diff[l] ← diff[l] + valdiff[r+1] ← diff[r+1] − val# finalize: prefix-scan to recover the full arrayfinal[0] ← diff[0]for i in 1..n−1:final[i] ← final[i−1] + diff[i]# diff has length n+1 so r+1 is always a legal index

03 / When to recognize this pattern

"add val to arr[l..r]"

The literal canonical signal. The reads come after all the writes — never interleaved. Update many times, read once.

"bookings / passengers / events"

Each booking adds a count over a span, each event toggles a window. The shape is (start, end, delta) — that's the difference-array shape.

"sweep line on integers"

When endpoints are small enough to index directly, the difference array is just a sweep line without the sort.

"final array after k updates"

The pattern only pays off when update count ≥ 2. A single update is no faster than writing the slice directly. The amortization is over the updates.

04 / Common pitfalls

Forgetting the −val at r+1.

Both touches matter: +val at l turns the increment on, −val at r+1 turns it off. Skip the second and the addition leaks past the range — every cell to the right ends up +val too high.

ii.

Off-by-one at the right boundary.

The closer is at r+1, not r. Size the diff array as n + 1 so r+1 = n is a legal index; trim that trailing cell after the prefix scan.

iii.

Reading mid-stream.

Before the finalize pass, diff is not the array — it's the deltas. Querying any arr[i] in the middle of the updates is wrong; either finalize first, or use a Fenwick tree for interleaved updates and queries.

05 / Go practice — on LeetCode

Four problems, ordered by difficulty. No solutions here, by design.

01Maximum Population Year— LC 1854easy→02Corporate Flight Bookings— LC 1109medium→03Car Pooling— LC 1094medium→04Shifting Letters II— LC 2381medium→

— / When to use which

1-D linear

Use when you have many range-sum queries on a fixed array.

range-sum · running-total · LC 303

2-D grid

Use for rectangle queries on a matrix — inclusion-exclusion on the corners.

matrix-region · block-sum · LC 304

difference

Flip the direction: many range updates, then a single read of every cell.

range-add · car-pooling · flight-bookings

hash map

Count subarrays whose sum hits a target — prefix + map of seen prefixes.

subarray-sum-k · divisible-by-k · LC 560