Day 19 — Segment Trees

What you’ll learn here

• Range queries in O(log n): sum, min, max, gcd, any associative operation
• Point updates and range updates with lazy propagation
• Recursive build, query, and update — the canonical template
• Binary Indexed Trees (Fenwick trees) — when you want something smaller and only need prefix sums

Segment trees are the heavy machinery of competitive programming. They turn “give me the sum of any subarray, possibly after a thousand updates” from O(n) per query into O(log n).