Intro

Segment trees answer range queries in $O(\log n)$. Structure: Binary tree where each node covers a range. Leaves are single elements.

Internal nodes combine children. Operations:

• Build: $O(n)$
• Query: $O(\log n)$
• Update: $O(\log n)$

Use Cases: Range sum, range min/max, range GCD.

When you need both updates and queries. vs Prefix Sum: Prefix sum is $O(1)$ query but $O(n)$ update. Segment tree is $O(\log n)$ for both. Space: $O(n)$.