Pick the structure that makes the operation you repeat cheapest. The full catalog has a one-line “when to use” for every structure in this wiki.
Linear and Basic
- General — array, linked list, stack, queue, deque, hash table
- Sorting — every comparison and non-comparison sort
- Array and Matrix Techniques — rotation, transposition, in-place patterns
- Prefix Sum · Difference Array
- Monotonic Stack · Monotonic Queue
- Minimum Stack and Queue
- STL Containers Cheatsheet
Trees and Range Structures
- Segment Tree · Lazy Propagation
- Fenwick Tree (BIT) · 2D Fenwick and 2D Segment Tree
- Sparse Table · Disjoint Sparse Table
- Square Root Decomposition
- Merge Sort Tree
- Segment Tree Beats
- Li Chao Tree
- Wavelet Tree
Balanced BSTs and Heaps
- Binary Heap / Priority Queue
- Advanced Heaps — pairing, Fibonacci, leftist, skew, meldable
- Balanced BSTs — AVL, red-black, splay, scapegoat
- Treap and Implicit Treap
- Ordered Set / PBDS
Disjoint Sets
- Disjoint Set Union
- DSU Variants — rollback, persistent, weighted, bipartite
Tree Decompositions
- Heavy-Light Decomposition
- Centroid Decomposition
- Virtual Tree
- Link-Cut Tree
- Euler Tour Tree
- DSU on Tree (Small to Large)
Strings and Bits
- Trie · Binary Trie
- Suffix Array · Suffix Automaton · Suffix Tree
- Palindromic Tree (Eertree)
- Linear / XOR Basis
Persistence
- Persistent Data Structures — segment tree, trie, DSU, array
Geometric
- KD-Tree
- Other Geometric Structures — quadtree, R-tree, interval tree, range tree, BVH
Exotic and Theoretical
- Exotic Structures — van Emde Boas, x/y-fast trie, fusion tree, tango tree, soft heap