Sign in to watch this lesson
Advanced - Data Structures and Range Queries Ā· 4:00
Dynamic (Sparse - Implicit) Segment Tree
When positions run up to 10^9 but only a few are ever used, a dynamic segment tree keeps the full tree only in principle: the root exists, and an update creates the missing nodes on its root-to-leaf path, about 30 of them. Reads treat a missing child as zero and must never allocate. Nodes live in an index pool, the midpoint is computed as l + (r - l) / 2, lazy notes work as usual, and when all queries are known in advance, coordinate compression with an ordinary tree is simpler and faster.
You will learn
- Explain why an update over a range of size C creates at most about log2 C nodes, and why the total stays O(Q log C)
- Implement a dynamic segment tree with an index pool, child creation on first touch, and reads that never allocate
- Avoid the midpoint overflow and the allocate-on-read memory leak
- Decide between a dynamic tree and coordinate compression, and combine dynamic nodes with lazy propagation or tree descent