Part XI · Advanced Data Structures and Offline Techniques
64. Offline Range Queries and Query Reordering
7 lessons•24 topics•Advanced / Expert
0 of 7 lessons published
64.01Outline
Offline vs online
- Queries available in advance
- Reordering
- Coordinate compression
- Query sorting
64.02Outline
Mo's algorithm
- Block ordering
- Add/remove operations
- Frequency maintenance
- O((n+q)sqrt n) typical bound
64.03Outline
Mo variations
- Hilbert order
- Mo with updates
- Mo on trees
- Direction-sensitive add/remove
64.04Outline
Parallel binary search
- Batch midpoints
- Time-ordered event updates
- Fenwick integration
64.05Outline
CDQ divide and conquer
- 3D dominance counting
- Offline partial order
- Merge-time processing
64.06Outline
Small-to-large technique
- Merge smaller map into larger
- Subtree color frequencies
- Amortized O(n log n) intuition
64.07Outline
Offline dynamic connectivity
- Segment tree over time
- Edge active intervals
- Rollback DSU