Difference Arrays and Range Updates
22 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A warehouse adds stock to many ranges of shelves and reads the stock at the end. Looping over each range repeats work. A difference array records only where each change starts and stops.
Updating a range item by item
A warehouse has 8 shelves. A delivery adds the same units to every shelf from low to high, and there are many deliveries. Looping over the range costs its length for each delivery.
shelves = [0] * 8deliveries = [(1, 4, 5), (3, 6, 2)]for low, high, units in deliveries: for i in range(low, high + 1): shelves[i] += unitsprint(shelves)Example 1 · Brute force updates
shelves = [0] * 6for low, high, units in [(0, 2, 4), (2, 4, 1)]: for i in range(low, high + 1): shelves[i] += unitsprint(shelves)[4, 4, 5, 1, 1, 0]
What this code does
- Each update touches every shelf in its range.
- Shelf 2 is in both ranges, so it ends with 4 + 1.
Each update costs O(range length), so u updates on n items can cost O(n * u).
Mark only the two ends
Difference array is a list that stores how much the value changes from one position to the next. Adding to a whole range needs only two edits to it, and a running total rebuilds the real values.
Record the change at the start of the range and undo it just after the end. Two writes per update, whatever the length of the range.
n = 8diff = [0] * (n + 1)for low, high, units in [(1, 4, 5), (3, 6, 2)]: diff[low] += units diff[high + 1] -= unitsprint(diff)Example 2 · Watch the difference array change
diff = [0] * 7for low, high, units in [(0, 2, 4), (2, 4, 1)]: diff[low] += units diff[high + 1] -= units print(diff)[4, 0, 0, -4, 0, 0, 0] [4, 0, 1, -4, 0, -1, 0]
What this code does
- Only two cells change per update, and a negative number marks where the update stops.
- Index 3 holds -4 because the first update stops there, while the second one is still running.
Read it left to right: from index 1 the values go up by 5, and from index 5 they go down by 5 again. Each update is O(1).
One accumulate gives the final values
After all updates, the running total of the difference array is the real list. The spare last slot only exists so that high + 1 is always a valid index.
from itertools import accumulate
diff = [0, 5, 0, 2, 0, -5, 0, -2, 0]shelves = list(accumulate(diff))[:8]print(shelves)Example 3 · Updates on top of existing stock
from itertools import accumulate
stock = [10, 10, 10, 10, 10, 10]diff = [0] * 7for low, high, units in [(0, 2, 4), (2, 4, 1)]: diff[low] += units diff[high + 1] -= unitsprint([s + d for s, d in zip(stock, accumulate(diff))])[14, 14, 15, 11, 11, 10]
What this code does
- The running total of diff is the change at each shelf.
- zip pairs it with the starting stock, and the comprehension adds them.
Total cost: O(u) for the updates plus O(n) for one pass, so O(n + u) instead of O(n * u).
Going back: from a list to its differences
Subtract each item from the next one to get the difference array of any list. itertools.pairwise gives the neighbouring pairs.
from itertools import accumulate, pairwise
shelves = [0, 5, 5, 7, 7, 2, 2, 0]diff = [shelves[0]] + [b - a for a, b in pairwise(shelves)]print(diff)print(list(accumulate(diff)) == shelves)Example 4 · Round trip with pairwise
from itertools import accumulate, pairwise
target = [3, 1, 2, 1, 4]diff = [target[0]] + [b - a for a, b in pairwise(target)]print(diff)print(list(accumulate(diff)))print(sum(d for d in diff if d > 0))[3, -2, 1, -1, 3] [3, 1, 2, 1, 4] 7
What this code does
- The differences are the steps between neighbours. accumulate rebuilds the target from them.
- Each upward step needs at least that many new range additions, so the sum of positive steps is the least number of +1 range updates, counting from zero: 7.
accumulate and the differences undo each other. This pair is the core of every range-update trick.
Counting overlaps
Meetings are (start, end) hours, and the end hour is free again. Add 1 at the start and subtract 1 at the end. The running total is the number of meetings at each hour.
from itertools import accumulate
meetings = [(9, 11), (10, 12), (10, 13), (14, 15)]diff = [0] * 25for start, end in meetings: diff[start] += 1 diff[end] -= 1busy = list(accumulate(diff))print(max(busy), busy.index(max(busy)))Example 5 · All the busiest hours
from itertools import accumulate
meetings = [(9, 11), (10, 12), (10, 13), (11, 13)]diff = [0] * 25for start, end in meetings: diff[start] += 1 diff[end] -= 1busy = list(accumulate(diff))peak = max(busy)print(peak)print([hour for hour, count in enumerate(busy) if count == peak])3 [10, 11]
What this code does
- The peak count is the largest running total.
- enumerate pairs each hour with its count, so a comprehension lists every hour at the peak.
Example 6 · Large times with a dictionary
from collections import Counter
meetings = [(1000, 5000), (3000, 9000), (4000, 6000)]events = Counter()for start, end in meetings: events[start] += 1 events[end] -= 1current = peak = 0for time in sorted(events): current += events[time] peak = max(peak, current)print(peak)3
What this code does
- When times go up to a billion, a list is too big. A Counter keeps only the times that matter.
- Sort the event times and keep a running total. The cost is O(m log m) for m meetings.
The answer is the largest value and the first hour where it happens. This is the sweep-line idea in its simplest form.
Next step
Check your understanding
12 quick questions