Data Structures
Structures that answer range queries and maintain sets under updates in logarithmic time.
10 articles~85 min total
0/10
Fundamentals
- Minimum Stack and Minimum QueueKeep the minimum of a stack or a queue available in O(1), and find the minimum of every window of fixed length in O(n).6 minIntermediate
- Sparse TableAnswer range-minimum (and other idempotent) queries in O(1) after O(n log n) preprocessing, for arrays that never change.5 minIntermediate
Trees
- Disjoint Set Union (Union-Find)Maintain a partition of elements into sets with near-constant-time merge and find, using path compression and union by size.9 minIntermediate
- Fenwick Tree (Binary Indexed Tree)Prefix sums with point updates in O(log n) using a tiny array, plus range updates and finding the k-th element.9 minIntermediate
- Segment TreeAnswer range queries (sum, min, max, gcd, ...) and point updates in O(log n), then add lazy propagation for range updates.12 minAdvanced
- Sqrt Decomposition and Mo's AlgorithmSplit an array into blocks of size about √n to balance updates and queries, and answer offline range queries by ordering them cleverly (Mo's algorithm).9 minAdvanced
- Treap (Cartesian Tree)A binary search tree kept balanced by random priorities, built on two operations, split and merge; includes the implicit treap for array-like sequences.13 minAdvanced
- Randomized HeapA mergeable priority queue in about ten lines: merge two heaps by a random walk, and get insert and extract-min in expected O(log n).6 minIntermediate
- Sqrt TreeAnswer range queries for any associative operation in O(1) after O(n log log n) preprocessing, by applying sqrt decomposition recursively.7 minAdvanced