Arrays and searching 0/120

Prefix sums · 3 of 3

Difference arrays

Apply many range additions with two writes each, then recover every value with one running sum.

1,131 words · 6 min read

Part 1 of 3 Difference arrays

Many range additions on one array

Prefix sums answer many questions about an array that does not change. Some problems are the other way round: there are many changes, each adding an amount to a whole range of positions, and the values are read only after the last change.

There are nn flights, numbered 1 to nn. Each booking [first, last, seats] reserves seats seats on every flight from first to last, both included. Return an array whose entry ii is the total seats reserved on flight i+1i + 1.

Constraints

  • 1≤n≤2×1041 \le n \le 2 \times 10^4
  • 1≤1 \le bookings.length ≤2×104\le 2 \times 10^4
  • 1≤1 \le first ≤\le last ≤n\le n
  • 1≤1 \le seats ≤104\le 10^4

Sample 1 · Input

bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5

Output

[10,55,45,25,25]

Sample 2 · Input

bookings = [[1,2,10],[2,2,15]], n = 2

Output

[10,25]

In the first sample, flight 2 is inside all three bookings and gets 10+20+25=5510 + 20 + 25 = 55 seats. Flight 5 is inside only the last one and gets 25.

The direct method adds each booking's seats to every flight it covers. A booking can cover all nn flights, so the worst case is:

2×104 bookings×2×104 flights=4×108 additions2 \times 10^4 \text{ bookings} \times 2 \times 10^4 \text{ flights} = 4 \times 10^8 \text{ additions}

That is four times the 10810^8 budget. To find something cheaper to store, look at how the seat count changes from each flight to the next. Here is the booking [2, 3, 20] on its own, with five flights:

flight      1    2    3    4    5seats       0   20   20    0    0change      0  +20    0  -20    0
Each change is a flight's seats minus the seats of the flight before it. Flight 1 has no flight before it, so its change is its own seats.

The count goes up by 20 at flight 2, where the booking starts, and down by 20 at flight 4, the first flight after it ends. Every other flight has the same count as the flight before it. So a booking makes two changes, however many flights it covers: one at its first flight and one at the flight just after its last. Those two numbers are enough to rebuild the whole row: start from 0 and add the changes from left to right, and the running sum is 0, 20, 20, 0, 0.

An array that stores these changes is called a difference array, because each entry is the difference between a value and the value before it. Changes from different bookings add up: if two bookings start at flight 2, the count rises by both amounts there. So we can record every booking in one difference array and take the running sum once, at the end.

That running sum is the same pass that builds a prefix sum array. There it turned values into running totals; here it turns the differences back into the values. We leave out the leading 0 this time, because we read the running sums themselves and never subtract two of them.