Segment Tree: Build & Query
Range min, max, or sum in log n.
Beyond the Fenwick Tree
A Fenwick tree shines for sums, but a segment tree handles min, max, gcd, and more. It is the flexible workhorse of range queries.
A Tree Over Ranges
Each node owns a range of the array. The root covers everything; children split it in half until leaves hold single elements.
All lessons in this course
- Fenwick Tree for Prefix Sums
- Inversions with a BIT
- Segment Tree: Build & Query
- Lazy Propagation for Range Updates