Where it runs
1. The problem
Last lesson's segment tree changed one element at a time. You wrote the new value into a leaf and went up the one path to the root, recomputing every ancestor. That is a point update: one position changes, at a cost of O(log n).
Now the change covers a whole stretch: "add 3 to every element in [l, r]". A booking takes seats 41 through 80, and the count of each of those 40 seats goes up by one. With point updates that is 40 climbs up the tree. A range of a million positions gives a million climbs. A range change costs O(length of the range) again, and the tree has won nothing.
You want "add delta to all of [l, r]" to cost the same O(log n) as a query. To get there, the walk down stops at the nodes whose range lies fully inside [l, r]. The change is written right onto them and does not go down to every leaf.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Problems that add to or flip a whole range and then ask for a range sum or maximum. LeetCode rarely needs the lazy tree, since when every update comes before the queries the difference array from lesson 27 is simpler. It pays off when updates and queries mix.
Range adds, then one read of every seat count. The lazy tree passes, and the difference array from lesson 27 does it in O(n).
A flip on l to r turns the count of 1s into the length minus that count, so store counts and a pending flip on each node.
Compress the square edges to positions. Each square reads the max height over its range and sets the whole range to the new height, so the pending tag holds a value to set where the lesson's holds an amount to add.