So far, prefix sums have been about reading — “what's the sum from here to there?” But real systems don't just read. They write.

Picture this: you're the ops engineer for a fleet of 10,000 delivery vehicles. Headquarters sends you three directives in quick succession: “Push a GPS firmware update to vehicles 47 through 200.” “Apply a speed limiter patch to vehicles 12 through 89.” “Enable holiday routing for vehicles 150 through 300.”

The brute-force approach: loop through each range and touch every vehicle individually. Directive 1 touches 154 vehicles. Directive 2 touches 78. Directive 3 touches 151. That's 383 individual write operations for just three directives.

Now scale it up. A thousand directives per day, each spanning hundreds of vehicles. Suddenly you're doing millions of individual operations, and most of them are redundant — you're visiting the same vehicles over and over, each time applying one more increment.

What if each directive — no matter how wide the range — only required touching two cells? Not 154 writes. Not 78. Just two. A mark at the start that says “begin the effect here” and a mark at the end that says “cancel the effect here.” Then, when you're done with all directives, a single sweep from left to right propagates every effect to every vehicle in one pass.

That's the idea. And it's the inverse of what you've been doing with prefix sums. Instead of precomputing a running total to answer queries, you're deferring computation until the very end — batching all the updates, then computing the result once.

The cost? O(1) per update, O(n) for the final sweep. For Q updates on an array of size n, that's O(Q + n) instead of O(Q * n). The savings are staggering.

Apply three range updates by hand. Watch the ops counter climb. Then try placing just two markers per update — and predict what happens when you sweep.

What you just used is called a difference array — and its relationship to the prefix sum is one of the most beautiful dualities in computer science.

Let's trace through a concrete example to see the round-trip in action.

Start with an original array: arr = [0, 0, 0, 0, 0, 0] (six zeros). You want to apply the update “add 3 to indices 1 through 3.”

Step 1: Build the difference array. Initialize diff = [0, 0, 0, 0, 0, 0]. Apply the update: diff[1] += 3 and diff[4] -= 3. Now diff = [0, 3, 0, 0, -3, 0].

Look at what you wrote. The +3 at index 1 is a start marker — it says “from here onward, add 3.” The -3 at index 4 is a stop marker — it says “the effect ends here; cancel it.” Together, they encode the entire range update in just two numbers.

Step 2: Sweep with prefix sum. Accumulate diff from left to right:

• result[0] = 0
• result[1] = 0 + 3 = 3
• result[2] = 3 + 0 = 3
• result[3] = 3 + 0 = 3
• result[4] = 3 + (-3) = 0
• result[5] = 0 + 0 = 0

Final result: [0, 3, 3, 3, 0, 0]. Exactly what you'd get from the brute-force loop — but with 2 writes + 1 sweep instead of 3 writes.

This is the derivative/integral duality from calculus, transplanted into discrete arrays:

• The difference array is the discrete derivative. Each element records the change from the previous position — not the absolute value, but how much it increased or decreased.
• The prefix sum is the discrete integral. It accumulates those changes back into absolute values.
• The round-trip — prefix_sum(diff(arr)) = arr — is the fundamental theorem of discrete calculus. Differentiate, then integrate, and you're back where you started.

This duality means range updates and range queries are mirror operations. A prefix sum spends O(n) upfront to enable O(1) range queries on a static array. A difference array spends O(n) at the end (the sweep) to enable O(1) range updates on a batch.

The key constraint is timing: difference arrays work when you batch all updates before reading the final result. If you need to interleave updates and queries — “add 5 to range [2,7], now what's the sum of [3,5], now add 2 to [1,4]” — the difference array can't help, because each query requires a fresh sweep. For that, you need a more powerful structure: a Fenwick tree (Binary Indexed Tree) or a segment tree, which handle both operations in O(log n). That's the next level of the prefix sum evolution.