DSA Notes

Range Queries

Lazy Propagation

Update a whole range at once by postponing the work.

The idea

Updating every element of a range one by one costs O(n log n). Lazy propagation stops at the O(log n) nodes that are fully covered: it fixes their stored answer and leaves a note (the lazy tag) saying “my children still owe this update”.

The note is pushed one level down only when a later operation needs to go below that node.

For “add v to a range, ask for the maximum”: a covered node’s maximum grows by v, and its tag grows by v.

Sample problem

1109. Corporate Flight Bookings ↗ Medium

There are n flights. Each booking [first, last, seats] reserves that many seats on every flight from first to last. Return the total seats reserved on each flight.

bookings = [[1,4,10],[3,6,20],[2,8,5]], n = 8
output = [10,15,35,35,25,25,5,5]

Why the solution works

Adding to every flight of every booking costs O(n) per booking. A segment tree can cover any range with O(log n) whole nodes, so record the booking on those nodes and stop there.

The recorded amount is a lazy note: “everything below me still owes this”. It is pushed down only when someone needs the values underneath. Here that happens once, at the end, in a single walk that carries the notes from the root to each leaf.

When updates and queries are mixed, the same notes are pushed one level down whenever an operation has to pass through a node. (For this particular problem a difference array is even simpler; the tree shows the general technique.)

Complexity: O(log n) per booking, O(n) for the final walk, O(n) memory.

Watch out

  • Push before descending, in updates and in queries.
  • With two kinds of update (assign and add), define how their tags combine and in which order they apply.
  • A range sum must add val × (length of the node), not just val.
Watch it run

Practise on LeetCode