Algovault

Algorithms, data structures and templates for competitive programming

• A black box you can copy easily: simple, fast, and well-tested
• C++17 for GCC, with a few in Python 3 that mostly run on PyPy too
• Built for contests like Codeforces, AtCoder and ICPC

1. Copy a file into your solution, every C++ file compiles on its own
2. Delete its main(), which only holds self-tests and a worked example
3. Read the header at the top for the API, complexity and limits

For example, a Suffix Automaton answers substring questions in three calls:

SuffixAutomaton<> sa("banana");

sa.distinct_substrings();   // 15
sa.occurrences("ana");      // 2, overlapping
sa.contains("nab");         // false

• ✔ marks a template that passes a judge test, and links to one
• ✔ next to a practice problem links an accepted solution built on the template, kept in practice/

Practice problems

• Big Integer - arbitrary precision signed integers ✔
• FFT - polynomial products, fastest for small values ✔
• Fraction - exact rational arithmetic, always reduced
• GCD and LCM Convolution - convolution over gcd(i, j) or lcm(i, j) ✔
• Lagrange Interpolation - value of a polynomial from consecutive samples ✔
• Linear Recurrence - linear recurrence of a sequence and its n-th term ✔
• Min-Plus Convolution - fast when one or both sides are convex ✔
• NTT - polynomial products, fastest modulo NTT primes ✔
• Online Convolution - terms built from a convolution of earlier ones ✔
• Polynomial - power series ops and multipoint evaluation ✔
• Subset Convolution and SOS DP - zeta and Mobius transforms, subset convolution ✔
• Walsh-Hadamard Transform - xor, or and and convolutions ✔

Practice problems

• Bell Numbers - set partition counts, also one B_n for huge n ✔
• Bernoulli Numbers - B_0..B_n modulo a prime
• Binomial Coefficients - n choose k modulo any m, prime or not ✔
• Combinatorics - factorial tables, nCr and nPr modulo a prime ✔
• Eulerian Numbers - permutations with k ascents, modulo any m
• Faulhaber's Formula - sum of k-th powers of 1..n
• Fast Factorial - n! modulo a prime p in O(sqrt(p) log p) ✔
• Gambler's Ruin - probability that the first player goes broke
• Josephus Problem - the m-th one out when every k-th person leaves ✔
• Necklaces - ring colorings up to rotation or reflection
• Partition Numbers - p(0..n) modulo any m ✔
• Permutation Cycles - cycles, k-th power and root, minimum swaps ✔
• Permutation Index - O(n) rank of a permutation, a perfect hash
• Permutation Rank - rank and unrank of permutations ✔
• Stirling Numbers - a whole row of either kind modulo m ✔

Practice problems

• Convex Hull Trick - min or max of lines added in slope order
• Coordinate Compression - replaces values with small ids
• Disjoint Set Union - merges sets and tells if two nodes share one ✔
  • Partially Persistent - connectivity and component sizes at any past time
  • Potential - differences x[b] - x[a] within each set ✔
  • Rollback - unions can be undone, for offline connectivity ✔
• Distinct Subarray Aggregates - distinct gcd/or/and of subarrays ending at i
• Euler Tour Tree - dynamic forest with subtree sums and subtree add ✔
• Fenwick Tree - point or range add with point or range sums ✔
  • 2D - the same on a grid ✔
  • 2D, Implicit - rectangle add and cell value on huge grids
  • 2D, Sparse - point add and rectangle sum on huge grids ✔
  • 3D - the same in 3D
• Hash Map - anti-hack hash table for integer keys ✔
• Interval Set - interval union with add, remove, coverage ✔
• Leftist Heap, Persistent - persistent meldable priority queue ✔
• Li Chao Tree - min or max of lines and segments at a point ✔
• Link-Cut Tree - dynamic forest with link, cut and path queries ✔
• Merge Sort Tree and Wavelet - range k-th smallest and count below x ✔
• Mo's Algorithm - offline range queries on an array ✔
  • On Tree Paths - offline path queries on a tree
  • With Rollback - state that can add but not remove ✔
  • With Updates - range queries with point assignments ✔
• Monotonic Stack - nearest smaller or greater and histogram rectangle ✔
• Ordered Set - set and multiset with k-th smallest and rank ✔
• Permutation Tree - decomposes a permutation into common intervals ✔
• Rope - persistent text, every version stays readable
• Segment Tree - range update and range query, with binary search ✔
  • 2D - point assignment and rectangle query on a grid
  • Beats - range chmin and chmax with range sum ✔
  • Merging - multisets with merge, split and k-th
  • Persistent - every version stays queryable, with k-th search ✔
  • XOR - range fold of a[p ^ x] for any x
