THE DIFFERENCE ARRAY — a dart

THE DIFFERENCE ARRAY add to a whole range by touching two cells — the inverse of the prefix sum

The difference array is the prefix sum run backwards, and it makes range updates cheap the way prefix sums make range queries cheap. To add v to every element in [i..j], you touch just two cells of the difference array: d[i] += v and d[j+1] −= v. Apply as many range updates as you like — each is O(1) — then a single prefix-sum pass reconstructs the final array. A correct naive updater walks the whole range every time (O(range) each); the difference array defers all of it to one closing integration. It is the discrete derivative, and the imos method of competitive programming.

THE TECHNIQUE range +v: d[i]+=v, d[j+1]−=v; integrate once at the end

A range update on a zero array. The demo marks two cells and integrates to read the updated value: live demo

HISTORY & CREDIT the difference array / imos method

“Adding to a range means writing every cell in it.” — the difference array marks the two endpoints and defers the work to one final integration; a hundred range updates cost two cells each. cited

inverse of scan · the difference operator d[k]=a[k]−a[k−1], undone by the prefix sum.
the trick · range-add becomes two point-writes; the “imos method” in competitive programming.
2D · four corner-marks add to a rectangle, integrated twice — the companion of the summed-area table.
now · batched range updates, sweep-line accumulation, difference-of-Gaussians in vision.

Two marks stand in for a whole range; the sum at the end makes them real. The discrete derivative, deferred and then integrated. difference array

RECOMMEND FOR I-13 the O(1) range update, on the compiler

On the canonical compiler, adding +2 across positions 1..3 via marks d[1]+=2, d[4]−=2 then integrating gives value 2 at position 2:

$ i13 run op_diffarray.i13 # d=[0,2,0,0,-2]; integrate to index 2 RUN OK · 71 step(s) · peak stack 7 · call depth 4 value_at_2 = 2 -- range +2 applied by touching two cells, read by one pass

Recommend: the difference array is the prefix sum's mirror twin — cheap range updates to match cheap range queries — and the pairing is a small A↔Z palindrome inside the batch (integral and derivative, dart 322 & 323). i13 applies +2 over a range by two writes and reads back 2. The supplement to correctness: a correct updater writes every cell in the range; this writes two and defers the rest to one integration. A witness of the derivative↔integral duality rather than a keeper, but it closes the query/update pair cleanly.