Algorithms / Segment Tree Lazy Propagation
Least You Need to Know: Lazy Propagation for Range Updates and Range Queries
Lazy propagation lets a segment tree postpone pushing range updates into children until that detail is actually needed. The main idea is to keep a pending tag that says, in effect, 'this whole interval has already been updated even if the children are not individually refreshed yet.'
Least you need to know
- Lazy propagation stores deferred update information at internal nodes.
- A lazy tag means the node value already reflects an update, even if children have not been individually adjusted yet.
- Before descending to children, pending lazy information is usually pushed downward.
- Lazy propagation is useful when both updates and queries affect ranges, not just single points.
- Segment trees often use about
4narray space in interview implementations.
Key notation
- lazy[node] — pending update still to be propagated to children
- push — transfer a pending tag to child nodes before deeper recursion
- 4n — common safe array size for tree storage in interviews
Worked example
- Suppose you add 5 to every element in a query range.
- If a node interval is fully covered, increase its stored aggregate and record a lazy tag instead of updating every descendant immediately.
- Later, if a partial-overlap query needs the children, push that tag down first.
- This deferral keeps both range updates and queries efficient.
Common mistakes
- Students sometimes forget to update the node's own aggregate when attaching a lazy tag.
- Pushing lazy tags too late or never can make child answers stale.
- Lazy propagation is for deferred range effects, not for unrelated balancing.
How to recognize it
- The problem needs many range updates plus many range queries.
- Point-update structures are no longer sufficient.
- You want to defer work on untouched subtrees until a later query or deeper update needs it.
บทเรียนถัดไปที่แนะนำ
เรียนต่อในหัวข้อนี้ด้วย Least You Need to Know: Segment Trees, Range Queries, and Overlap Cases
Least You Need to Know: Segment Trees, Range Queries, and Overlap Casesบทเรียนที่เกี่ยวข้อง
เรียนต่อด้วยบทเรียนใกล้เคียงในหัวข้อเดียวกัน