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.
Apply 3 range updates to an array of 8 zeros. Instead of touching every index in each range, record where the change starts and where it stops. The extra slot 8 catches changes that run to the end.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.
Add 5 to indices 1 to 3. Which slots change?
Answer: 1 and 4. Only the endpoints: the change starts at 1 and must stop after 3, so the cancelling delta goes at 4.
Add 2 to indices 2 to 6. Which slots change?
Answer: 2 and 7. Only the endpoints: the change starts at 2 and must stop after 6, so the cancelling delta goes at 7.
Add -3 to indices 0 to 4. Which slots change?
Answer: 0 and 5. Only the endpoints: the change starts at 0 and must stop after 4, so the cancelling delta goes at 5.
How it runs, step by step
Apply 3 range updates to an array of 8 zeros. Instead of touching every index in each range, record where the change starts and where it stops. The extra slot 8 catches changes that run to the end.
A difference array of 8 plus one slots, all zero. Applying 3 range updates by recording only the endpoints.
Update 1: add 5 to indices 1 to 3. Two writes: +5 at 1, where it starts, and -5 at 4, where it stops. The 2 cells between them are never touched.
Add 5 to indices 1 through 3 by writing +5 at slot 1 and -5 at slot 4.
Update 2: add 2 to indices 2 to 6. Two writes: +2 at 2, where it starts, and -2 at 7, where it stops. The 4 cells between them are never touched.
Add 2 to indices 2 through 6 by writing +2 at slot 2 and -2 at slot 7.
Update 3: add -3 to indices 0 to 4. Two writes: -3 at 0, where it starts, and +3 at 5, where it stops. The 4 cells between them are never touched.
Add -3 to indices 0 through 4 by writing -3 at slot 0 and +3 at slot 5.
All 3 updates recorded with 6 writes. Now one prefix pass: each cell becomes the running sum of the deltas so far, which is exactly the updates covering that index.
All updates are recorded. A prefix sum pass now turns the deltas into final values.
Index 0: delta -3. Running sum 0 -3 = -3, which is the final value at 0.
Index 0 becomes -3.
Index 1: delta +5. Running sum -3 +5 = 2, which is the final value at 1.
Index 1 becomes 2.
Index 2: delta +2. Running sum 2 +2 = 4, which is the final value at 2.
Index 2 becomes 4.
Index 3: no delta here, so the running sum stays 4 and that is the value.
Index 3 becomes 4.
Index 4: delta -5. Running sum 4 -5 = -1, which is the final value at 4.
Index 4 becomes -1.
Index 5: delta +3. Running sum -1 +3 = 2, which is the final value at 5.
Index 5 becomes 2.
Index 6: no delta here, so the running sum stays 2 and that is the value.
Index 6 becomes 2.
Index 7: delta -2. Running sum 2 -2 = 0, which is the final value at 7.
Index 7 becomes 0.
Final array: -3, 2, 4, 4, -1, 2, 2, 0. The slot at 8 is only ever a place for deltas to stop. 3 updates cost 2 writes each plus one pass of 8, instead of walking every range.
The final values are -3, 2, 4, 4, -1, 2, 2, 0. Each update cost two writes plus one shared pass.
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