Why is a difference array called the inverse of a prefix sum, and when does that duality pay off?
answer
- one transform undoes the other
- running sums versus successive gaps
- telescoping cancellation in both directions
- which side of the workload is hot
- read-many-write-never versus write-many-read-once
basics
~20 sTaking running sums and taking successive differences undo each other, so either transform recovers the original array. That duality splits the work: prefix arrays make reads cheap and writes useless, difference arrays make range writes cheap and defer all reading to one pass.
solid answer
~50 sFor an array `a`, the prefix transform produces running sums and the difference transform produces gaps between neighbours; applying one to the output of the other returns `a` unchanged, which is what "inverse" means here. The practical consequence is that the two serve mirrored operation profiles. A prefix array is built once and then only read — read-many, write-never — because any change to the source invalidates every prefix entry after it. A difference array is written many times and read once — you record `m` range increments in O(1) each, then spend one O(n) pass to materialize. So when hundreds of date-range shift postings have to become a per-day headcount array, you accumulate marks and materialize once, at O(m + n). Choose by asking which side of the workload is hot: the reads or the range writes.
go deeper
Know that running sums and successive differences reverse each other, and that one transform is aimed at cheap reads while the other is aimed at cheap range writes.
Derive the telescoping cancellation in both directions, and explain why any update makes every later running-sum entry stale.
Classify a real workload by its read-to-range-write ratio before choosing, and say what the bracketing passes cost when you enter and leave the difference representation.
Own the framing that these are specializations, not containers: committing to one shapes the module's API, and a workload whose profile is drifting is a signal to revisit the choice before the constants bite.
## The two transforms For an array `a` of length `n`, define two operations. **Prefix (running sums):** `P[0] = a[0]`, and `P[i] = P[i-1] + a[i]`. **Difference (successive gaps):** `D[0] = a[0]`, and `D[i] = a[i] - a[i-1]`. Apply the difference transform to `P` and you get `P[0] = a[0]` at index 0 and `P[i] - P[i-1] = a[i]` everywhere else — exactly `a` back. Apply the prefix transform to `D` and the sum telescopes: `a[0] + (a[1]-a[0]) + ... + (a[i]-a[i-1]) = a[i]` — again `a` back. Each transform is O(n) and each undoes the other, which is precisely what makes them a dual pair. The calculus analogy is exact enough to be useful: prefix is discrete integration, difference is discrete differentiation, and the telescoping cancellation is the fundamental theorem in miniature. ## Why the duality forces a workload choice Because the transforms are inverses, they push cost to opposite ends of the pipeline. | | prefix array | difference array | |---|---|---| | build | O(n) once | O(1) per recorded update | | range update | invalidates the suffix — effectively O(n) | O(1), two marks | | reading a value | already there | needs the materialize pass | | profile it fits | read-many, write-never | write-many, read-once | A prefix array is a *precomputed answer*. It is fast because the work happened up front, and it is fragile for the same reason: change one source element and every prefix entry from that index onward is stale, so maintaining it under updates costs O(n) per update. A difference array is a *deferred instruction log*. Each range increment is two constant-time marks, so recording is nearly free, and the cost of turning the log into answers is paid exactly once at the end. Neither is a general-purpose container. Each is a specialization that wins by giving up the other direction entirely. ## The write-many-read-once shape in practice A scheduling system holds hundreds of shift postings, each of the form "we need `v` extra staff every day from date `l` through date `r`". The output wanted is a per-day headcount array over a planning horizon of `n` days. The shape of that workload is the difference array's home turf: every posting is a range write, nothing is read until the whole roster is loaded, and then the entire horizon is read exactly once to produce the plan. Record `+v` at `l` and `-v` at `r+1` for each posting — O(m) — then run one accumulator pass over the horizon — O(n). Total O(m + n), and the read side gets a plain array with no indirection. Applying each posting directly to the days it covers would be O(m · n) in the worst case, and with long postings across a year-long horizon that difference is the difference between milliseconds and minutes. ## Composing the two Because they are inverses, they compose in ways worth recognizing. If you already hold a materialized array and want to start batching range increments against it, take its difference transform first, record marks, then prefix back. Two O(n) passes bracket any number of O(1) updates, so a batch of `m` updates against an existing array is O(n + m) rather than O(n·m). Running the prefix transform twice is also meaningful: the second pass turns a range increment into a *ramp* — a linearly growing increment across the range — which is how the pattern generalizes to arithmetic-progression updates. You still record a constant number of marks, just more than two, at the range's endpoints. And the shape extends dimensionally. In two dimensions a rectangle increment becomes four marks — one at each corner, with inclusion-exclusion signs — followed by prefix passes along each axis. The mark count grows as 2^d in `d` dimensions, which is why the trick stays practical for grids and stops being attractive well before high-dimensional data. ## What the duality does not give you The two structures do not combine into one that is fast at both ends. If a workload genuinely interleaves range writes with reads, neither transform helps: the prefix array must be rebuilt after each write, and the difference array must be materialized before each read. Recognizing that the duality is a *choice between profiles*, not a way to have both, is the judgment the question is really probing.
- You already hold a materialized headcount array and now need to batch fifty range adjustments against it. What do you do?Difference the array once in O(n), record the fifty adjustments as two marks each in O(1), then prefix back in O(n). Two linear passes bracket any number of constant-time updates, giving O(n + m) instead of the O(n·m) of applying each range directly. The bracketing passes are the fixed price of entering and leaving the difference representation.
- How does the pattern extend to a rectangular increment on a two-dimensional grid?Four marks instead of two, one at each corner of the rectangle with inclusion-exclusion signs, then a prefix pass along each axis to materialize. The generalization is 2^d marks in d dimensions, so it stays cheap for grids and becomes unattractive quickly as dimensions grow.
- Why can't you keep both structures live and get cheap reads and cheap range writes at once?They are inverses of the same data, not independent indexes, so a write to one invalidates the other. Maintaining a prefix array through a range write costs O(n) to rebuild the affected suffix, and reading a value from a difference array costs a pass. Keeping both means paying a linear cost on every operation, which is worse than picking one.
Prefix sums integrate and difference arrays differentiate: one accumulates a curve you then read off cheaply, the other records slopes you integrate once at the end.
saying these in an interview costs you the question
- Thinks a difference array also speeds up reads
- Believes a prefix array can absorb updates cheaply
- Cannot state that the two transforms undo each other
- Says you can maintain both structures for free
- Treats the choice as style rather than workload profile