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 flights, numbered 1 to . Each booking [first, last, seats] reserves seats seats on every flight from first to last, both included. Return an array whose entry is the total seats reserved on flight .
Constraints
-
bookings.length -
firstlast -
seats
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 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 flights, so the worst case is:
That is four times the 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 0The 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.
Record each update with two writes
The code keeps the changes in an array called diff, indexed from 0, so flight f is at index f - 1. A booking [first, last, seats] starts at index first - 1. Its last flight is at index last - 1, so the first index after it is last, and the two writes are:
diff[first - 1] += seatsdiff[last] -= seatsIn the figure for the first sample, each booking is a bar over the indices it covers, labelled with that range in half-open form: the first booking, 10 seats on flights 1 and 2, covers indices 0 and 1, the half-open range [0, 2), and writes at index 0 and at index 2. Below the bars are diff after all six writes and its running sum.
diff gives every flight's seats.Index 1 received and , so diff[1] is 45. The third booking ends at flight 5, the last one, and writes its at index 5. No flight is stored there and the running sum stops before it, but the write still needs a cell, so diff has of them.
def corp_flight_bookings(bookings, n):
diff = [0] * (n + 1)
for first, last, seats in bookings:
diff[first - 1] += seats
diff[last] -= seats
answer = []
total = 0
for i in range(n):
total += diff[i]
answer.append(total)
return answer
print(corp_flight_bookings([[1, 2, 10], [2, 3, 20], [2, 5, 25]], 5))
print(corp_flight_bookings([[1, 2, 10], [2, 2, 15]], 2))The first loop makes the two writes for each booking, and the second takes the running sum.
Cost of range additions
- Adding each booking flight by flight
per booking - A booking can cover every flight: up to additions at the largest input.
- Two writes per booking
per booking - 40,000 writes for 20,000 bookings, however many flights each covers.
- The final running sum
, once - 20,000 additions, and cells of memory for
diff.
That is 60,000 steps at the largest input. A cell of diff is a change and says nothing about a flight on its own, so the seat counts exist only after the final pass. A difference array fits a batch of updates followed by reads. When reads come between the updates, each read would need a pass of its own, and a Fenwick tree handles that case with steps for each update and each read.
When the values do not start at 0, make the same writes and add each position's running sum to that position's starting value.
Apply range additions and watch the two writes
Every value starts at 0. Choose a half-open range and an amount and apply it: the diff row changes in two cells, and the values row is its running sum. Enter the three bookings as 10 on [0, 2), 20 on [1, 3) and 25 on [1, 5) to rebuild the figure. Then apply on [1, 3), which makes the same two writes with the signs swapped and cancels the second booking.
Common difference-array mistakes
Writing the negative amount at the index of the last flight in the booking.
- Where it breaks
- For the booking
[1, 2, 10]with two flights,diff[1] -= 10cancels the 10 before the running sum reaches flight 2. The result is[10, 0]instead of[10, 10]. - The fix
- Write the negative amount one index later, at
diff[last].
Giving
diffonly cells.- Where it breaks
- A booking that ends at flight writes to
diff[n]. Python raisesIndexError, and C++ writes past the end of the vector, which is undefined behavior. - The fix
- Allocate cells. The last one is written and never read.
Reading a seat count from
diffbefore the final pass.- Where it breaks
- After the first sample's three bookings
diff[1]is 45, but flight 2 has 55 seats: 45 is how much flight 2 differs from flight 1. - The fix
- Make every update first, then take the running sum once and read from that.
Recall With 5 flights, a booking reserves 10 seats on flights 2 through 4. Which two cells of `diff` change?
Flights 2 through 4 are indices 1 through 3, the half-open range [1, 4), so the writes are diff[1] += 10 and diff[4] -= 10. The running sum is 0 at index 0, then 10 at indices 1, 2 and 3, and back to 0 at index 4.