• Sliding Window Aggregation - queue fold under any associative operation ✔
• Sparse Table - O(1) range min, max or gcd on a static array ✔
  • 2D - O(1) static rectangle min or max on a grid
  • Disjoint - O(1) query for any associative operation ✔
• Square Root Decomposition - range add and count of values below x in a range
• Treap - ordered multiset and sequence with reversals ✔
  • Run-Length Implicit - huge sequences stored as runs of equal values
• Trie - prefix counts and binary trie xor queries ✔

Practice problems

• Aliens Trick (WQS) - optimum with exactly k items for a convex cost
• Block Removal DP - max score clearing runs of equal blocks
• Bounded Knapsack - limited copies per item in O(n capacity) ✔
• Bounded Subset Sum - reachable sums of a multiset, with a witness
• CKY - context-free grammar membership
• Concave 1D1D DP - dp[x] = min dp[i] + w(i, x) for Monge w
• Divide and Conquer DP - split into k segments of minimum total cost
  • Knuth Partition DP - same split in O(n^2), faster for large k
• Garsia-Wachs - min cost to merge adjacent piles in O(n log n)
• Hamiltonian Path and Cycle - shortest Hamiltonian path and cycle ✔
• Knuth Optimization - interval DP over split points in O(n^2) ✔
• Longest Common Increasing Subsequence - LCIS and one witness in O(n m)
• Longest Increasing Subsequence - LIS and LDS with one optimal subsequence ✔
• Maximum Square - largest filled square and diamond at each cell ✔
• Plug DP - count or optimize cycles and paths on a grid
• Slope Trick - maintains a convex piecewise linear function

Practice problems

• Circle Geometry - intersections, tangents, enclosing circle, areas ✔
• Closest Pair of Points - nearest two points by exact squared distance ✔
• Convex Hull - static and online hull, Minkowski sum ✔
  • 3D - triangulated hull in space, volume and area
• Delaunay Triangulation - triangulation with empty circumcircles ✔
• Geometry - exact predicates and polygon queries ✔
• Half-Plane Intersection - convex region common to all half-planes ✔
• KD-Tree - nearest point to a query, points in a rectangle ✔
• Pick's Theorem - lattice points inside and on a polygon
• Polygon Union - area of a union of simple polygons
• Rectangle Union - area and perimeter of a union of rectangles ✔
• Segment Intersection Sweep - whether any two segments intersect

Practice problems

• 2-SAT - satisfiability with an assignment and at-most-one ✔
  • Lexicographic - satisfying assignment preferring true from x1 ✔
• 3-Edge-Connected Components - vertices joined by 3 edge-disjoint paths ✔
• Absolute Center - graph center and minimum diameter spanning tree ✔
• Articulation Points and Blocks - cut vertices, blocks and the block-cut tree ✔
• Bellman-Ford - shortest paths with negative edges and cycles ✔
• Bridges - bridges and 2-edge-connected components ✔
• Cactus Graph - cactus recognition, cycles and the cactus tree
• Chordal Graph - recognition, elimination order or induced cycle ✔
• Chromatic Number - minimum colors in a vertex coloring ✔
• Complement Graph BFS - BFS and components of the complement graph ✔
• Dijkstra - shortest paths with non-negative edges, 0-1 BFS ✔
• Directed MST - minimum arborescence from a root ✔
• Dominator Tree - immediate dominators from a root ✔
• Edge Coloring - D colors if bipartite, D + 1 for simple graphs ✔
• Euler Path - walk using every edge exactly once ✔
• Flow with Lower Bounds - circulation and s-t flow with edge lower bounds ✔
• Floyd-Warshall - all pairs shortest paths with negative cycles ✔
• General Graph Matching - maximum matching in general graphs ✔
  • Weighted - edge weights, maximizes the total weight ✔
• Global Minimum Cut - minimum cut weight and one side
• Gomory-Hu Tree - all-pairs min cuts of an undirected graph
• Hopcroft-Karp - maximum bipartite matching, O(m sqrt(n)) ✔
• Hungarian Algorithm - minimum or maximum cost assignment ✔
• Johnson's Algorithm - all-pairs shortest paths with negative edges ✔
• K Shortest Walks - lengths of the k shortest walks from s to t ✔
• Kruskal Reconstruction Tree - reachable vertices using edges of weight at most w
• Manhattan MST - minimum spanning tree under L1 distance ✔
• Matroid Intersection - largest common independent set of two matroids ✔
  • Weighted - the max weight common independent set
