Section Recap

Segment trees: $O(\log n)$ range queries with updates. Structure: Array-based binary tree.

Node $i$ has children $2i$ and $2i+1$. Core Operations:

• Build from array: $O(n)$
• Point update: $O(\log n)$
• Range query: $O(\log n)$

Lazy Propagation: For range updates.

Mark nodes as "lazy" and push updates when needed. Common Uses: Range sum, min, max, GCD, count. Time: $O(\log n)$. Space: $O(n)$.