Difference Array
A difference array records where range updates start and stop, then uses one prefix pass to materialize the final values.
The Core Trick
Suppose many operations add val to every index in range l..r. Updating each element directly costs O(r - l + 1) per operation, which can become too slow when both the array and update list are large.
A difference array stores changes between neighboring positions instead of final values. To add val on l..r, do diff[l] += val and diff[r + 1] -= val if r + 1 is inside the array. The first mark starts the increase; the second mark cancels it after the range ends.
Reconstructing the Array
After all updates are marked, run a prefix sum over diff. The running total at index i is exactly the net value that should apply to arr[i]. Every active update has started but not yet been canceled, so it contributes to the running total.
This turns each update into O(1) work and performs the actual propagation once. The final reconstruction costs O(n), so the total cost is O(n + q) for q range updates.
When to Use It
Difference arrays are the range-update counterpart to prefix sums. Prefix sums answer many range queries quickly after fixed data. Difference arrays apply many range updates quickly before final data is needed.
Look for phrases like apply many increments, bookings over intervals, range addition, brightness changes, or timeline deltas. If no query asks for intermediate states between updates, a difference array is often the simplest optimal approach.
Boundary Discipline
The cancellation at r + 1 is the main source of bugs. If r is the last valid index, there is no later element where the increase should stop, so skip the cancellation or allocate n + 1 difference slots and ignore the sentinel during reconstruction.
Also keep the interval convention consistent. The common formula above is for closed ranges l..r. Half-open ranges use different boundaries, and mixing conventions causes off-by-one errors.
Apply range additions with a difference array
The extra slot lets the code mark right + 1 even when the update reaches the last real index.
Key Takeaways
- For range add **l..r**, mark **diff[l] += val** and **diff[r + 1] -= val**.
- A prefix pass over the difference array reconstructs the final values.
- Each range update is **O(1)**, and all final values appear after one **O(n)** pass.
- Difference arrays are ideal when many updates happen before final point values are needed.