Sign in to watch this lesson
Advanced - Data Structures and Range Queries Ā· 4:51
RMQ Survey - Choosing the Structure
Range-minimum structures sit on a map of update cost against query cost: sparse tables and the Cartesian-tree method answer in O(1) but never change, Arpa's trick is nearly constant but offline, segment and Fenwick trees are logarithmic on both sides, and square-root blocks and the sqrt tree trade one side for the other. Five questions in order (does the array change, are queries offline, is the operation idempotent or invertible, are updates ranges, what are the sizes and budgets) pick the structure, and a measurement settles speed against memory.
You will learn
- Place sparse table, Fenwick tree, segment tree, sqrt decomposition, sqrt tree, Arpa's trick and the Cartesian-tree method by build, query and update cost
- Choose a structure by asking, in order: does the array change, are queries offline, is the operation idempotent or invertible, are updates ranges, and what are n, Q and the budgets
- Weigh measured speed against memory (a sparse table of 10^6 ints is 80 MB)
- Avoid O(1) structures on changing data, prefix-only Fenwick minima, and over-engineering; connect LCA to RMQ over an Euler tour