Why do two O(1) writes to a difference array record an increment across a whole index range?
answer
- think about storing gaps, not values
- what does a running total do after a bump
- one mark opens the range, one closes it
- the closing mark sits one past the end
- range increment = two suffix increments
basics
~20 sA difference array stores the gap between neighbouring entries. Adding v at index l and subtracting v at index r+1 raises the running total by v for exactly positions l through r, and one prefix pass turns those two marks back into real values.
solid answer
~40 sA difference array `diff` holds the gap between consecutive entries of the target array, so the real value at index `i` is the running total `diff[0] + ... + diff[i]`. Adding `v` at `l` lifts every running total from `l` onward by `v`; subtracting `v` at `r+1` cancels that lift from `r+1` onward. The net effect is exactly `+v` on `l..r`, paid for with two constant-time writes. Nothing in the real array has changed yet — you pay one O(n) prefix pass at the end that materializes every recorded update at once. For `m` batched adjustments over `n` shelf positions in a warehouse count array that is O(m + n) work, instead of the O(m·n) you get from looping over each range and touching every position it covers.
go deeper
Be ready to state the two writes and the final prefix pass from memory, and to say why the recorded values are not real until that pass runs.
Explain the telescoping sum that makes the encoding reversible, and derive the O(m + n) total against the O(m·n) of applying each range directly.
Show the judgment that the pattern needs a write phase that closes before the read phase, and name what kind of workload violates that precondition.
Own the call on whether the cleverness is worth it: a two-line loop is obvious to every maintainer, while a deferred-materialize array invites a colleague to read it one refactor too early.
## What a difference array actually stores Given a target array `a` of length `n`, its difference array `diff` stores gaps rather than values: ``` diff[0] = a[0] diff[i] = a[i] - a[i-1] for i >= 1 ``` That encoding is losslessly reversible: the running total of `diff` up to index `i` telescopes back to `a[i]`, because `(a[0]) + (a[1]-a[0]) + (a[2]-a[1]) + ... + (a[i]-a[i-1])` cancels everything but `a[i]`. So a single left-to-right pass carrying one accumulator reconstructs the whole array in O(n) time and O(1) extra space beyond the output. In interview problems you rarely build `diff` from an existing array. You start with an all-zero `diff` representing an all-zero target, record a pile of range increments into it, and materialize once. ## Why two writes are enough The accumulator is a running sum, so anything you add at position `l` is carried forward through every later index. That one write already performs "add `v` to every index from `l` to the end" — a suffix increment. The second write, `diff[r+1] -= v`, injects the opposite suffix increment starting one position later. The two suffixes overlap everywhere except `l..r`, and where they overlap they cancel exactly: | index range | contribution of `+v` at `l` | contribution of `-v` at `r+1` | net | |---|---|---|---| | `0 .. l-1` | 0 | 0 | 0 | | `l .. r` | `+v` | 0 | `+v` | | `r+1 .. n-1` | `+v` | `-v` | 0 | That is the whole trick: a range increment is the difference of two suffix increments, and a suffix increment is one write into a running-sum encoding. ## The cost argument Suppose a warehouse system applies `m` batched stock adjustments, each of the form "add `v` units to every shelf position from `l` to `r`", over an array of `n` shelf positions. - **Direct application.** Each adjustment writes to every position it covers. A range can cover the whole aisle, so the worst case is O(m·n). With 200,000 adjustments over 100,000 positions that is up to 2 × 10^10 writes — hopeless. - **Difference array.** Each adjustment is two writes: O(m) total. One materialize pass is O(n). Total O(m + n) — about 500,000 operations for the same input. Space is O(n) for the difference array (plus one slot; see the boundary discussion below), which is the same order as the array you are already holding. Note what the O(1) claim does and does not say. Each *update* is O(1), genuinely and in the worst case — not amortized, not expected. But the *array* is not correct after those updates; correctness is deferred to the prefix pass. The pattern trades read-time freshness for write-time speed. ## When the trick applies Three conditions have to hold: 1. **The updates are range increments** — add the same delta to a contiguous stretch. Range *assignment* ("set every position in `l..r` to `v`") does not decompose into two additive marks, because a later assignment must erase earlier ones rather than accumulate with them. 2. **The deltas compose additively.** Increments commute, so the order in which you record them does not matter and overlapping ranges simply sum. This is why you can record all `m` updates before doing any work. 3. **The reads come after the writes.** The array is only trustworthy once you have run the prefix pass. ## The two classic mistakes The first is closing the range at `r` instead of `r+1`. Writing `diff[r] -= v` cancels the increment one position early, so the last element of every range silently misses its update — a bug that passes small hand-traced examples where `l == r` is never exercised, then fails on real data. The second is forgetting that the closing write can land at index `n`, one past the end, when a range runs to the last position. Either size the difference array `n+1` and ignore the final slot, or guard the write; both are correct, and the extra slot is never read by a materialize pass that stops at `n-1`. ## Rebuilding intuition If you ever blank on the signs mid-interview, re-derive rather than recall: write down a five-element zero array, apply "+3 on indices 1..3" by hand, and take successive differences of the result. You get `0, +3, 0, 0, -3` — the `+3` sits at the left endpoint and the `-3` sits at one past the right endpoint, which is exactly the two writes. That thirty-second derivation is more reliable under pressure than a memorized formula, and interviewers notice when a candidate can rebuild a rule instead of reciting it.
- What does the array hold immediately after those two writes, before any prefix pass?Nothing usable as a value array — it holds gaps, not counts. Reading `diff[i]` gives the delta between neighbours, so a caller that reads it directly sees garbage. The recorded updates only become real values after the running-sum pass. That deferral is the price of O(1) updates, and it is why the pattern only fits workloads whose reads come after the write batch closes.
- If two adjustments cover overlapping shelf ranges, do you need to do anything special?No. Increments compose additively, so overlapping ranges just accumulate: each contributes its own `+v` and `-v` marks, and the running sum adds them up wherever they overlap. Order does not matter either, since addition commutes. This is exactly why you can record all `m` updates blindly and materialize once — a property that range *assignment* does not have.
- How would you undo one recorded increment before materializing?Record its negation: `diff[l] -= v` and `diff[r+1] += v`. Because the encoding is additive, an increment and its negation cancel to zero at every index, and the retraction is still two constant-time writes. After materializing, though, undoing is no longer cheap — you would have to re-difference the array first or replay the batch.
It is like flagging a stretch of shelving with a start flag and a stop flag instead of relabelling every shelf: one walk down the aisle carrying a running count applies every flag pair at once.
saying these in an interview costs you the question
- Says the array is correct right after the two writes
- Closes the range at r instead of r+1
- Claims difference arrays speed up reads as well as writes
- Thinks overlapping ranges must be merged first
- Applies the same trick to range assignment, not increment