Part XI · Advanced Data Structures and Offline Techniques
63. Persistence, Dynamic Trees and Specialized Range Structures
7 lessons•29 topics•Advanced / Expert
0 of 7 lessons published
63.01Outline
Persistent data structures
- Versioning
- Path copying
- Structural sharing
- Persistent array
- Persistent segment tree
63.02Outline
Persistent search
- Kth smallest on subarray
- Versioned frequency trees
- Persistent trie
- Fat-node method intro
63.03Outline
Li Chao tree
- Minimum/maximum line at x
- Discrete vs continuous coordinates
- Segment insertion
- Dynamic Li Chao
63.04Outline
Segment tree beats
- Chmin/chmax
- Sum queries
- Node invariant
- Amortized complexity caveats
63.05Outline
Link-cut trees
- Dynamic forest
- Expose/access
- Link/cut
- Path aggregates
- Splay-based implementation overview
63.06Outline
Euler-tour trees
- Dynamic forest representation
- Split/merge of Euler tour
- Connectivity maintenance
63.07Outline
Wavelet trees/matrices
- Rank/select
- Kth smallest
- Range frequency
- Space-time trade-offs