Segment trees for range queries and updates · 3 of 3 Advanced
Lazy propagation
Update a whole range at once by leaving tags on the nodes inside it and pushing them down only when an operation goes below.
Books1
Links3
- Range Update Range Query Range updates with two Fenwick trees, then lazy segment trees for range add and for Range Updates and Sums, with a problem list. usaco.guide (opens in a new tab)
- Segment Tree Its range updates section: adding on segments, assigning on segments, and adding with maximum queries. cp-algorithms.com (opens in a new tab)
- Lazy Segtree A library version of the lazy tree. Its mapping and composition functions are the last two requirements of this page. atcoder.github.io (opens in a new tab)
More links5
- USACO Guide – Lazy Propagationusaco.guide (opens in a new tab)
- 715. Range Modulealgo.monster (opens in a new tab)
- Errichto – Segment Tree with Lazy Propagationyoutube.com (opens in a new tab)
- CF Blog — Lazy Propagation on Segment Trees (by bAbAa)codeforces.com (opens in a new tab)
- CF Blog — Segment Tree with Lazy Propagation (by dragonslayerintraining)codeforces.com (opens in a new tab)