LESSON 8 · PATTERN GUIDE

Difference Array / Range Updates

Apply many interval increments cheaply, then reconstruct the final values with a running sum.

FIRST, LEARN THE PATTERNAn update over [left, right] changes only the difference at left and the position after right. A prefix pass accumulates the changes.

Many range additions or bookings update intervals, and the final values are needed after all updates.

How to approach it

Add delta at left, subtract delta at right + 1 when in bounds, then take a prefix sum over the difference array.

Watch out for

Use a difference array one element longer when convenient, and watch inclusive versus exclusive interval endpoints.

A CLOSER EXPLANATION

A range update affects two boundaries: where the change starts and where it stops applying. Store those boundary changes, then a prefix sum reconstructs the value at every position. This changes many O(range length) updates into O(1) work per update plus one O(n) reconstruction.

NOW YOU TRY

Practice question

Start with five zeros. Apply +3 to indices 1–3 and then +2 to indices 2–4. What is the final array?

EXAMPLEn = 5; updates = [(1, 3, +3), (2, 4, +2)]Give your answer before revealing the explanation.

Show a hint

Record only the start and the position just after each update's end, then prefix-sum.

Show an answer

[0, 3, 5, 5, 2]

CONNECT IT TO REAL LIFE

Difference Array / Range Updates at work

A conference room is reserved for day ranges: +1 booking on days 1–3 and +1 on days 3–4. How many bookings are active on days 1 through 5?

Show one possible approach

[1, 1, 2, 1, 0]. Add at the start day and subtract just after each reservation ends, then prefix-sum the boundary changes.

Practice next

Use these problem IDs to find additional practice for this pattern:

37010941109189319432381