🐬 Data Structures

Every data structure actually implemented and proved somewhere in this repo, organized by what it’s for, with the key operations and their cost. This is a map into deep content, not a re-explanation — see also the base data-structure catalog (arrays, lists, measured memory per element) and Types of Trees (the tree-shaped taxonomy). For the general problem-solving strategies these structures serve, see 🐬 Paradigms and 🐬 Techniques; for a single named procedure, see 🐬 Algorithms.

Linear

Structure	Supports	Note
Array	$O(1)$ index, $O(n)$ insert/erase	Data Structure Catalog
Linked list (singly/doubly/circular)	$O(1)$ insert/erase at a known node, $O(n)$ index	Data Structure Catalog
Stack / queue / deque	$O(1)$ push/pop at the relevant end(s)	Data Structure Catalog
Monotonic stack / deque	$O(1)$ amortized nearest-greater/smaller, sliding window min/max	Monotonic Stack, Two Pointers

Hash-based

Structure	Supports	Note
Hash table / set (unordered_map/gp_hash_table)	$O(1)$ expected insert/find/erase	STL Containers and Hashing
Anti-hash-test-safe hashing (splitmix64, random seed)	same, but adversary-safe	STL Containers and Hashing

Heaps

Structure	Supports	Note
Binary heap (priority_queue)	$O(\log n)$ push/pop-min, $O(1)$ top	Heaps
Leftist / pairing / skew heap	$O(\log n)$ (amortized for pairing/skew) push/pop/merge	Heaps
Radix heap	$O(1)$ push, $O(\log C)$ amortized pop-min for bounded-range weights	Heaps
Priority-queue-undo	$O(\log n)$ push/pop with rollback to any earlier state	Heaps

Union-Find

Structure	Supports	Note
DSU (union by size/rank + path compression)	$O(\alpha (n))$ amortized union/find	Disjoint Set Union
Weighted DSU	union/find plus a potential/offset per element	Disjoint Set Union
DSU with rollback	union/find + $O(1)$ undo of the last union	Disjoint Set Union
DSU on tree / small-to-large	merges child sets in $O(n\log n)$ total across the whole tree	Small to Large

Range-query structures

Structure	Supports	Note
Sparse table	$O(1)$ idempotent range query (min/max/gcd/and/or), no updates	Sparse Table
Disjoint sparse table	$O(1)$ range query for any associative (non-idempotent) op, no updates	Sparse Table
Sqrt tree	$O(1)$ query, $O(\sqrt{n})$ update for associative ops	Sparse Table
Fenwick / BIT (+ range-update variant)	$O(\log n)$ point update / prefix query (and the reverse)	Fenwick Tree
Segment tree	$O(\log n)$ point/range update, range query	Segment Tree
Lazy segment tree	$O(\log n)$ range update, range query	Lazy Propagation
Persistent segment tree	$O(\log n)$ update creating a new version, query any version	Dynamic and Persistent Segment Trees
Segment tree beats	$O(\log n)$ amortized range chmin/chmax + range sum	Segment Tree Beats
Li Chao tree	$O(\log n)$ insert a line, query the envelope at a point	Li Chao and Kinetic Segment Tree
Kinetic segment tree	maintains a changing argmin/argmax under moving linear functions	Li Chao and Kinetic Segment Tree
Wavelet tree / persistent structure for order statistics	$O(\log n)$ range $k$-th smallest, range count in $[l,r]$	Range Order Statistics
Ordered set / PBDS tree	$O(\log n)$ order-of-key, find-by-order	Ordered Set and PBDS
Chtholly tree (ODT)	$O(\log n)$ amortized range assign on randomized data	Chtholly Tree
Van Emde Boas tree / fast bitset-based sets	$O(\log \log U)$ predecessor/successor	Fast Set and Exotic Structures

Balanced search trees

Structure	Supports	Note
Treap	$O(\log n)$ expected insert/erase/split/merge, implicit-key variant for order statistics	Treaps and Balanced BSTs
Splay tree	$O(\log n)$ amortized access/insert/erase, self-adjusting	Treaps and Balanced BSTs
Implicit treap / rope	$O(\log n)$ range reverse/shift on a sequence	Treaps and Balanced BSTs

Tries

Structure	Supports	Note
String trie / Aho–Corasick	$O(\text{total length})$ build, multi-pattern matching	Trie and Aho–Corasick
Binary (bitwise) trie	$O(\log C)$ insert/erase/max-XOR query	Binary Trie
Palindromic tree (Eertree)	$O(n)$ build, one node per distinct palindromic substring	Eertree

Dynamic and advanced trees

Structure	Supports	Note
Link-cut tree	$O(\log n)$ amortized link/cut/path-query on a dynamic forest	Link-Cut Tree
Top tree	$O(\log n)$ link/cut + arbitrary path and subtree aggregation	Top Trees
Euler tour tree	$O(\log n)$ amortized link/cut + subtree aggregates on a dynamic forest	Euler Tour Tree
Kruskal reconstruction tree	$O(\log n)$ “max edge on path $\le x$” via LCA, built once	Kruskal Reconstruction Tree
Centroid tree	$O(\log n)$ depth, backbone for path-counting divide and conquer	Centroid Decomposition
Virtual (auxiliary) tree	$O(k\log n)$ total DP restricted to $k$ marked vertices	Virtual Tree
Heavy-light skeleton	$O(\log n)$ per chain hop, pairs with a segment tree for path queries	Heavy-Light Decomposition
Persistent segment tree / treap / trie	any of the above rebuilt so updates create $O(\log n)$ new nodes	Persistence

String structures

Structure	Supports	Note
Suffix array (+ LCP array)	$O(n\log n)$ or $O(n)$ (SA-IS) build, binary-searchable substrings	Suffix Array
Suffix automaton	$O(n)$ states, every distinct substring as one path	Suffix Automaton
Suffix tree	compressed trie of all suffixes, $O(n)$ via Ukkonen’s	Suffix Tree

Spatial

Structure	Supports	Note
K-d tree	$O(\sqrt{n})$ or $O(\log n)$-ish range/nearest-neighbour queries in low dimensions	KD-Tree and Spatial Structures