Segment trees answer range queries in . Structure: Binary tree where each node covers a range. Leaves are single elements.
Internal nodes combine children. Operations:
- Build:
- Query:
- Update:
Use Cases: Range sum, range min/max, range GCD.
When you need both updates and queries. vs Prefix Sum: Prefix sum is query but update. Segment tree is for both. Space: .