Difference Array
Adding v to a whole range is two writes if you only record where the change starts and where it stops. A prefix pass at the end turns those deltas back into values, and every update lands on exactly its range because its +v and -v cancel outside it.
Add amounts to 2 rectangles of a 4 x 6 grid of zeros without touching every cell. Each rectangle becomes four corner marks in a difference grid: a start at its top-left, stops past its right edge and below its bottom edge, and a restart where those two stops would cancel twice. A prefix pass along rows and then down columns turns the marks back into the rectangles. The extra stop row and column catch edges at the border.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 2, with their answers.
Add +5 to rows 0-2, columns 1-3. Which cells of the difference grid change?
Answer: (0,1) +5, (0,4) -5, (3,1) -5, (3,4) +5. Four corners: start, two stops, and a restart where the stops overlap.
Add +2 to rows 1-3, columns 2-5. Which cells of the difference grid change?
Answer: (1,2) +2, (1,6) -2, (4,2) -2, (4,6) +2. Four corners: start, two stops, and a restart where the stops overlap.
How it runs, step by step
Add amounts to 2 rectangles of a 4 x 6 grid of zeros without touching every cell. Each rectangle becomes four corner marks in a difference grid: a start at its top-left, stops past its right edge and below its bottom edge, and a restart where those two stops would cancel twice. A prefix pass along rows and then down columns turns the marks back into the rectangles. The extra stop row and column catch edges at the border.
A 5 by 7 difference grid, all zero.
Rectangle rows 0 to 2, columns 1 to 3, +5. Four writes: +5 at (0,1) starts it; -5 at (0,4) stops it past the right edge; -5 at (3,1) stops it below the bottom; +5 at (3,4) cancels the corner that both stops would hit.
Rectangle 1: four corner writes.
Rectangle rows 1 to 3, columns 2 to 5, +2. Four writes: +2 at (1,2) starts it; -2 at (1,6) stops it past the right edge; -2 at (4,2) stops it below the bottom; +2 at (4,6) cancels the corner that both stops would hit.
Rectangle 2: four corner writes.
Row 0, prefix along the row: each cell adds the one to its left, so a start spreads right until its stop cancels it. Row 0 is now 0, 5, 5, 5, 0, 0.
Row 0 prefixed.
Row 1, prefix along the row: each cell adds the one to its left, so a start spreads right until its stop cancels it. Row 1 is now 0, 0, 2, 2, 2, 2.
Row 1 prefixed.
Row 2, prefix along the row: each cell adds the one to its left, so a start spreads right until its stop cancels it. Row 2 is now 0, 0, 0, 0, 0, 0.
Row 2 prefixed.
Row 3, prefix along the row: each cell adds the one to its left, so a start spreads right until its stop cancels it. Row 3 is now 0, -5, -5, -5, 0, 0.
Row 3 prefixed.
Row 4, prefix along the row: each cell adds the one to its left, so a start spreads right until its stop cancels it. Row 4 is now 0, 0, -2, -2, -2, -2.
Row 4 prefixed.
Column 0, prefix down the column: each cell adds the one above, so a row's spread continues down until the stop row cancels it. Column 0 is now 0, 0, 0, 0.
Column 0 prefixed.
Column 1, prefix down the column: each cell adds the one above, so a row's spread continues down until the stop row cancels it. Column 1 is now 5, 5, 5, 0.
Column 1 prefixed.
Column 2, prefix down the column: each cell adds the one above, so a row's spread continues down until the stop row cancels it. Column 2 is now 5, 7, 7, 2.
Column 2 prefixed.
Column 3, prefix down the column: each cell adds the one above, so a row's spread continues down until the stop row cancels it. Column 3 is now 5, 7, 7, 2.
Column 3 prefixed.
Column 4, prefix down the column: each cell adds the one above, so a row's spread continues down until the stop row cancels it. Column 4 is now 0, 2, 2, 2.
Column 4 prefixed.
Column 5, prefix down the column: each cell adds the one above, so a row's spread continues down until the stop row cancels it. Column 5 is now 0, 2, 2, 2.
Column 5 prefixed.
Column 6, prefix down the column: each cell adds the one above, so a row's spread continues down until the stop row cancels it. Column 6 is now 0, 0, 0, 0.
Column 6 prefixed.
The top-left 4 x 6 block holds every rectangle's sum. 2 rectangles cost 4 writes each plus one pass over the grid, O(k + R x C), instead of O(k x R x C) for filling each rectangle cell by cell.
Final grid computed.
Remember
- A range add is +v at l and -v at r + 1. Nothing in between is touched.
- One prefix pass at the end applies every update at once, so k updates cost O(n + k), not O(n * k).
- Reach for it when many range updates come before a single read. It does not help if reads and updates interleave.
Topics covered
Where this is used
GraphicsGlyph rasterization in font-rs
font-rs draws a glyph by adding small signed area deltas into one flat float buffer wherever an outline segment crosses a pixel, and it never writes to the pixels in between that the fill will cover. A single prefix pass over the whole buffer, the accumulate step, turns those deltas into the coverage of every pixel at once. The work therefore tracks the length of the outline plus the size of the bitmap, not the area being filled, which is why a large solid glyph costs no more per pixel than a thin one.
BioinformaticsRead depth from aligned intervals
bedtools genomecov turns hundreds of millions of aligned read intervals into a per-base coverage track. Each read contributes one +1 where it starts and one -1 that takes effect just past where it ends, so the cost per read is constant no matter how long the read is, and one sweep along the chromosome yields the depth at every base. Incrementing each read's bases one at a time would multiply the entire job by the read length.
DatabasesDelta encoding in Parquet columns
Parquet's DELTA_BINARY_PACKED encoding stores an INT32 or INT64 column as its difference array: one starting value, then the gap to each following value. Timestamps and generated ids move in small, similar steps, so those gaps bit-pack into a few bits each where the raw values need 32 or 64, and the reader rebuilds the column by running the sum forward one element at a time. The cost is that no value can be recovered without every gap ahead of it, so these pages are decoded in whole blocks rather than seeked into.
HardwareIntegrator and comb stages in CIC filters
A cascaded integrator-comb filter, used in sigma-delta converters and software-defined radio front ends, pairs integrator stages that hold a running sum with comb stages that subtract the sample M steps back. The comb is the difference operator the running sum undoes, so the pair cancels everything except the last M terms and leaves a sliding sum of M samples for a couple of additions per sample and no multiplier at all. That is what makes it affordable at the raw converter rate, where a filter with a multiply per tap would not fit in the gate budget.
Why it works this way
Why the array has one slot more than the data
A range that ends at the last index writes its -v at index n, which is off the end of an n-slot array. The extra slot exists purely to absorb that closing delta: nothing ever reads it, and the prefix pass stops before it. You could instead skip the -v whenever r is the last index, but that puts a branch in every update for no gain, and forgetting it is the usual way this code crashes on its first real input.
Where the fourth corner in the 2D version comes from
diff[r1][c1] += v and diff[r1][c2 + 1] -= v open and close the update horizontally, but after both prefix passes they apply to every row from r1 downward, not just to r1 through r2. The pair written at row r2 + 1 cancels them from that row on. The last corner, diff[r2 + 1][c2 + 1], is +v because that cell has now been subtracted twice, once by the row close and once by the column close, so one v has to go back. It is inclusion-exclusion, the same four-corner arithmetic a summed-area table uses to read a rectangle.
It works for add, and not for assign
The prefix pass has no idea which update was recorded first; it just totals whatever deltas landed in each slot. That is fine for addition, which commutes, and it is why the updates can arrive in any order, or be built by separate workers whose diff arrays you add element-wise at the end. Setting a range to a value does not commute - two overlapping assignments give different answers depending on which ran last - so no pair of deltas can encode one. Range assign needs a segment tree with lazy propagation instead.
If a read has to land in the middle of the updates
The prefix pass is O(n), so re-running it after every update is worse than just looping over each range naively. Keep the two-delta idea but store the difference array in a Fenwick tree: a range add is still two point updates, and reading one element becomes a prefix sum in O(log n) rather than O(n).
Read more
- More on Prefix SumsUSACO Guide
- Fenwick tree: range update, point querycp-algorithms
- Delta encodingWikipedia
- Range Update QueriesCSES 1651 · cses.fi
- font-rs, the accumulation buffer rasterizerGitHub