Difference Array

A difference array is the inverse of a prefix sum. Prefix sums make range queries cheap; a difference array makes range updates cheap. When you have to add +k to many ranges [start, end] and only need the final array, mark each range's boundaries in $O(1)$ and rebuild everything with a single prefix-sum pass at the end.

The idea#

The trick is to record only where each update begins and ends. Picture a flat line. Instead of raising every point in a range one by one, flip a switch at the entry point and flip it back at the exit point.

1. At start: switch on, diff[start] += k. The effect begins here.
2. At end + 1: switch off, diff[end + 1] -= k. The effect stops here.
3. Final pass: take the running total. The +k carries forward from start until it meets the -k at end + 1, where the two cancel.

The brute force touches every index of every range, $O(n \cdot q)$ for q updates. The difference array costs $O(1)$ per update plus one $O(n)$ rebuild.

To see the switch in action, take length = 5 and one update [1, 3, +2]:

Index 4 drops back to 0 because the -2 cancels the +2 that cascaded in from index 1. Without that -2, the increment would leak all the way to the end of the array.

How to spot it#

Range updates show up in many disguises, so look for these cues:

• Many updates of the form "add v to every index in [l, r]".
• You only need the final state, not answers between updates.
• The index space is small and discrete (up to about $2 \times 10^5$).
• Bookings, passengers, population by year, or shifts applied to ranges of a string.

If the coordinates are huge (up to $10^9$), or you need to react to events in order, use Line Sweep instead. A difference array is the special case of a sweep where every coordinate gets its own slot.

Template#

The template puts the three steps from above into code. It takes inclusive ranges, 0-indexed.

diff = list of n + 1 zeros       # spare slot, so end + 1 never overflows
for each (start, end, val) in updates:
    diff[start] += val           # switch on
    diff[end + 1] -= val         # switch off after the range
for i from 1 to n - 1:
    diff[i] += diff[i - 1]       # running total rebuilds the real values
return the first n values of diff

The spare slot at index n replaces the if end + 1 < n check. Anything written there falls off the end of the result.

Pitfalls#

These are the mistakes that most often cost a correct answer.

• Inclusive vs half-open. Read the problem: does the effect still apply at end? Inclusive means mark end + 1. Half-open (drop-off point, death year) means mark end.
• 1-indexed input. Some problems number positions from 1. Shift both ends down by one before marking.
• Out-of-range end + 1. Allocate n + 1 slots, or guard the write.
• Reading diff[-1]. A rebuild loop that starts at index 0 and reads diff[i - 1] silently reads the last element in Python. Start the loop at 1.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

• 1854. Maximum Population Year
• 370. Range Addition
• 1109. Corporate Flight Bookings
• 1094. Car Pooling
• 2381. Shifting Letters II
• 848. Shifting Letters
• 995. Minimum Number of K Consecutive Bit Flips

Hints#

Open a hint only after you have tried the problem for a while.

Key takeaways#

• A difference array turns each range update into two $O(1)$ boundary writes.
• One prefix-sum pass at the end rebuilds the real values.
• +v at start, -v at end + 1 for inclusive ranges, at end for half-open ones.
• Use it when indices are small and you only need the final state; otherwise sweep.