📚 Data Structure Catalog

Every structure in this wiki, with a one-line “reach for this when…”.

Linear

Structure	When
Array / vector	indexed access, cache locality, the default
Linked list	$O(1)$ splice at a known node; rarely worth it
Stack	LIFO; recursion, bracket matching, DFS
Queue	FIFO; BFS, scheduling
Deque	both ends; 0-1 BFS, sliding windows
Hash table	$O(1)$ lookup, order irrelevant
Prefix sum	static range sums in $O(1)$
Difference array	many range adds, one final read
Monotonic stack	next/previous greater or smaller
Monotonic queue	sliding window min/max
Minimum stack/queue	minimum under arbitrary push/pop

Range query

Structure	When
Sparse table	static, idempotent op, $O(1)$ query
Disjoint sparse table	static, any associative op, $O(1)$ query
Fenwick tree	point update, prefix sum; shortest code
Segment tree	any associative op with updates
Lazy segment tree	range updates too
Segment tree beats	chmin/chmax range updates
Sqrt decomposition	operations a segment tree cannot merge
Merge sort tree	count elements $\le x$ in a range, no updates
Wavelet tree	range $k$-th smallest in $O(n\log C)$ bits
Li Chao tree	minimum over a set of lines at a point
2D BIT / segment tree	grid queries on a dense small grid

Sets and priority

Structure	When
Binary heap	always need the minimum; Dijkstra
Meldable heaps	merging heaps cheaply
Balanced BST (set/map)	ordered, predecessor/successor
PBDS `tree`	$k$-th smallest and rank
Treap	a BST you need to extend
Implicit treap	insert/erase/reverse inside a sequence

Disjoint sets

Structure	When
DSU	merging only; components, Kruskal
Rollback DSU	offline dynamic connectivity
Parity DSU	bipartiteness, relative constraints

Trees

Structure	When
Binary lifting	LCA, $k$-th ancestor, path aggregates (no updates)
Euler tour + BIT	subtree queries and updates
HLD	path queries and updates on a static tree
Centroid decomposition	counting over all paths
Virtual tree	many queries over small vertex subsets
DSU on tree	offline subtree aggregate queries
Link-cut tree	online link/cut with path queries
Euler tour tree	online link/cut with subtree queries

Strings and bits

Structure	When
Trie	prefix queries, autocomplete
Binary trie	maximum XOR with a query value
XOR basis	maximum XOR over all subsets
Suffix array + LCP	substring queries, low memory
Suffix automaton	all substrings, online, 30 lines
Eertree	all palindromic substrings
Aho-Corasick	many patterns at once
bitset	boolean DP, set operations, $/64$ speedup

Persistence and geometry

Structure	When
Persistent segment tree	range $k$-th, historical versions
KD-tree	nearest neighbour, online geometric queries
Quadtree / R-tree / BVH	spatial data with extent

Exotic

Structure	When
van Emde Boas, y-fast trie	predecessor in $O(\log \log U)$
Fusion tree	word-RAM predecessor search
Soft heap	$O(1)$ ops with bounded corruption

---

The decision tree

Do the queries involve ranges of an array?
├─ no updates, idempotent op   -> sparse table
├─ no updates, k-th smallest   -> persistent segtree / wavelet tree
├─ point update, prefix sum    -> Fenwick tree
├─ range update, range query   -> lazy segment tree
├─ chmin/chmax updates         -> segment tree beats
├─ weird un-mergeable op       -> sqrt decomposition
└─ offline                     -> Mo's algorithm, or a BIT sweep

Do they involve a tree?
├─ subtree                     -> Euler tour + BIT
├─ path, static tree           -> HLD (or binary lifting if read-only)
├─ all paths, counting         -> centroid decomposition
├─ small vertex subsets        -> virtual tree
└─ tree changes online         -> link-cut tree

Sets that merge?              -> DSU (rollback if you need undo)
Need the k-th smallest?        -> PBDS, or a BIT over values
Maximum XOR?                   -> binary trie (element) / XOR basis (subset)
Strings?                       -> suffix automaton, or hashing

See also: Data Structures · Range Query Techniques · Complexity Cheatsheet