Bumping a whole range without touching every slot

You run a booking calendar. At the start every day has zero guests. One booking takes days 3 to 9 for 4 guests, so you add 4 to each of those seven days. Another takes days 2 to 20 for 2 guests, so you add 2 to nineteen days. And so on, for thousands of bookings.

The first idea: for each booking, walk over its days and add the guests. One booking for 300 days is 300 additions. Ten thousand bookings like that make millions of writes, and you haven't even checked for overbooking yet.

You read the final number for each day only once, at the end. Until then you just stack range additions on top of each other. There is a way to record each such addition with two marks, then turn all the marks into the final numbers in one pass.

Take 5 days, numbered 0 to 4, and the booking "+2 guests on days 1 to 3". Instead of three additions you leave two marks. On day 1 you write +2: from here on there are 2 more guests. On day 4, right after the booking ends, you write -2: from here on those guests are gone.

You can leave as many pairs of marks as you like, for any bookings. At the very end you walk through the days once from the start and keep the total of all the marks you have met. Day 0: 0. Days 1, 2, 3: 2 each. Day 4: 0 again. Two marks per booking and one pass at the end.

Make a helper array diff, one cell longer than the data, filled with zeros. To add val over the range [l, r], leave two marks: diff[l] += val and diff[r+1] -= val. The +val mark turns the addition on from l. The -val mark turns it off right after r.

Nothing else is needed for one update. Two writes, however wide the range is.

To get the real values, walk from left to right and keep a running total: running += diff[i], then result[i] = running. The running total carries each +val forward from the place where it was turned on and loses it at r+1. So exactly the days from l to r get the addition.

Subtract at r+1, not at r. The addition has to last through day r, so it is turned off one cell later. If you turn it off at r, the last day of every range misses its addition.

Trace it on n = 5 with the updates [[1,3,2], [2,4,1]].

• Update [1,3,2]: diff[1] += 2, diff[4] -= 2.
• Update [2,4,1]: diff[2] += 1, diff[5] -= 1.
• Now diff = [0, 2, 1, 0, -2, -1].
• The running total: 0, then 0 + 2 = 2, then 2 + 1 = 3, then 3 + 0 = 3, then 3 - 2 = 1. So result = [0, 2, 3, 3, 1].

Check it by hand: +2 on days 1 to 3 and +1 on days 2 to 4 give exactly this.

Each update is two writes: O(1). For u updates that is O(u). The final pass visits each cell once: O(n). The total is O(n + u). Memory is O(n) for the diff array.

Adding to every element by hand costs O(n) per update and O(n·u) in total. The marks at the two ends remove that factor.

There is one condition: the method works when all the writes come first and the reading comes after. If reads and writes take turns (write, read, write, read), a plain difference array can't keep up. That needs a Fenwick tree or a segment tree, which come much later in the course.

Occupancy of seats and days in a calendar with capacity checks, and finding overbooked flights and hotels. Applying many rules such as "add N over this range of IP addresses" or "raise prices in this price range", after which the result is read once. A heatmap that gets thousands of ranges painted onto it and is then drawn once. Anywhere a batch of range additions piles up first and the totals are looked at later.