Difference array
Overview
An array representing the differences between adjacent elements, used to apply multiple range additions in O(1) time each.
It reduces O(N) range updates to O(1).
Where used: Flight booking systems, Cumulative ticket counting
Why it exists
Problem: We need to add a value `V` to all elements in an array between indices `L` and `R`, multiple times. Doing this Naively takes O(N) per query, which is too slow for many queries.
Naive approach: Run a for-loop from `L` to `R` and add `V` to each element, taking O(N) time per range update.
Better idea: Instead of updating all elements, just mark the start of the range with `+V` and the element just after the end of the range with `-V`. Later, we can recover the final array by computing the prefix sum of these marks.
Why learn this
- It is the direct inverse of the Prefix Sum pattern.
- It teaches you how to defer expensive operations (lazy evaluation) until they are actually needed.
Mental model
Like putting a 'Start adding V here' sign at index L, and a 'Stop adding V here' sign at index R+1. When you walk down the street (prefix sum), you accumulate the active signs.
A difference array `diff` tracks the change between adjacent elements of the original array. To add `V` to `[L, R]`, we only update `diff[L] += V` and `diff[R + 1] -= V`. After all range updates, a prefix sum over `diff` reconstructs the final values.
Repeated decision: Where do I start the addition, and where do I cancel it out?
Deep dive
A difference array is exactly what it sounds like: `diff[i] = arr[i] - arr[i-1]`. Because of this definition, if we compute the prefix sum of `diff`, we get the original `arr` back.
The magic happens when we want to update a range. Suppose we want to add 10 to every element from index 2 to 5. Instead of doing 4 additions, we add 10 to `diff[2]`. When we eventually compute the prefix sum, every element from index 2 onwards will be 10 higher. But we only wanted to add 10 up to index 5! So, we subtract 10 from `diff[6]`. This 'cancels out' the addition for everything after index 5.
By doing `diff[L] += V` and `diff[R + 1] -= V`, we process any range update in `O(1)` time. After millions of these O(1) updates, we do a single `O(N)` prefix sum pass to read the final array.
This technique is an offline algorithm—it assumes you know all the updates in advance and only need the final array at the end. If you need to interleave updates and reads, you need a Segment Tree or Fenwick Tree.
Key points
- Complexity: Range Update is O(1). Final Array Reconstruction is O(N). Space is O(N).
- Offline Only: You cannot easily query the value of a specific element *during* the updates without doing an O(N) prefix sum. It's meant for batch updates.
Pattern: Difference Array
Recognition cues:
- Apply multiple range additions
- Return the final array after all operations are done
Failure signals
- The problem requires both updates AND point/range queries interleaved.
Engineering examples
Data stream batching
Applying thousands of overlapping discount codes to a catalog of products.
Instead of locking and updating database rows for every discount, we record the start and end of the discount ranges and apply them in one linear sweep.
When not to use
- Online Queries: If you need to query the array's state in between updates, the difference array fails because reading requires an O(N) sweep.
Common mistakes
- Off-by-one on the cancellation index: If the range is `[L, R]`, the subtraction happens at `R + 1`, not `R`. Subtracting at `R` would mean the value at index `R` doesn't get the addition.
- Out of bounds on R + 1: If the range extends to the very end of the array, `R + 1` might be out of bounds. You should allocate the difference array with size `N + 1` to safely handle this.
Recall questions
- What two operations are needed to add `V` to the range `[L, R]` in a difference array?
- How do you recover the final array from a fully populated difference array?
Understanding checks
An array of 5 zeros is updated with `diff[1] += 5` and `diff[3] -= 5`. What is the prefix sum array?
`[0, 5, 5, 0, 0]`.
Index 0 is 0. Index 1 adds 5 (total 5). Index 2 adds 0 (total 5). Index 3 adds -5 (total 0). Index 4 adds 0 (total 0).
To add 10 to indices 2 through 4, a dev writes `diff[2] += 10; diff[4] -= 10;`. What's the bug?
Index 4 will NOT receive the +10 in the final prefix sum. It should be `diff[5] -= 10`.
The subtraction acts as an instruction to 'stop adding from this point forward'. If you stop at 4, index 4 misses out.
Questions & answers
Corporate Flight Bookings
This is a pure difference array problem. Add passengers at the start flight, subtract at end_flight + 1.
Approach: Create an array of size N+1. Process bookings in O(1). Return the prefix sum.
Practice tasks
Corporate Flight Bookings
You are given `n` flights and an array `bookings` where `bookings[i] = [first, last, seats]`. Return an array of size n with the total number of seats booked on each flight.
Continue learning
Previous: Prefix Sums