Corporate Flight Bookings
There are n flights numbered 1..n. Each booking [first, last, seats] reserves seats on every flight from first to last inclusive. Return the total seats reserved on each flight.
- 1 ≤ n ≤ 2 · 10^4
- 1 ≤ bookings.length ≤ 2 · 10^4
- 1 ≤ first ≤ last ≤ n
- 1 ≤ seats ≤ 10^4
- Many range updates, then read all values once
- Adding a constant over a range = +v at start, −v after end
- Difference array, then prefix sum
If many queries ask for an aggregate over [l, r] and the aggregate has an inverse (sum, XOR, product without zeros), precompute P[i] = agg(a[0..i)) once so every query becomes P[r+1] - P[l]. Combined with a hash map of seen prefix values it counts subarrays with a given sum in one pass; the inverse trick (difference array) makes range updates O(1).
Create a difference array d of size n + 1. For each booking add seats at d[first - 1] and subtract it at d[last]. Taking the running prefix sum of d reconstructs the per-flight totals: every flight inside a range picks up the +seats and flights past the range are cancelled by the -seats. Each booking costs O(1) regardless of its width.
- Applying each booking directly is O(n · b). A Fenwick tree with range update / point query handles interleaved updates and queries in O(log n) each.