Sign in to watch this lesson
Advanced - Data Structures and Range Queries Ā· 5:05
DSU Extensions - Painting Offline, Distances and Parity, Arpa's Trick, Small-to-Large
Union-find only ever merges, and that one-way merging solves more than connectivity. Replaying interval assignments last to first with parent[v] = v + 1 paints every cell once; storing a parity (or a distance) on each link turns it into an online two-colouring with the link rule x ^ y ^ 1; Arpa's sweep with a monotonic stack answers range minimums offline as a[find(L)]; and pouring smaller sets into larger ones bounds every element to log n moves.
You will learn
- Paint intervals offline by replaying them in reverse with a next-unpainted DSU, and explain why union by rank must not be used
- Store parities (or distances) to the parent, update them during path compression, and link roots with parity x ^ y ^ 1 to detect odd cycles online
- Answer offline range-minimum queries with Arpa's sweep: a monotonic stack plus parent links, reading a[find(L)] when the sweep reaches R
- Merge sets small-to-large, argue the log n bound on moves per element, and apply it to distinct values in every subtree in O(n log^2 n)