• Maximum Clique - max clique, max independent set, maximal cliques ✔
• Maximum Flow - max flow and min cut, with node capacities ✔
  • HLPP - push-relabel, faster where Dinic needs many phases ✔
• Min Cost Circulation - cheapest circulation with negative cycles ✔
• Min Cost Max Flow, Dijkstra - default min cost flow, with the cost slope ✔
• Min Cost Max Flow, SPFA - same as Dijkstra, without the cost slope ✔
• Minimum Mean Cycle (Karp) - exact minimum mean cycle and its edges
• Minimum Path Cover - path covers of a DAG and maximum antichain ✔
• Minimum Spanning Tree - minimum spanning forest, also implicit graphs ✔
• Network Simplex - min cost flow with supplies and lower bounds ✔
• Offline Dynamic Connectivity - connectivity under edge insertions and deletions
  • Online - answers as it goes, with component sums ✔
• Online Bridges - bridges and 2-edge components under insertions ✔
• Range Edge Dijkstra - shortest paths with edges to and from ranges
• Small Cycle Counting - counts triangles and 4-cycles
• Stable Marriage - proposer-optimal stable matching
• Steiner Tree - minimum tree connecting k terminals ✔
• Strongly Connected Components - components in topological order ✔

Practice problems

• Characteristic Polynomial - det(xI - A) modulo a prime ✔
• Determinant - determinant modulo any m, spanning tree counts ✔
• Freivalds' Algorithm - randomized check of a matrix product
• Gauss-Jordan - linear systems, rank and inverse over the reals
  • Band Matrix - grid equations that only use nearby cells
  • Bitset - the same over GF(2) ✔
  • Prime Modulus - the same modulo a prime, with kernel basis ✔
• Matrix - products and powers, modular or over a semiring ✔
• Matrix Permanent - permanent modulo any m, or exact
• Simplex - linear programming
• Thomas Algorithm - tridiagonal linear systems in O(n)
• XOR Basis - max xor, k-th xor and span intersection ✔

Practice problems

• All Divisors - divisor lists of every number up to a limit
• Chinese Remainder Theorem - systems of congruences with any moduli ✔
• Continued Fractions - best rational approximation, Stern-Brocot search ✔
• Digits of Factorial - number of digits of n! in any base
• Discrete Logarithm - smallest x with a^x = b mod m, any m ✔
• Divisors - sorted divisors of one number
• Du's Sieve - prefix sums of phi and mu in O(n^(2/3)) ✔
• Extended GCD - modular inverse, linear diophantine equations ✔
• Fast Fibonacci - n-th Fibonacci number by fast doubling ✔
• Fast Prime Counting - count of primes up to n in sublinear time ✔
• Fast Prime Sums - sum of primes up to n in sublinear time
• Fast Sieve - lists all primes up to n ✔
• Floor Sum - floor sums and minima of (a i + b) mod m ✔
• Integer Root - exact floor of square, cube and k-th roots ✔
• Linear Sieve - smallest prime factors, phi, mu and more
• Maximum Divisors - number with the most divisors up to a limit
• Miller-Rabin - deterministic primality test for 64-bit integers ✔
• Min_25 Sieve - prefix sums of a multiplicative function ✔
• Mobius Function - Mobius mu for 1..n at 1 byte per entry
• Modular Roots - k-th roots modulo a prime, primitive root ✔
• Modular Square Root - Tonelli-Shanks square root modulo a prime ✔
• Pell Equation - solutions of x^2 - d y^2 = 1 or -1, also mod m
• Pisano Period - period of Fibonacci numbers modulo n
• Pollard Rho - factorization and primality below 2^63 ✔
• Power Tower - a1^(a2^(...^an)) modulo m ✔
• Segmented Sieve - primes in a window [L, R] far from zero ✔
• Sum of Two Squares - every x^2 + y^2 = n up to 2^63 ✔

Practice problems

• Dinkelbach Fractional Programming - optimal ratio a(x) / b(x) over a set of choices
• Local Minimization - minimum of a function of a few real variables
• Numerical Integration - definite integrals by Simpson, Gauss or Romberg
• Simulated Annealing - generic randomized minimizer
• Ternary and Golden-Section Search - integer argmax of a unimodal function, real argmin

Practice problems

• 2D Pattern Matcher - every occurrence of a 2D pattern in a 2D text ✔
• Aho-Corasick - multi-pattern matching automaton ✔
• Hirschberg LCS - one longest common subsequence in linear memory ✔
  • Dynamic - patterns can be inserted online
