PrefixAlgorithmaka range update trick, delta array, imos method, line sweep on an array

Difference Array

Apply many range increments in O(1) each by writing +v at l and −v at r+1, then recover the final array with a single prefix-sum pass.

▶ VisualizePattern: Prefix SumPractice (2)
Progress

Overview

A difference array is the inverse of a Prefix Sum. Where prefix sums make range queries cheap on a static array, difference arrays make range updates cheap when all updates are known before any query — an *offline* setting. Store D[i] = a[i] − a[i-1]. To add v to every element in a[l..r], set D[l] += v and D[r+1] −= v: two O(1) writes regardless of the range length. After all updates, one prefix-sum pass over D reconstructs a.

This solves "m flight bookings over n flights", "count overlapping intervals at each point", "car pooling capacity", and any problem framed as "for each of m operations, add v to a range; return the final array" in O(n + m) instead of O(n·m).

range updateofflineO(1) updatecontiguoussweep

Intuition

A mental model before the formal terms.

Imagine painting a fence with many overlapping strokes and then asking how many coats each plank has. Rather than touching every plank in every stroke, put a sticky note at the first plank saying "+1 from here on" and another just past the last plank saying "−1 from here on". Afterwards, walk the fence once left to right, keeping a running tally of the notes you have passed. The tally at each plank is its coat count.

How it works

  1. Allocate D of length n + 1 filled with zeros (the extra slot absorbs r + 1 = n).
  2. For each update (l, r, v): D[l] += v, D[r+1] −= v.
  3. After all updates, run a prefix sum: a[0] = D[0], a[i] = a[i-1] + D[i] for i ≥ 1.
  4. If the array had initial values a₀, either start D as the difference of a₀ or add a₀[i] back at the end.
  5. For 2D ranges (add v to a submatrix), place four corner marks +v, −v, −v, +v and run 2D Prefix Sum to reconstruct.

Why it works

Prefix-sum of `D` reproduces `a`: define a[i] = D[0] + … + D[i]. A single update writes +v at l and −v at r+1. For i < l neither mark is included, so a[i] is unchanged. For l ≤ i ≤ r only the +v is included, so a[i] rises by exactly v. For i > r both marks are included and cancel, so a[i] is unchanged. That is precisely "add v to [l, r]".

Updates commute: prefix sum is linear, so the effect of many updates on D is the sum of their individual effects on a. Order of application is irrelevant, which is why the updates can be recorded lazily and resolved in one pass.

Cost: O(1) per update and O(n) for the final pass, so O(n + m) for m updates — versus O(m · avg range length) for direct application.

Recognition

How to tell a problem wants this.

  • "Add `v` to every element in `[l, r]`", "increment a range", "apply m operations then return the array", "bookings", "reservations".
  • "How many intervals cover each point", "maximum number of overlapping meetings/passengers at any moment", "car pooling" — each interval is a +1 at start and −1 at end.
  • The updates are all given up front (offline) and queries come only after them — if updates and queries interleave, you need a Fenwick Tree with range-update support or a Segment Tree with lazy propagation.
  • Constraints n, m ≤ 10^5 where naive range application would be 10^10.
  • Coordinates that are sparse or huge (10^9): use a sorted map of breakpoints (sweep line) instead of a dense array — same idea, compressed.
“sum of subarray” → Prefix Sum“overlapping intervals” → Intervals

Interactive visualization

Play, step, change the input. ← → and space work too.

a
0
0
0
1
0
2
0
3
0
4
0
5
0
6
0
7
D (differences)
0
0
0
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
1/13Apply 3 range increments to the array. Doing each in O(r−l) would be slow, so record only the endpoints in a difference array D of size n+1.
Range being updatedD entry touchedPrefix stepRecovered value
PseudocodeLearn Difference Array →
1D = [0] * (n + 1)
2for each update (l, r, v):
3  D[l] += v; D[r+1] -= v
4a[0] = D[0]; for i in 1..n-1: a[i] = a[i-1] + D[i]
Variables
n8
Complexity
best O(n + m)
avg O(n + m)
worst O(n + m)
space O(n)
Speed

Pseudocode

1D = array of n + 1 zeros
2for (l, r, v) in updates:
3  D[l] += v
4  D[r + 1] -= v
5a[0] = D[0]
6for i in 1..n-1: a[i] = a[i-1] + D[i]
7return a

Implementations

