Data Structures · Cluster
Union-Find and Succinct Structures
Disjoint sets, bitsets, and space-efficient indexes.
- 01 Parent-Pointer Forests as the Representation of Disjoint Sets How a partition of n elements is stored as a single array of parent indices, what find and union do to that array, and which questions the representation cannot answer.
- 02 Union by Rank and Path Compression: Two Heuristics That Fix the Chain How attaching the smaller tree under the larger bounds forest height, how rewriting parent links during a find flattens future traversals, and why the two heuristics must be analysed together.
- 03 The Inverse Ackermann Bound and Why It Is Effectively Constant How the α(n) function is defined, why the amortized cost of a disjoint-set sequence lands there, and what the matching lower bound says about improving it.
- 04 Cache Behaviour and Node Layout in Disjoint-Set Arrays Why a find is a dependent-load chain, how index width and array splitting change the number of cache lines touched, and what key remapping costs before the first union.
- 05 Small-to-Large Merging and the DSU on Tree Technique Why merging the smaller container into the larger bounds total moves to n log n, and how the same accounting answers subtree queries by reusing one mutable structure.
- 06 Rollback Union-Find and Offline Dynamic Connectivity How to undo a union by recording only the parent slot it overwrote, and how a segment tree over time turns edge insertions and deletions into a stack of reversible merges.
- 07 Bitset Representation and Word-Level Rank and Select How a bitvector is stored as words, how popcount turns a prefix count into a handful of instructions, and what the two-level directories for rank and select cost in bits per element.
- 08 Elias-Fano Encoding for Monotone Integer Sequences How splitting each value into a high and a low part turns a sorted sequence into one bitvector plus a packed array, and why this beats a plain array for prefix queries.
- 09 Wavelet Trees and Range Queries on Sequences How recursive bitvector partitioning answers range counting, quantile, and rank queries on a static sequence, and why the space is n log σ bits rather than an index per value.
- 10 Balanced Parentheses and Succinct Tree Navigation How a tree becomes a 2n-bit parentheses string, which rank and select combinations recover the parent and subtree boundaries, and what the extra index buys.