Part V · Trees, Priority Structures and Range Queries
30. Static Range Queries and Decomposition Techniques
6 lessons•27 topics•Intermediate / Advanced
6 of 6 lessons published
30.015 animated
Sparse table
- Idempotent operations
- Min/max/GCD
- Precompute powers of two
- O(1) RMQ
- Overlapping blocks
30.024 animated
Disjoint sparse table
- Associative queries
- Prefix/suffix per block
- Static range sums/products
- O(1) queries
30.035 animated
Square-root decomposition
- Block sums
- Point update
- Range query
- Lazy block updates
- Rebuild trade-offs
30.044 animated
Cartesian tree
- RMQ reduction
- Monotonic stack construction
- Cartesian tree properties
- LCA connection
30.055 animated
Range-query transformations
- Difference arrays
- Prefix sums
- Offline sorting
- Coordinate compression
- Query reordering
30.064 animated
Monotonic queue techniques
- Sliding window minima
- Sliding window maxima
- O(n) deque processing
- DP transitions