1# Corporate Flight Bookings: bookings[j] = [first, last, seats] (1-based inclusive)
2def corp_flight_bookings(bookings: list[list[int]], n: int) -> list[int]:
31 · Difference array with one extra slot so r + 1 == n stays in bounds
4    d = [0] * (n + 1)
52 · Each booking becomes two O(1) marks: +seats at l, -seats just past r
6    for first, last, seats in bookings:
7        d[first - 1] += seats  # convert 1-based first to 0-based l
8        d[last] -= seats       # (last - 1) + 1 == last
93 · One prefix-sum pass turns the marks into final seat counts
10    out = [0] * n
11    run = 0
12    for i in range(n):
13        run += d[i]
14        out[i] = run
15    return out
Walkthrough
  1. [0] * (n + 1) allocates the sentinel slot; Python lists are zero-filled here by construction.
  2. Tuple unpacking for first, last, seats in bookings names the fields directly in the loop header.
  3. The two marks are O(1) list writes; negative indices would silently wrap in Python, so the 1-based conversion deserves its comment.
  4. The reconstruction accumulates run in a plain loop — clear, and O(1) extra beyond the output.
  5. Python ints cannot overflow, so no width analysis is needed for run.
Complexity (this implementation)
time O(n + m) · space O(n)

itertools.accumulate can replace the final loop; slicing d[:n] first copies O(n) — see the alternative.

Language notes
  • itertools.accumulate is the stdlib prefix-sum; list(accumulate(d[:n])) is the one-liner reconstruction (the slice makes an O(n) copy — fine here, but a real cost in tight loops).
  • Beware negative indices: d[first - 1] with a bad first = 0 input would write to d[-1] (the last slot) instead of raising.
  • For sparse/huge coordinates use a dict of breakpoints plus sorted(marks) — the sweep-line form of the same idea.
Common mistakes in this language
  • Writing d = [0] * n and getting an IndexError (or, with negative indices, silent corruption) at d[last] when last == n.
  • Returning the prefix sums of the whole d including the sentinel — the answer has n entries, not n + 1.
  • Applying each booking with a for i in range(first - 1, last) loop — O(n·m), the exact thing the technique avoids.
Language differences that matter here
  • Zero initialisation: C++ vector<int>(n+1, 0) and Python [0] * (n+1) are zeroed by construction; JS/TS new Array(n+1) has holes until .fill(0) — Int32Array is the zero-by-contract alternative.
  • Out-of-range writes: C++ d[n+1] is undefined behaviour (silent corruption); Python negative indices wrap around instead of failing; JS/TS writing past the end silently grows the array — three different failure modes for the same off-by-one.
  • Overflow of accumulated totals: C++ needs long long when m * max(v) can pass 2^31; JS/TS are exact to 2^53; Python is unbounded.
  • Stdlib reconstruction: Python itertools.accumulate (slicing first copies O(n)); C++ std::partial_sum (accumulates in the input value_type — a widening trap); JS/TS have no scan primitive, so the manual loop is idiomatic.

Complexity

Best
O(n + m)
Average
O(n + m)
Worst
O(n + m)
Space
O(n)

m range updates at O(1) each plus one O(n) reconstruction. Queries are only valid after reconstruction (offline).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Many range increments, all known before the final values are needed.
  • Counting coverage / overlaps of intervals over integer positions.
  • Batch application of operations to an array (bookings, salary raises, sensor calibrations).
  • 2D variant: submatrix increments resolved with a 2D prefix sum.
Avoid it when
  • Updates and queries interleave ("add to range, then query a point, then add again") — reconstruction after each update is O(n); use a Fenwick Tree (range update, point query) or lazy Segment Tree.
  • Updates are not additive (set every element to v, multiply, take max) — a plain difference array only encodes additions; use a segment tree with the right lazy tag.
  • Only a handful of updates over a short array — direct loops are fine and clearer.
  • Coordinates are huge and sparse — use a sorted breakpoint map (sweep line) rather than allocating 10^9 slots.

Alternatives

Prefix SumFenwick TreeSegment TreeMerge Intervals

Common mistakes

  • Allocating D of length n and writing D[r+1] out of bounds when r = n − 1; always allocate n + 1.
  • Placing the −v at r instead of r + 1, which excludes a[r] from the update.
  • Mixing 1-based problem input with 0-based indices — convert once at the boundary and comment it.
  • Querying values before running the reconstruction pass.
  • Forgetting to include the original array's initial values in the result.

Interview patterns

  • Corporate Flight Bookings — the textbook difference array.
  • Car Pooling: +passengers at pickup, −passengers at drop-off; check running total ≤ capacity.
  • Meeting Rooms II via sweep of +1/−1 events (sort events when times are not small integers).
  • Range Addition: apply k updates to a zero array.
  • Number of Flowers in Full Bloom / Points covered by intervals — coverage counts.
  • 2D Range Addition: four corner marks per rectangle plus 2D Prefix Sum.
Interview questions on this
Mock interviews

Example problems

Corporate Flight BookingsmediumMeeting Rooms IImedium