Chapter 8
Data Structures on Trees
The five structures in this chapter appear in the majority of graph problems that are not purely graph-theoretic. Know them cold: the code below is the code you type in a contest.
6 pages4,407 words17 problems2 interactive
1Binary Heap and priority_queueThe array-shaped tree, why it is fast in practice, and the six uses beyond Dijkstra.2Disjoint Set Union (Union–Find)Two heuristics, one inverse-Ackermann bound, and the offline tricks that make it a problem-solving tool rather than a data structure.3Fenwick Tree (Binary Indexed Tree)Prefix sums in one loop, with the two-line tricks for range updates and "find smallest index with prefix ≥ x".4Segment TreeOne combining function, three shapes (plain, lazy, persistent), and the invariant that makes every variant obvious.5Trie (Prefix Tree) and Its RelativesBitwise tries, binary tries for xor, suffix automaton neighbours, and the Aho–Corasick step up.6Sparse Table and RMQO(1) range minimum queries on idempotent operations, with the log table that makes the proof two lines.