~/problems
Problems
Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.
Segment tree (+ lazy propagation)
Any associative range query with point or range updates in O(log n).
Notes
Recognise it when: you need range queries for any associative operation (min, max, sum, gcd) with updates. With lazy propagation, range updates work too.
- An iterative bottom-up tree (size 2n) is short to write for point updates and range queries.
- Lazy: each node stores
(value, pending). Push the pending value down before visiting the children.
In an interview: rarely required. Knowing that it exists, its O(log n) bounds, and when a Fenwick tree or a sorted list would do instead is usually enough.
5 problems
Advanced & competitive
Range queries Fenwick trees, segment trees, sparse tables.
Segment tree (+ lazy propagation) guide
- Basics: build and update a bottom-up segment tree basics easy
- Greenhouse: hottest sensor in a range py · c++ · java easy
- Falling squares py · c++ · java hard
- Dynamic range minimum queries py · c++ · java easy
- Range add, point query py · c++ · java easy