• Bit-String LCS - longest common subsequence in O(n m / 64) ✔
• De Bruijn Sequence - cyclic sequence containing every length n word
• Dynamic String Hash - substring hashes under range assignment ✔
• Hashing - forward and reverse polynomial hash of any segment ✔
• Hunt-Szymanski - LCS in O((r + n) log n) for r matching pairs ✔
• KMP - prefix function and pattern search ✔
• Lyndon Factorization - splits a sequence into Lyndon words ✔
• Manacher - longest palindrome at every center ✔
• Minimum Rotation - start of the lexicographically smallest rotation
• Palindromic Tree - eertree, one node per distinct palindrome ✔
• Subsequence Automaton - next occurrence table, distinct subsequences ✔
• Suffix Array - O(n) suffix array with LCP and pattern search ✔
• Suffix Automaton - substring counts and longest common substring ✔
• Tandem Repeats - every tandem repeat (square) in a string ✔
• Wildcard Matching - matching with wildcards in text or pattern ✔
• Z Algorithm - LCP of every suffix with the string ✔

Practice problems

• Centroid Decomposition - centroid tree with distances to each centroid ✔
• DSU on Tree - small-to-large answers for every subtree
• Dynamic Tree Diameter - tree diameter under edge weight updates ✔
• Heavy Light Decomposition - tree paths and subtrees as array ranges ✔
• Long-Path Decomposition - depth-indexed subtree DP and O(1) k-th ancestor ✔
• Lowest Common Ancestor - LCA, distance, jumps and path folds on a tree ✔
• Prufer Code - converts labeled trees to and from sequences
• Rerooting DP - a tree DP with every node as the root ✔
• Tree Isomorphism - canonical ids for rooted and unrooted trees ✔
• Virtual Tree - compresses a tree to k vertices and their LCAs

Practice problems

• Anti Double Hash - two strings colliding under a double hash
• Anti Polynomial Hash - two strings colliding under a polynomial hash

Practice problems

• 15 Puzzle Solver - solvability check and IDA* solver
• Assembly - inline x86 bit ops, gcd and square root ✔
• Bit Twiddling - bit manipulation tricks ✔
• Comb Sort - comb sort on any random access range ✔
• Dancing Links - exact cover with Algorithm X ✔
• Fast I/O - fast buffered input and output ✔
• Gray Codes - Gray code and its inverse
• Hackenbush - green values on graphs, red-blue on trees
• Knight Distance - fewest knight moves on an infinite board in O(1)
• N Queens - number of N queens solutions
• Next Palindrome - smallest palindromic number above a given one
• Nimber Arithmetic - nim product and inverse over GF(2^64) ✔
• Radix Sort - LSD radix sort of 32-bit integers ✔
• Radix Sort 64 - LSD radix sort of 64-bit integers ✔

Practice problems

• Alpha Beta Pruning - minimax game search with alpha-beta pruning
• Berlekamp-Massey - shortest linear recurrence and its n-th term
• Derangements - generalized derangement counts
• Dijkstra - single-source shortest paths
• Discrete Log - smallest x with a^x = b mod m, any m
• Fast Fibonacci - n-th Fibonacci number by fast doubling
• Fast I/O - token scanner over stdin
• General Graph Matching - maximum matching size in a general graph
• Lagrange Interpolation - value of a polynomial from any samples
• Miller-Rabin - deterministic primality test for 64-bit integers
• N Queens - number of N queens solutions
• Sieve - primes up to n by Eratosthenes
• String Hash - polynomial substring hashes
• Z Algorithm - LCP of every suffix with the string

Every template is checked four ways:

• Self and stress tests: GCC 14
  • -fsanitize=address,undefined: AddressSanitizer and UndefinedBehaviorSanitizer
  • an 8 MB stack, as on most judges
  • -Werror: warnings as errors
• Judge tests: -O2, like a judge

• Every push: the self, stress and judge tests of the files it changes, plus the repo checks
• Every night: all self and stress tests, then the stress tests again at 20x the iterations with a fresh seed
• Every week: all judge tests from scratch

The commands to run everything locally are in CONTRIBUTING.md.

• Bug reports, fixes and new templates are welcome as issues or pull requests, see CONTRIBUTING.md for the conventions and the checks CI runs
• The skills in .claude/skills/ apply them:
  • /crucible adds or refactors a template
  • /lucid keeps the docs consistent

MIT, see LICENSE