🐬 Templates

All templates live in whoashish115/cp-template — every file is one complete, submittable C++20 program (dependencies pasted in, empty solve(), main()). Pick the file, write solve(), submit.

• Usage, complexity and pitfalls of every file: NOTES.md
• Blank base template: main.cpp
• ICPC team notebook (25 pages): notebook/
• Bundled libraries: AtCoder Library, KACTL
• Every template compiles cleanly with g++ -std=c++20 -Wall (434/434 checked).

Which template?

Problem looks like	File
range sum / point update	range-queries/fenwick.cpp, segment-tree.cpp
range update + range query (add, assign, min, sum)	range-queries/lazy-segment-tree.cpp (iterative: -iterative)
static range min / gcd, O(1) query	range-queries/sparse-table.cpp, disjoint-sparse-table.cpp, linear-rmq.cpp
chmin / chmax on ranges	range-queries/segment-tree-beats.cpp
k-th smallest in range, count < x in range	range-queries/wavelet-matrix.cpp, merge-sort-tree.cpp, persistent-segment-tree.cpp
distinct values in range, offline queries	range-queries/distinct-in-range.cpp, mo.cpp, mo-with-updates.cpp, mo-rollback.cpp
2D sums / rectangles	range-queries/fenwick-2d.cpp, segment-tree-2d.cpp, basics/prefix-sums.cpp, geometry/rectangle-union.cpp
connectivity / merging sets	data-structures/dsu.cpp, dsu-rollback.cpp, offline-dynamic-connectivity.cpp, weighted-dsu.cpp
ordered set with k-th / rank	data-structures/ordered-set.cpp (pbds), treap.cpp, avl-tree.cpp
array with insert / reverse / split	data-structures/treap.cpp (implicit), splay-tree.cpp, pbds-heap-rope.cpp
interval assign (“Chtholly”)	data-structures/interval-set.cpp
max xor pair / subset xor	data-structures/binary-trie.cpp, linear-algebra/xor-basis.cpp
shortest path	graphs/bfs.cpp (0-1 BFS too), dijkstra.cpp, bellman-ford.cpp, spfa.cpp, floyd-warshall.cpp, johnson.cpp
MST	graphs/kruskal.cpp, prim.cpp, boruvka.cpp, directed-mst.cpp, geometry/manhattan-mst.cpp
SCC / 2-SAT / bridges / articulation	graphs/scc.cpp, two-sat.cpp, bridges-articulation.cpp, biconnected-components.cpp
Euler path, cycle finding, toposort	graphs/euler-path.cpp, find-cycle.cpp, topological-sort.cpp
matching / flow / assignment	flows/hopcroft-karp.cpp, dinic.cpp, min-cost-flow.cpp, hungarian.cpp, general-matching.cpp
min cut / project selection	flows/dinic.cpp (cut), max-closure.cpp, global-min-cut.cpp, gomory-hu.cpp
LCA, k-th ancestor, path queries	trees/lca-binary-lifting.cpp, lca-rmq.cpp, hld.cpp, ladder-kth-ancestor.cpp
subtree queries, small-to-large	trees/dsu-on-tree.cpp, rerooting.cpp, tree-knapsack.cpp, virtual-tree.cpp
paths of given length / distances in tree	trees/centroid-decomposition.cpp, distance-counting.cpp, centroid-queries.cpp
dynamic tree (link / cut)	trees/link-cut-tree.cpp, euler-tour-tree.cpp, top-tree.cpp
LIS / LCS / edit distance / knapsack	dp/lis.cpp, lcs.cpp, edit-distance.cpp, knapsack.cpp, classic-dp.cpp
DP speedups	dp/convex-hull-trick.cpp, li-chao-tree.cpp, divide-and-conquer-dp.cpp, knuth-optimization.cpp, aliens-trick.cpp, slope-trick.cpp, monotone-1d1d.cpp
digits / bitmask / profile DP	dp/digit-dp.cpp, tsp.cpp, sos-dp.cpp, broken-profile-dp.cpp, plug-dp.cpp
pattern matching	strings/prefix-function.cpp, z-function.cpp, string-hashing.cpp, aho-corasick.cpp, wildcard-matching.cpp
substrings / suffixes	strings/suffix-array.cpp, suffix-automaton.cpp, suffix-tree.cpp
palindromes	strings/manacher.cpp, palindromic-tree.cpp, palindrome-factorization.cpp
primes, divisors, phi, mobius	number-theory/sieve.cpp, factorization.cpp, basic-number-theory.cpp, segmented-sieve.cpp
sums over floor(n / i), prime sums	number-theory/quotient-blocks.cpp, du-sieve.cpp, min25-sieve.cpp, prime-counting.cpp
modular equations	number-theory/crt.cpp, extended-gcd.cpp, discrete-log.cpp, mod-sqrt.cpp, primitive-root.cpp
nCr mod p / any m, Lucas, Catalan	combinatorics/binomial.cpp, lucas.cpp, binomial-any-mod.cpp
counting with symmetry / partitions	combinatorics/burnside-lgv.cpp, stirling-bell-partitions.cpp, polynomial/counting-series.cpp
convolution / polynomials	polynomial/ntt.cpp, fft.cpp (any mod), poly.cpp (inv, log, exp, sqrt, eval)
linear recurrence, k-th term	polynomial/linear-recurrence.cpp, bostan-mori.cpp, berlekamp-massey.cpp, linear-algebra/matrix.cpp
xor / and / or convolution	polynomial/bitwise-convolution.cpp, fwht-any-base.cpp
linear systems, determinant, rank	linear-algebra/gaussian-elimination.cpp, determinant.cpp, gauss-xor.cpp, matrix-tree.cpp
LP	linear-algebra/simplex.cpp
games	game-theory/sprague-grundy.cpp, retrograde.cpp, hackenbush.cpp, game-search.cpp
geometry	geometry/point.cpp, lines-segments.cpp, polygon.cpp, convex-hull.cpp, circle.cpp, half-plane-intersection.cpp
successor / functional graph, k-th successor, cycles	graphs/functional-graph.cpp
grid BFS, flood fill, path letters, 0-1 BFS on grid	graphs/grid.cpp
path / subtree add + sum / max on a tree (one file)	trees/hld-path-queries.cpp
second-best MST, MST forced to use an edge	graphs/second-best-mst.cpp
max / min xor walk between vertices	graphs/xor-paths.cpp
which sums of coins are representable (huge H)	graphs/residue-shortest-path.cpp
is this degree sequence a graph / bipartite / tournament	graphs/degree-sequence.cpp
DAG path cover, max antichain (Dilworth)	flows/path-cover.cpp
exact cover, Sudoku, tilings	basics/dancing-links.cpp, backtracking-puzzles.cpp
subsequence checks / distinct subsequences	strings/subsequence-automaton.cpp
lattice paths with obstacles / reflections	combinatorics/lattice-paths.cpp, special-numbers.cpp
f(g(x)), series reversion	polynomial/poly-composition.cpp
shortest walk with exactly k edges	linear-algebra/min-plus-matrix.cpp
historic max, lines rising over time	range-queries/segment-tree-history.cpp, kinetic-segment-tree.cpp
compare multisets of subarrays, “is a permutation”	misc/set-hashing.cpp
modulus above 2^31	number-theory/modint64.cpp, fast-mod.cpp
more geometry	geometry/polygon-union.cpp, circle-union.cpp, delaunay.cpp, kd-tree.cpp, angular-sweep.cpp, segment-in-polygon.cpp, convex-distance.cpp, planar-faces.cpp, circle-inversion.cpp
interactive	contest/interactive.cpp (+ basics/binary-search.cpp)
huge numbers / fractions / dates	misc/bigint.cpp, fraction.cpp, dates.cpp, contest/int128-io.cpp
exact i64 convolution, convolution mod 1e9+7 / any m	polynomial/ntt.cpp (convolutionLL, convolutionAnyMod)
gcd / lcm convolution	dp/divisor-transforms.cpp
min / max of (a x + b) mod m, first x landing in [l, r]	number-theory/mod-linear.cpp
n! mod p for n up to 1e9, many such queries	number-theory/fast-factorial.cpp
count squarefree numbers up to 1e18	number-theory/squarefree-count.cpp
deque with fold (push / pop both ends)	basics/sliding-window.cpp (AggregateDeque)
range mode, range LIS, range sort	range-queries/range-mode.cpp, range-lis.cpp, sortable-segment-tree.cpp
rectangle add / rectangle sum offline	range-queries/offline-rectangle.cpp
unite a + i ~ b + i for a whole range of i	data-structures/dsu.cpp (RangeParallelDSU)
potentials in a non-commutative group	data-structures/weighted-dsu.cpp (GroupDSU)
tree DP with point updates	trees/static-top-tree.cpp
sum over vertices at distance in [lo, hi]	trees/centroid-queries.cpp (ContourSum)
when does an edge join a cycle (edges added online)	graphs/incremental-scc.cpp
treewidth <= 2 / series-parallel DP	graphs/treewidth-2.cpp
max independent set, all cliques	graphs/max-clique.cpp, maximal-cliques.cpp
matroid partition, weighted matroid intersection	flows/matroid-intersection.cpp
distinct substrings of s[l..r)	strings/distinct-substrings-in-range.cpp
LCS of a with every substring of b	strings/lcs-variants.cpp (seaweedKernel)
sparse series inv / exp / log / pow / sqrt	polynomial/sparse-fps.cpp
set power series exp / log	polynomial/bitwise-convolution.cpp
interpolation on a geometric sequence, Newton form	polynomial/chirp-z.cpp, newton-basis.cpp
points of B inside triangles of A	geometry/points-in-triangle.cpp
line vs convex polygon, exact angles	geometry/convex-polygon-queries.cpp, angular-sweep.cpp
Stern-Brocot path / LCA / ancestor	number-theory/continued-fractions.cpp
stone merging (adjacent piles), alphabetic tree	dp/knuth-optimization.cpp (garsiaWachs)
largest subset sum <= t, small weights, huge t	dp/subset-sum.cpp (maxSubsetSumAtMost)

All templates

basics/ — searching, sorting, two pointers, prefix sums, greedy, backtracking

#	Template	What it does	Notes
1	array-classics.cpp	Array Classics. Boyer-Moore majority vote (and Misra-Gries for > n/k), Dutch national flag partition, and reservoir sampling	Majority Element
2	backtracking-puzzles.cpp	Backtracking Puzzles (Sudoku, knight’s tour, maze paths, word search). Bitmask Sudoku solver, Warnsdorff knight’s tour, counting simple paths in a grid maze, and word search on a letter grid	Backtracking Puzzles
3	backtracking.cpp	Backtracking and Exhaustive Generation. N-Queens with bitmasks, and generation of all subsets, k-combinations and permutations as index lists	Backtracking
4	binary-search.cpp	Binary Search. First/last integer where a monotone predicate holds, unbounded search, and real-valued bisection	Binary Search
5	bit-tricks.cpp	Bit Tricks. Bit counting helpers, submask/supermask enumeration, Gosper’s next combination, Gray code and bit reversal	Bit Operations
6	coordinate-compression.cpp	Coordinate Compression. Maps arbitrary sortable values to ranks 0..k-1, preserving order	Coordinate Compression
7	dancing-links.cpp	Dancing Links (Algorithm X, exact cover). Chooses rows of a 0/1 matrix so that every column is covered exactly once; finds one solution or counts all of them	Dancing Links
8	greedy-classics.cpp	Greedy Classics (intervals, Huffman, deadlines, fractional knapsack)	Greedy
9	kadane.cpp	Kadane’s Maximum Subarray. Maximum-sum non-empty subarray with its bounds, the circular variant, and the maximum-sum submatrix	Kadane
10	meet-in-the-middle.cpp	Meet in the Middle (Subset Sums). Sorted list of all subset sums, and counting / best subset sums against a bound by splitting the set in half	Meet in the Middle
11	merge-sort-inversions.cpp	Merge Sort and Inversion Count. Stable bottom-up merge sort that also counts inversions (pairs i < j with a[j] < a[i])	Inversions
12	monotonic-stack.cpp	Monotonic Stack. Nearest smaller/greater element to the left and right of every position, and the largest rectangle in a histogram	Monotonic Stack
13	prefix-sums.cpp	Prefix Sums and Difference Arrays. 1D/2D prefix sums for static range sums and 1D/2D difference arrays for offline range additions	Prefix Sums
14	radix-sort.cpp	Radix Sort. Stable LSD radix sort (8 bits per pass) for integers and for any records with an unsigned integer key	Sorting
15	searching.cpp	Searching in Sorted Arrays (linear, jump, interpolation, exponential). The classic search variants on a sorted array, each returning an index of x or -1	Searching
16	sliding-window.cpp	Sliding Window Aggregates. Min/max of every length-k window with a monotone deque, and a two-stack queue that aggregates any associative operation	Two Pointers
17	sorting.cpp	Sorting Algorithms (counting, merge, quick 3-way, heap, insertion, shell, bucket) and Quickselect	Sorting
18	ternary-search.cpp	Ternary Search. Minimum of a unimodal function over an integer range or a real interval (ternary and golden-section)	Ternary Search
19	two-pointers.cpp	Two Pointers	Two Pointers

combinatorics/ — binomials, special numbers, counting under symmetry

#	Template	What it does	Notes
1	binomial-any-mod.cpp	Binomial Coefficients Modulo Any Integer. C(n, k) modulo an arbitrary m for n, k up to 1e18, via generalized Lucas modulo each prime power of m and CRT	Binomial Mod m
2	binomial-sums.cpp	Sums of Binomial Coefficients. Prefix sums of a row C(n, 0..k) (single and many offline queries), and sums over a residue class sum_{i = r mod m} C(n, i)	Binomial Sums
3	binomial.cpp	Binomial Coefficients	Combinatorics
4	bounded-compositions.cpp	Bounded Compositions (stars and bars with upper bounds)	Stars and Bars
5	burnside-lgv.cpp	Burnside / Polya Counting and the LGV Lemma. Orbits under a permutation group (necklaces, bracelets, any explicit group) and non-intersecting lattice paths as a determinant	Burnside
6	graph-counting.cpp	Counting Labeled Graphs, Connected Graphs, DAGs, Trees and Forests. Tables of the numbers of labeled graphs on n vertices that are arbitrary, connected, acyclic directed, trees, rooted forests	Graph Counting
7	lattice-paths.cpp	Lattice Path Counting (obstacles, ballot / Catalan, reflection between two lines)	Lattice Paths
8	lucas.cpp	Lucas’s Theorem. C(n, k) modulo a small prime p for n, k up to 1e18 by multiplying the binomials of the base-p digits	Lucas Theorem
9	permutation-group.cpp	Permutation Groups (Schreier-Sims), k-th Roots of Permutations, Factoradic Encoding. Order of and membership in the group generated by permutations; a q with q^k = p; bijection between permutations and [0, n!)	Permutation Groups
10	q-binomial.cpp	q-Binomial (Gaussian) Coefficients. [n choose k]_q modulo a prime: number of k-dimensional subspaces of F_q^n (q a prime power), or the q-analogue for any q	q-Binomial
11	rsk.cpp	Robinson-Schensted-Knuth Correspondence (Young tableaux)	Robinson-Schensted-Knuth
12	special-numbers.cpp	Special Number Sequences (Eulerian, Narayana, Motzkin, Schroder, Delannoy, Lah, Fubini, restricted partitions). Tables and closed forms of the counting sequences that show up behind many combinatorics problems	Special Numbers
13	stirling-bell-partitions.cpp	Stirling Numbers, Bell Numbers, Partitions and Derangements. Tables of Stirling numbers of both kinds, Bell numbers, integer partition numbers p(n) and derangements over any ring type	Stirling and Bell

contest/ — contest setups and tooling

#	Template	What it does	Notes
1	codejam.cpp	Code Jam / Kick Start / Hacker Cup Output Format. Multi-test template that prints “Case x: ” before every answer	Fast I/O
2	fast-io.cpp	Fast Input/Output. Buffered fread/fwrite reader and writer for integers (including __int128), strings, characters and lines	Fast I/O
3	file-io.cpp	File Input / Output (USACO, old judges). Reads NAME.in and writes NAME.out when they exist, otherwise falls back to stdin / stdout	Fast I/O
4	int128-io.cpp	128-bit Integer I/O. Reads and prints __int128 / unsigned __int128 with the ordinary iostream operators	Fast I/O
5	interactive.cpp	Interactive Problem Template. Query/answer helpers that flush, count queries and can be switched to an in-process stub judge for local testing	Interactive
6	multithreaded.cpp	Multithreaded Test Cases (tourist style, for offline rounds). Reads all tests, solves them in parallel threads and prints the answers in order	Fast I/O
7	pragmas.cpp	Base Template with Optimization Pragmas	Contest Template
8	random.cpp	Test Data Generator	Stress Testing
9	stress/brute.cpp	Stress kit: brute force. Brute force for stress.cpp: the simplest obviously-correct solution (try everything), same input format	Stress Testing
10	stress/checker.cpp	Stress kit: checker	Stress Testing
11	stress/gen.cpp	Stress kit: generator	Stress Testing
12	stress/stress.cpp	Stress kit: runner	Stress Testing

data-structures/ — DSU, balanced trees, heaps, tries, persistent and hash structures

#	Template	What it does	Notes
1	avl-tree.cpp	AVL Tree (balanced BST with order statistics). Height-balanced binary search tree: insert, erase, contains, k-th smallest, rank; duplicates allowed	Balanced BST
2	binary-trie.cpp	Binary Trie (XOR Trie). Multiset of non-negative integers as a bitwise trie: min/max xor with a value, k-th smallest of x xor v, count of x xor v < k	Binary Trie
3	cartesian-tree.cpp	Cartesian Tree. O(n) stack construction of the min-rooted (or any comparator) Cartesian tree of an array	Cartesian Tree
4	dsu-partially-persistent.cpp	Partially Persistent DSU. Union-find that remembers the time of every merge, so connectivity and sizes can be asked for any past time	Disjoint Set Variants
5	dsu-rollback.cpp	DSU with Rollback. Union-find that can undo merges in LIFO order, for offline DFS over versions or time	Disjoint Set Variants
6	dsu.cpp	Disjoint Set Union (Union-Find). Maintains a partition of {0..n-1} under merging, with component sizes	Disjoint Set Union
7	dynamic-bitset.cpp	Dynamic Bitset. Bitset with run-time size, range set/reset/flip/count, next/previous set bit, shifts and logic ops	Bitset
8	fast-set.cpp	Fast Set (64-ary Bitset Tree). Set of integers in [0, n) with insert, erase, contains, next (first >= x) and prev (last <= x) in O(log_64 n)	Fast Set
9	hash-map.cpp	Hash Map with Anti-Hack Hash. Splitmix64 hash with a random seed for unordered_map / unordered_set / gp_hash_table, safe against anti-hash tests	Hash Maps
10	hash-table-bloom.cpp	Hand-written Hash Table (open addressing) and Bloom Filter. Fast fixed-capacity hash map from u64 keys with linear probing, and a Bloom filter for approximate membership	Hash Table
11	interval-set.cpp	Interval Set (Chtholly Tree / ODT). Array stored as maximal runs of equal values in a std::map, with range assign and visiting the runs of a range	Chtholly Tree
12	median-heap.cpp	Running Median (two heaps) and Sliding Window Median. Median of a growing stream, and the median of every window of size k	Running Median
13	meldable-heap.cpp	Meldable Heap (Leftist Heap). Many priority queues in one node pool that can be merged in O(log n): push, top, pop and meld	Advanced Heaps
14	offline-dynamic-connectivity.cpp	Offline Dynamic Connectivity. Connectivity under edge insertions and deletions known in advance: segment tree over time + rollback DSU	Dynamic Connectivity
15	ordered-set.cpp	Ordered Set (PBDS Order-Statistics Tree). Balanced BST with k-th element and rank queries: ordered set, ordered map and ordered multiset	Ordered Set
16	pbds-heap-rope.cpp	GNU Extensions: Pairing Heap and Rope. __gnu_pbds priority queue with modify/erase/join through iterators, and __gnu_cxx::rope (persistent-ish sequence)	Rope
17	persistent-array.cpp	Persistent Array. Array with versions: reading any version and writing (which creates a new version) in O(log n)	Persistence
18	persistent-dsu.cpp	Persistent DSU. Union-find where every merge creates a new version and any old version can be queried or merged again	Disjoint Set Variants
19	persistent-heap.cpp	Persistent Leftist Heap. Meldable min-heap where push, pop and meld return new versions and never modify old ones	Persistence
20	persistent-queue.cpp	Persistent Queue and Stack. Queues and stacks with versions: push/pop on any old version creates a new version	Persistence
21	persistent-treap.cpp	Persistent Implicit Treap. Sequence with O(log n) split/merge where every operation keeps all old versions (fast copy-paste of substrings)	Persistence
22	persistent-trie.cpp	Persistent Binary Trie. Max/min xor of x with an element of a subarray a[l, r), and counting, via prefix versions of a binary trie	Persistence
23	queue-undo-trick.cpp	Queue Undo Trick. Turns any structure with “apply update / undo last update” (stack-like) into one that can also remove the OLDEST update	Queue Undo
24	radix-heap.cpp	Radix Heap (monotone priority queue for Dijkstra)	Radix Heap
25	scapegoat-tree.cpp	Scapegoat Tree (rebuilding balanced BST, ordered multiset). Balanced binary search tree without rotations: an unbalanced subtree is flattened and rebuilt perfectly	Balanced BST
26	skip-list.cpp	Skip List. Probabilistic ordered set with expected O(log n) insert, erase, search and lower_bound, built from linked lists with random levels	Skip List
27	splay-tree.cpp	Splay Tree (keyed multiset and implicit sequence). Self-adjusting BST: an ordered multiset with rank/k-th/predecessor queries, and a sequence with range reverse and range sum	Balanced BST
28	top-k-sum.cpp	Top-K Sum. Maintains the sum of the k largest elements of a multiset under insertions, deletions and changes of k	Top-K Sum
29	treap-keyed.cpp	Keyed Treap (FHQ Treap, split/merge by key). Ordered multiset with insert, erase, rank, k-th, predecessor/successor and subtree sums, all by split/merge	Treap
30	treap.cpp	Implicit Treap. Sequence with insert/erase at any position, range reverse, range add, range sum/min, split and merge	Treap
31	venice-heap.cpp	Venice Heap (Lazy Add + Small-to-Large Merge). Min-heap that supports “add x to every element” in O(1) and merging heaps by moving the smaller one	Venice Heap
32	weight-balanced-tree.cpp	Weight-Balanced Tree (persistent ordered set with rotations, Adams / BB[alpha])	Balanced BST
33	weighted-dsu.cpp	Weighted (Potential) DSU. Union-find that maintains known differences value[v] - value[u] and detects contradictions	Disjoint Set Variants

dp/ — classic DP and every DP optimization

#	Template	What it does	Notes
1	aliens-trick.cpp	Aliens Trick (WQS Binary Search). Removes a “use exactly / at most k items” constraint by charging a penalty per item when the answer is concave in k	Aliens Trick
2	broken-profile-dp.cpp	Broken Profile DP (Domino Tilings). Counts domino tilings of a grid with blocked cells by a cell-by-cell bitmask DP over the frontier	Broken Profile
3	classic-dp.cpp	Classic DP Collection	Dynamic Programming Cheatsheet
4	connected-component-dp.cpp	Connected Component DP (inserting elements in sorted order)	Connected Component Dynamic Programming
5	convex-hull-trick.cpp	Convex Hull Trick (Monotone Slopes). Minimum of lines y = k x + m at a point, for lines added in non-increasing order of slope	Convex Hull Trick
6	cyk.cpp	CYK Parsing (context-free grammar membership). Decides whether a string is generated by a grammar in Chomsky normal form and counts its parse trees, by interval DP	Cocke-Younger-Kasami
7	dag-dp.cpp	DP on a DAG (longest / shortest paths, path counting). Topological-order DP on a directed acyclic graph: longest and shortest paths from a source (any weights) and the number of paths	DAG Dynamic Programming
8	digit-dp.cpp	Digit DP. Counts the integers in [0, bound] whose digits are accepted by a small finite automaton	Digit Dynamic Programming
9	divide-and-conquer-dp.cpp	Divide and Conquer DP Optimization. Layered partition DP cur[i] = min_{j < i} prev[j] + cost(j, i) when the optimal split point is monotone	Divide and Conquer Optimization
10	divisor-transforms.cpp	DP over Divisors (zeta / Mobius on the divisor lattice)	Divisor Dynamic Programming
11	doubling-x2-plus-1.cpp	Doubling DP (“x2 / +1” trick) for Elementary Symmetric Sums. E_k(0, 1, …, n) = sum over 0 <= i_1 < … < i_k <= n of i_1 i_2 … i_k for all k <= K, in O(K^2 log n) for huge n	Doubling Dynamic Programming
12	dynamic-dp.cpp	Dynamic DP on a Tree (max weight independent set with point updates). Maintains a tree DP under vertex weight changes in O(log^2 n) per update, via heavy-light decomposition and (max, +) 2x2 matrices	Dynamic DP
13	edit-distance.cpp	Edit Distance (Levenshtein). Minimum cost to turn one sequence into another by insertions, deletions and substitutions	Edit Distance
14	hirschberg.cpp	Hirschberg’s Algorithm (LCS / edit alignment in linear memory). Reconstructs a longest common subsequence of two sequences in O(n m) time and O(n + m) memory	Hirschberg
15	knapsack.cpp	Knapsack (0/1, Unbounded, Bounded, Subset Sum). Maximum value within a weight capacity for 0/1, unbounded and bounded items, plus bitset subset sums	Knapsack
16	knuth-optimization.cpp	Knuth Optimization and Garsia-Wachs. Interval DP dp[l][r] = cost(l, r) + min over splits of dp[l][m] + dp[m][r] in O(n^2) instead of O(n^3)	Knuth Optimization
17	lcs.cpp	Longest Common Subsequence. One longest common subsequence of two sequences, plus a bit-parallel LCS length	Longest Common Subsequence
18	li-chao-tree.cpp	Li Chao Tree. Minimum of lines and line segments y = k x + m at points of a fixed coordinate set	Li Chao Tree
19	line-container.cpp	Line Container (Dynamic Convex Hull Trick). Maximum or minimum of lines y = k x + m at a point, with lines inserted in any order	Convex Hull Trick
20	lis.cpp	Longest Increasing Subsequence. Length and one optimal subsequence of the longest strictly increasing or non-decreasing subsequence	Longest Increasing Subsequence
21	monotone-1d1d.cpp	1D/1D DP with Monotone Decisions (binary search on a deque). Dp[x] = min over i < x of dp[i] + w(i, x) in O(n log n) when w satisfies the quadrangle inequality	1D1D Optimization
22	persistent-li-chao.cpp	Persistent Li Chao Tree	Li Chao Tree
23	plug-dp.cpp	Plug DP / Broken Profile with Connectivity (Hamiltonian cycles in a grid). Counts the Hamiltonian cycles through all free cells of a grid with obstacles, cell by cell with bracket-encoded plug states	Broken Profile
24	product-at-most-k.cpp	Counting Subsets with Product at most K (floor-division states). Number of subsets (subsequences) of positive integers whose product is <= K, modulo a prime, in O(n sqrt K)	Floor Division States
25	rollback-cht.cpp	Convex Hull Trick with Rollback (CHT on a tree)	Convex Hull Trick
26	slope-trick.cpp	Slope Trick. Maintains a convex piecewise linear function with integer slopes under adds of /x - a/, prefix/suffix minima and shifts	Slope Trick
27	smawk.cpp	SMAWK (row minima of a totally monotone matrix). For every row, the column of its leftmost minimum in a totally monotone n x m matrix given by a function, in O(n + m) evaluations	SMAWK
28	sos-dp.cpp	Sum over Subsets (Zeta / Mobius Transforms). In-place subset and superset sum transforms and their inverses over bitmasks	Sum over Subsets
29	submask-count-dynamic.cpp	Dynamic Submask Counting (meet in the middle on bits). Multiset of B-bit masks with insert/erase and “how many elements are submasks of s” in O(2^(B/2)) per operation	Dynamic Submask Count
30	subset-sum.cpp	Subset Sum (sqrt grouping, bitset, reconstruction). Which sums are reachable by subsets of positive integers with total S, in O(S sqrt S) (or /64 with bitsets), with a witness subset	Subset Sum
31	subset-union.cpp	Size of the Union for Every Subset of Sets (SOS). Given m sets over n elements, the size of the union of every one of the 2^m families of sets, in O(n + m 2^m)	Subset Union
32	tsp.cpp	Travelling Salesman (Held-Karp). Minimum-cost Hamiltonian cycle or path from vertex 0 by bitmask DP, with the visiting order	Travelling Salesman
33	xor-equation.cpp	Counting Solutions of x_0 ^ x_1 ^ … ^ x_{n-1} = X with 0 <= x_i <= a_i. Number of tuples with bounded entries whose xor equals X, modulo a prime, in O(n log max)	XOR Counting

flows/ — max flow, min cost flow, matchings, cuts, matroids

#	Template	What it does	Notes
1	dinic.cpp	Dinic’s Maximum Flow. Maximum flow, minimum s-t cut and per-edge flows in a directed network	Dinic
2	edmonds-karp.cpp	Edmonds-Karp and Ford-Fulkerson Maximum Flow. The textbook max-flow algorithms: BFS shortest augmenting paths (Edmonds-Karp) and DFS augmenting paths (Ford-Fulkerson)	Edmonds-Karp
3	flow-decomposition.cpp	Flow Decomposition (paths and cycles). Splits a feasible s-t flow into at most E augmenting paths and cycles, each with its amount	Flow Decomposition
4	flow-lower-bounds.cpp	Flow with Lower Bounds. Feasible circulation and minimum / maximum s-t flow when every edge has bounds lo <= flow <= hi	Lower Bounds
5	general-matching.cpp	Maximum Matching in General Graphs (Edmonds’ Blossom). Maximum cardinality matching in an undirected graph, contracting odd cycles (blossoms)	General Matching
6	global-min-cut.cpp	Global Minimum Cut (Stoer-Wagner). Minimum weight set of edges whose removal disconnects an undirected weighted graph	Global Min Cut
7	gomory-hu.cpp	Gomory-Hu Tree (All-Pairs Minimum Cut). A tree on the same vertices whose path minima equal all pairwise minimum cuts of an undirected graph	Gomory-Hu
8	hopcroft-karp.cpp	Hopcroft-Karp Bipartite Matching. Maximum bipartite matching in O(E sqrt V), plus a minimum vertex cover by König’s theorem	Hopcroft-Karp
9	hungarian.cpp	Hungarian Algorithm (Assignment Problem). Minimum-cost assignment of n rows to distinct columns of an n x m cost matrix (n <= m)	Hungarian
10	kuhn.cpp	Kuhn’s Bipartite Matching (and lexicographically smallest matching). Simple augmenting-path bipartite matching, plus the lexicographically smallest maximum matching	Kuhn
11	matroid-intersection.cpp	Matroid Intersection (unweighted, weighted) and Matroid Partition. Largest set independent in two matroids at once (unweighted), with graphic, colorful (partition) and linear (xor) matroid oracles	Matroid Intersection
12	max-closure.cpp	Maximum Weight Closure (Project Selection). Choose a set of vertices closed under “u chosen => v chosen” maximizing the total weight, via a minimum cut	Max Closure
13	max-density-subgraph.cpp	Maximum Density Subgraph. Non-empty vertex set S maximizing /E(S)/ / /S/ (edges inside S per vertex), exactly, with integer flows	Densest Subgraph
14	min-cost-b-flow.cpp	Minimum Cost b-Flow (supplies, lower bounds, negative costs). Cheapest flow meeting vertex supplies/demands and edge bounds lo <= f <= hi with any (also negative) costs, by capacity scaling	Min Cost b-Flow
15	min-cost-flow-cost-scaling.cpp	Min Cost Max Flow by Cost Scaling (push-relabel, negative cycles allowed). Minimum cost maximum s-t flow for integer costs of any sign (negative cycles included), very fast in practice	Cost Scaling
16	min-cost-flow.cpp	Minimum-Cost Flow (Successive Shortest Paths). Min-cost max-flow (or up to a flow limit) with Dijkstra on reduced costs; negative edge costs allowed	Min Cost Flow
17	min-cut-unique.cpp	Minimum Cut Uniqueness and Cut Sides. After a max flow, the minimal source side, the minimal sink side and whether the minimum s-t cut is unique	Cut Uniqueness
18	network-simplex.cpp	Network Simplex (min cost b-flow). Minimum cost flow with supplies/demands, lower bounds and any costs, by the network simplex method (block pivoting)	Network Simplex
19	path-cover.cpp	Minimum Path Cover of a DAG (vertex-disjoint and with shared vertices)	Path Cover
20	push-relabel.cpp	Push-Relabel Maximum Flow (Highest Label). Fast maximum flow value and minimum cut with highest-label selection, gap and global relabeling	Push-Relabel
21	randomized-matching.cpp	Randomized General Matching (Tutte matrix). Maximum matching size and a maximum matching of a general graph via a random Tutte matrix modulo a prime	Tutte Matrix
22	weighted-general-matching.cpp	Maximum Weight Matching in General Graphs (weighted blossom). Maximum total weight matching of an undirected graph with positive integer weights, in O(n^3)	Weighted Blossom

game-theory/ — impartial and partizan games, game search

#	Template	What it does	Notes
1	game-search.cpp	Game Tree Search (negamax with alpha-beta pruning and a transposition table). Minimax value and best move of a two-player zero-sum game, pruning branches that cannot change the result	Minimax
2	hackenbush.cpp	Hackenbush (green on graphs, blue-red on trees). Grundy value of Green Hackenbush on a rooted multigraph, and the surreal value of Blue-Red Hackenbush on a rooted tree	Hackenbush
3	matching-game.cpp	Gallai-Edmonds Decomposition and Undirected Vertex Geography	Matching Games
4	retrograde.cpp	Games on Graphs with Cycles (retrograde analysis, loopy Sprague-Grundy)	Loopy Games
5	sprague-grundy.cpp	Impartial Games (Sprague-Grundy). Mex, Grundy value tables, Nim and misere Nim with winning moves, Wythoff’s game and nim multiplication	Sprague-Grundy
6	surreal-numbers.cpp	Surreal Numbers (dyadic rationals) for Partizan Games	Hackenbush

geometry/ — 2D / 3D geometry, hulls, polygons, circles, sweeps

#	Template	What it does	Notes
1	angular-sweep.cpp	Angular Sweep (circle covering, exact Angle struct, similarity transform). Maximum number of points inside or on a circle of fixed radius r placed anywhere, and a best center	Angular Sweep
2	bounding-rectangle.cpp	Minimum Bounding Rectangle and Rectangle in Rectangle	Bounding Rectangle
3	circle-inversion.cpp	Circle Inversion. Inversion in a circle: maps points, and circles / lines to circles / lines, turning tangency problems into line problems	Circle Inversion
4	circle-union.cpp	Area of a Union of Circles. Area covered by at least one of n circles (Green’s theorem over the uncovered boundary arcs)	Circle Union
5	circle.cpp	Circles. Circumcircle, circle-line and circle-circle intersections, common tangents and intersection areas	Circle-Circle
6	closest-pair.cpp	Closest Pair of Points. Pair of points with minimum Euclidean distance, by a sweep line over a y-ordered set	Closest Pair
7	convex-distance.cpp	Distance Between Two Convex Polygons. Minimum distance between two convex polygons (0 if they intersect), via the Minkowski difference	Convex Distance
8	convex-hull-3d.cpp	3D Convex Hull. Convex hull of points in 3D as outward-oriented triangles (incremental, exact), with surface area and volume	3D Hull
9	convex-hull.cpp	Convex Hull (Monotone Chain). Convex hull of a point set in counter-clockwise order, optionally keeping collinear boundary points	Convex Hull
10	convex-layers.cpp	Convex Layers (onion peeling). Peels the convex hull repeatedly; layer[i] = how many hulls were removed before point i is on the hull	Convex Layers
11	convex-polygon-queries.cpp	Convex Polygon Queries. O(log n) point location in a convex polygon, extreme vertex in a direction and tangents from a point	Convex Polygon Queries
12	delaunay.cpp	Delaunay Triangulation and Voronoi Diagram	Delaunay
13	dynamic-convex-hull.cpp	Dynamic Convex Hull (insertions only). Maintains the convex hull of a growing point set: insert a point, test whether a point is inside or on the hull	Dynamic Hull
14	geometry-3d-extras.cpp	3D Extras: Rotations (axis-angle, quaternions), Polyhedra, Spherical Geometry	3D Geometry
15	half-plane-intersection.cpp	Half-Plane Intersection. Convex polygon (CCW) equal to the intersection of closed half-planes, by angle sort and a deque	Half-Plane Intersection
16	hull-diameter.cpp	Rotating Calipers (Diameter and Width). Farthest pair of points and minimum width of a convex polygon with rotating calipers	Rotating Calipers
17	kd-tree.cpp	k-d Tree (nearest neighbour). Static 2D tree answering “closest other point to p” by squared distance	KD Tree
18	lines-segments.cpp	Lines and Segments. Point-on-segment test, projection, distances, and line/segment intersections (exact for integers)	Line Intersection
19	manhattan-mst.cpp	Manhattan Minimum Spanning Tree. Minimum spanning tree under the Manhattan distance from O(n) candidate edges (octant sweep)	Manhattan Geometry
20	max-collinear.cpp	Maximum Number of Collinear Points. Largest number of the given integer points lying on one line (duplicates count separately)	Max Collinear
21	min-enclosing-circle.cpp	Minimum Enclosing Circle (Welzl). Smallest circle containing all given points, by randomized incremental construction	Enclosing Circle
22	minkowski-sum.cpp	Minkowski Sum of Convex Polygons. Minkowski sum {a + b} of two convex polygons in O(n + m) by merging their edges by angle	Minkowski Sum
23	planar-faces.cpp	Faces of a Planar Graph (and the outer face)	Planar Faces
24	point-location.cpp	Point Location (offline): the segment directly below each query point. For non-crossing segments and query points, finds for every query the first segment hit by a ray shot straight down	Point Location
25	point.cpp	2D Point and Vector. Point with vector arithmetic, dot and cross products, orientation test and polar-angle order	Vectors
26	point3d.cpp	3D Point, Planes and Segments. Point3 with dot and cross products and orientation, planes, line-plane intersection and 3D distances	3D Geometry
27	points-in-triangle.cpp	Count Points in Triangles (O(1) per query after O(n (n + m) log) preprocessing). Number of points of a set B strictly inside the triangle A[i] A[j] A[k] for many queries over vertices from a set A	Points in Triangle
28	polygon-clipping.cpp	Polygon Clipping, Convex Polygon Intersection, Ear-Clipping Triangulation, Affine Transforms	Polygon Clipping
29	polygon-union.cpp	Area of a Union of Polygons. Exact-up-to-precision area covered by at least one of several simple polygons	Polygon Union
30	polygon.cpp	Simple Polygon Tools. Signed area, perimeter, point in polygon, centroid, cut by a line and lattice point counts (Pick)	Polygon Area
31	rectangle-union.cpp	Union of Axis-Parallel Rectangles (area and perimeter). Sweep line over x with a segment tree on compressed y storing how much of the y axis is covered	Rectangle Union
32	segment-in-polygon.cpp	Segment Inside Polygon. Whether a segment lies entirely inside a simple polygon (touching the boundary is allowed), for any polygon shape	Segment in Polygon
33	segment-intersection.cpp	Segment Intersection Detection (Shamos-Hoey) and Simple Polygon Test. Finds whether any two of n segments intersect (and one such pair), and whether a polygon is simple	Segment Intersection
34	triangle.cpp	Triangle Centers and Formulas. Centroid, incenter, circumcenter, orthocenter, excenters, area from sides, angles and medians of a triangle	Triangles

graphs/ — shortest paths, MST, connectivity, SCC, matching-free graph theory, cliques, planarity

#	Template	What it does	Notes
1	bellman-ford.cpp	Bellman-Ford Shortest Paths. Shortest paths with negative edge weights, marking vertices made arbitrarily cheap by negative cycles	Bellman-Ford
2	bfs.cpp	Breadth-First Search (multi-source, 0-1 BFS). Unweighted shortest paths from a set of sources with parents and paths; 0-1 BFS for 0/1 edge weights	Breadth-First Search
3	biconnected-components.cpp	Biconnected Components and Block-Cut Tree. Splits an undirected multigraph into vertex-biconnected components (blocks), finds cut vertices and builds the block-cut tree	Biconnected Components
4	bipartite.cpp	Bipartite Check (2-coloring, odd cycle). 2-colors an undirected graph or returns an odd cycle proving that it is not bipartite	Bipartite Graphs
5	boruvka.cpp	Boruvka’s Minimum Spanning Tree (and XOR MST)	Boruvka
6	bridges-articulation.cpp	Bridges and Articulation Points (low-link). Finds bridges and cut vertices of an undirected multigraph with one iterative DFS	Bridges
7	cactus.cpp	Cactus Graph (cycles and the cactus tree). Finds the simple cycles of an edge cactus (every edge on at most one cycle) and builds its tree of vertices + cycle nodes	Cactus Graphs
8	chinese-postman.cpp	Chinese Postman (Route Inspection). Shortest closed walk that uses every edge of a connected undirected weighted graph at least once	Chinese Postman
9	chordal-graph.cpp	Chordal Graphs (Perfect Elimination Ordering). Maximum cardinality search, chordality test, maximum clique, optimal coloring and chromatic polynomial of chordal graphs	Chordal Graphs
10	chromatic-number.cpp	Chromatic Number (inclusion-exclusion)	Graph Coloring
11	chromatic-polynomial.cpp	Chromatic Polynomial. P(x) = number of proper colorings with at most x colors, for graphs with up to ~18 vertices, modulo a prime	Chromatic Polynomial
12	complement-graph.cpp	BFS on the Complement Graph. Shortest paths (unit weights) and connected components of the complement of a sparse graph in O(n + m)	Complement BFS
13	count-four-cycles.cpp	Counting 4-Cycles. Number of 4-cycles (as edge sets) in a simple undirected graph	Cycle Counting
14	count-triangles.cpp	Triangle Counting and Enumeration. Lists every triangle of an undirected graph exactly once by orienting edges from low to high degree	Cycle Counting
15	degree-sequence.cpp	Degree Sequences (Erdos-Gallai, Havel-Hakimi, Gale-Ryser, Landau)	Degree Sequences
16	difference-constraints.cpp	System of Difference Constraints. Finds integers x_0..x_{n-1} satisfying constraints x_v - x_u <= c (and <=, >=, == variants), or reports infeasibility	Difference Constraints
17	dijkstra.cpp	Dijkstra’s Shortest Paths. Single- or multi-source shortest paths with non-negative edge weights, parents and path reconstruction	Dijkstra
18	directed-mst.cpp	Directed MST / Minimum Arborescence (Chu-Liu/Edmonds). Minimum-weight spanning arborescence rooted at a given vertex, with the chosen edges, using mergeable heaps and cycle contraction	Chu-Liu-Edmonds
19	dominator-tree.cpp	Dominator Tree (Lengauer-Tarjan). Immediate dominators of every vertex of a directed graph with respect to a root	Dominator Tree
20	dynamic-connectivity-online.cpp	Online Dynamic Connectivity (Holm-de Lichtenberg-Thorup). Fully dynamic undirected graph: add edge, remove edge, connectivity and component size queries answered online	Holm-de Lichtenberg-Thorup
21	dynamic-mst-offline.cpp	Offline Dynamic MST (edge weight changes). MST weight after each of q offline updates “set the weight of edge i to x” on a connected graph	Dynamic MST
22	edge-coloring.cpp	Edge Coloring (Bipartite with Delta colors, Vizing with Delta + 1)	Edge Coloring
23	euler-path.cpp	Euler Path / Circuit (Hierholzer). Finds a trail that uses every edge exactly once in a directed or undirected multigraph, with edge ids and existence checks	Euler Path
24	find-cycle.cpp	Find a Cycle (directed and undirected). Returns the vertices of some cycle of a directed or undirected graph, or an empty list if acyclic	Cycle Detection
25	floyd-warshall.cpp	Floyd-Warshall All-Pairs Shortest Paths. All-pairs shortest paths with negative weights; pairs affected by a negative cycle get -inf	Floyd-Warshall
26	functional-graph.cpp	Functional Graphs (successor graphs: every vertex has exactly one outgoing edge). Cycles, distance to the cycle, the k-th successor for k up to 1e18, and the distance from u to v along successors	Functional Graphs
27	grid.cpp	Grid Graphs (BFS, multi-source, path, components, 0-1 BFS). Shortest paths and connected regions on a character grid with 4 or 8 directions	Grid Graphs
28	incremental-dag-reachability.cpp	Incremental Reachability in a DAG (Italiano). Inserts edges into a DAG (rejecting edges that would create a cycle) and answers reachability in O(1)	DAG Reachability
29	incremental-scc.cpp	Incremental SCC (when does each edge become part of a cycle). Edges are added one by one; for each edge, the first time (prefix index) when its two endpoints are strongly connected	Incremental SCC
30	johnson.cpp	Johnson’s All-Pairs Shortest Paths. All-pairs shortest paths on sparse graphs with negative weights (Bellman-Ford potentials + n Dijkstras)	Johnson
31	k-shortest-paths.cpp	K Shortest Walks (Eppstein). Lengths of the k shortest s-t walks (vertices and edges may repeat) with persistent leftist heaps	Yen
32	kruskal.cpp	Kruskal’s Minimum Spanning Tree. Minimum spanning tree (or forest) of an undirected weighted graph by sorting edges and joining components with a DSU	Kruskal
33	max-clique.cpp	Maximum Clique / Maximum Independent Set (Bron-Kerbosch)	Maximum Clique
34	maximal-cliques.cpp	Maximal Clique Enumeration (Bron-Kerbosch) and Clique Counting. Calls a function for every maximal clique (with pivoting), and counts all cliques of a graph with up to ~45 vertices	Bron-Kerbosch
35	min-diameter-spanning-tree.cpp	Minimum Diameter Spanning Tree (Absolute Graph Center)	Minimum Diameter Tree
36	min-mean-cycle.cpp	Minimum Mean Cycle (Karp). Minimum average edge weight over all directed cycles, as an exact fraction, with one optimal cycle	Minimum Mean Cycle
37	min-weight-cycle.cpp	Minimum Weight Cycle (Girth). Shortest cycle through every vertex, through every edge, and overall, for undirected and directed graphs with non-negative weights	Girth
38	online-bridges.cpp	Online Bridges (Incremental 2-Edge-Connectivity). Adds edges one by one and maintains the number of bridges and the 2-edge-connected components	Online Bridges
39	planarity.cpp	Planarity Testing (Left-Right algorithm). Decides whether an undirected graph can be drawn in the plane without crossing edges	Boyer-Myrvold
40	prim.cpp	Prim’s Minimum Spanning Tree. Minimum spanning tree (or forest) grown from a vertex: O(n^2) on an adjacency matrix for dense graphs, heap-based for sparse ones	Prim
41	replacement-paths.cpp	Replacement Paths (Shortest Path Avoiding Each Edge). For an undirected graph with positive weights, the s-t distance when any single edge is removed	Replacement Paths
42	residue-shortest-path.cpp	Shortest Paths over Residues (coin problem: which sums are representable)	Residue Paths
43	scc-kosaraju.cpp	Strongly Connected Components (Kosaraju). Two-pass SCC (DFS order on the graph, then DFS on the reverse graph), iterative	Strongly Connected Components
44	scc.cpp	Strongly Connected Components (Tarjan). Strongly connected components of a directed graph, numbered in topological order, plus the condensation DAG	Strongly Connected Components
45	second-best-mst.cpp	Second-Best MST and MST with a Forced Edge	Second-Best MST
46	segment-tree-graph.cpp	Shortest Paths with Range Edges (Segment Tree Graph). Dijkstra on a graph with edges vertex -> range, range -> vertex and range -> range, using O(n) helper nodes	Segment Tree Graph
47	spfa.cpp	SPFA (Queue-Based Bellman-Ford). Single-source shortest paths with negative weights and negative-cycle detection, usually much faster than plain Bellman-Ford	Shortest Path Faster
48	st-numbering.cpp	st-Numbering (Bipolar Orientation). Orders the vertices from s to t so that every other vertex has a neighbour before it and a neighbour after it	st-Numbering
49	stable-marriage.cpp	Stable Marriage (Gale-Shapley). Proposer-optimal stable matching; preference lists may be incomplete and the sides may differ in size	Stable Marriage
50	stable-roommates.cpp	Stable Roommates (Irving’s Algorithm)	Stable Roommates
51	steiner-tree.cpp	Minimum Steiner Tree. Minimum-weight connected subgraph containing k given terminals of an undirected graph with non-negative weights, with its edges	Steiner Tree
52	strong-orientation.cpp	Strong Orientation (Robbins) and Min-Max Indegree Orientation hints	Strong Orientation
53	three-edge-connected.cpp	Three-Edge-Connected Components. Partitions the vertices into classes connected by 3 edge-disjoint paths (no 2 edges disconnect them)	3-Edge Connectivity
54	topological-sort.cpp	Topological Sort (Kahn). Orders the vertices of a DAG so every edge goes forward; detects cycles; optional lexicographically smallest order	Topological Sort
55	transitive-closure.cpp	Transitive Closure (Bitset Reachability). Answers “can u reach v” for all pairs of a directed graph with SCC condensation and bitset DP	Transitive Closure
56	treewidth-2.cpp	Tree Decomposition of Width 2 (series-parallel graphs). Decides whether a graph has treewidth <= 2 and returns a tree decomposition with bags of size <= 3	Treewidth 2
57	two-edge-connected-components.cpp	Two-Edge-Connected Components. Splits an undirected multigraph into 2-edge-connected components (no bridge inside) and builds the bridge tree	Bridge Tree
58	two-sat.cpp	2-SAT. Satisfiability of a conjunction of 2-literal clauses over boolean variables, with an assignment	2-SAT
59	xor-paths.cpp	XOR Paths in Graphs (cycle space basis). Maximum / minimum xor of a walk between two vertices of an undirected graph with xor edge weights	XOR Paths

linear-algebra/ — matrices, elimination, determinants, LP, xor bases

#	Template	What it does	Notes
1	black-box.cpp	Black-Box Linear Algebra (Freivalds’ check, Wiedemann sparse determinant). Randomized algorithms that only multiply matrices by vectors: verify A B = C, and the determinant of a sparse matrix	Wiedemann
2	characteristic-polynomial.cpp	Characteristic Polynomial. Coefficients of det(x I - A) over a field by reduction to Hessenberg form, O(n^3)	Characteristic Polynomial
3	determinant.cpp	Determinant. Determinant of a square matrix over a field (MInt with prime modulus, doubles) or modulo any integer	Determinant
4	gauss-xor.cpp	Gaussian Elimination over GF(2). Solves a system of xor equations and computes its rank with bitset rows (64 columns per word operation)	Gaussian Elimination
5	gaussian-elimination.cpp	Gaussian Elimination. Solves a system of linear equations (one solution plus a null-space basis) and computes rank, over MInt or doubles	Gaussian Elimination
6	matrix-inverse.cpp	Matrix Inverse. Inverts a square matrix over MInt or doubles by Gauss-Jordan elimination on [A / I]	Matrix Inverse
7	matrix-mod2.cpp	Matrices over GF(2) with Bitsets (inverse, rank, determinant). Inverse, rank and determinant of an n x n 0/1 matrix modulo 2, with rows stored as bitsets	GF(2) Matrices
8	matrix-tree.cpp	Matrix-Tree Theorem (Kirchhoff / Tutte). Counts spanning trees of an undirected multigraph, or spanning arborescences of a directed one, as a Laplacian determinant	Matrix-Tree Theorem
9	matrix.cpp	Matrix. Dense matrix over any ring with multiplication, fast exponentiation, identity and matrix-vector product	Matrices
10	min-plus-matrix.cpp	Min-Plus (Tropical) Matrix Power. Shortest walks with exactly k edges (or at most k), and longest walks with max-plus, for k up to 1e18	Min-Plus Matrix
11	permanent-hafnian.cpp	Permanent and Hafnian	Permanent
12	simplex.cpp	Simplex (Linear Programming). Maximizes c^T x subject to A x <= b and x >= 0 with the two-phase simplex method	Simplex
13	structured-matrices.cpp	Structured Matrices (circulant, permutant, rank-one, Vandermonde, tridiagonal, Sherman-Morrison). Determinants and solvers that exploit the structure of special matrices instead of O(n^3) elimination	Structured Matrices
14	xor-basis-extra.cpp	Xor Basis Extras (max-weight basis, range max xor, rank of a value in the span). Online maximum-weight linearly independent set, maximum subset xor inside a[l..r], and how many span values are below x	XOR Basis
15	xor-basis.cpp	Xor Basis (Linear Basis over GF(2)). Maintains a basis of the xor span of inserted 64-bit numbers: membership, max/min xor, k-th smallest	XOR Basis

base

#	Template	What it does	Notes
1	main.cpp		Contest Template

misc/ — big numbers, dates, parsing, heuristics, assorted tricks

#	Template	What it does	Notes
1	bigint.cpp	Arbitrary-Precision Integer (BigInt). Signed arbitrary-precision integers stored in base 1e9 with + - * / % and comparisons	Big Integers
2	bump-allocator.cpp	Bump Allocator (fast new / delete)	Bump Allocator
3	dates.cpp	Calendar Utilities. Leap years, day-of-week and conversions between a (year, month, day) date and a day number	Calendar
4	expression-parser.cpp	Expression Parser and Evaluator. Recursive-descent evaluator for arithmetic expressions with + - * / ^, unary minus and parentheses	Expression Parsing
5	fraction.cpp	Exact Fraction Arithmetic. Rational numbers kept in lowest terms with a positive denominator, using 128-bit intermediates	Fractions
6	heuristic-search.cpp	Heuristic Search (hill climbing, beam search, genetic algorithm)	Heuristics
7	ida-star.cpp	IDA* Search (iterative deepening A*), with the 15-puzzle as example	Iterative Deepening
8	interval-cover.cpp	Interval Cover and Constant Intervals. Fewest intervals covering a target range (greedy); splitting [from, to) into maximal runs where a function is constant	Greedy
9	josephus.cpp	Josephus Problem. Finds the survivor when n people in a circle are eliminated by counting every k-th one	Josephus
10	knight-moves.cpp	Knight Moves on an Infinite Board. Minimum number of knight moves between two squares of an unbounded chessboard in O(1)	Knight Moves
11	negative-base.cpp	Negative Base Numbers (base -2 and any base -b). Conversion between integers and base -b digit strings, plus addition of base -2 numbers digit by digit	Negative Base
12	parallel-binary-search.cpp	Parallel Binary Search	Parallel Binary Search
13	permutation-utils.cpp	Permutation Utilities. Inverse, composition, cycle decomposition, and k-th permutation / rank via Lehmer code	Permutations
14	set-hashing.cpp	Set / Multiset Hashing with Random Weights (sum hash, xor hash)	Set Hashing
15	simulated-annealing.cpp	Simulated Annealing. Generic simulated-annealing template applied to the Euclidean travelling salesman problem	Simulated Annealing
16	subarray-aggregates.cpp	Subarray Aggregates with Few Distinct Values (GCD / OR / AND over all subarrays)	Subarray Aggregates
17	subarray-mex.cpp	MEX of All Subarrays. Which values occur as the mex of some subarray, and the mex of all those mex values (CF 1436E)	Subarray MEX
18	trygub-number.cpp	Trygub Number (huge binary number under +- x 2^e)	Trygub Number

number-theory/ — modint, sieves, factorization, CRT, discrete log / root, multiplicative sums

#	Template	What it does	Notes
1	basic-number-theory.cpp	Basic Number Theory. Overflow-safe 64-bit modular multiply/power plus O(sqrt n) primality, factorization, divisors and Euler phi	Overview
2	cipolla.cpp	Cipolla’s Algorithm (square roots modulo a prime). X with x^2 = a (mod p) by arithmetic in F_p(sqrt(w)) for a non-residue w = t^2 - a	Cipolla
3	continued-fractions.cpp	Continued Fractions and the Stern-Brocot Tree. Continued fractions, convergents, closest fractions with bounded denominator and binary search over fractions	Continued Fractions
4	crt.cpp	Chinese Remainder Theorem. Solves systems x = r[i] (mod m[i]) with arbitrary (non-coprime) moduli, plus Garner’s method for the answer modulo another number	Chinese Remainder Theorem
5	diophantine-extra.cpp	More Linear Diophantine Equations (N variables, non-negative counts). An integer solution of sum a_i x_i = c, and the number of non-negative solutions of a x + b y = c and a x + b y + c z = n	Diophantine Equations
6	dirichlet.cpp	Dirichlet Convolution Toolkit	Dirichlet Convolution
7	discrete-log.cpp	Discrete Logarithm (Baby-Step Giant-Step). Smallest x >= 0 with a^x = b (mod m) for any modulus m, including gcd(a, m) > 1	Discrete Log
8	divisor-counting.cpp	Divisor Counting (smallest number with k divisors, count with exactly k divisors, sum of d(i)). Smallest n with exactly k divisors, how many n <= N have exactly k divisors, and sum_{i <= N} d(i) in about O(N^{1/3})	Divisor Functions
9	du-sieve.cpp	Du’s Sieve (Prefix Sums of phi and mu). Prefix sums of Euler’s phi and the Mobius function up to n ~ 1e10 in O(n^{2/3}) using Dirichlet convolution identities	Du’s Sieve
10	elliptic-curve.cpp	Elliptic Curves over F_p. Points on y^2 = x^3 + a x + b (mod p): addition, doubling, scalar multiplication, point counting for small p	Elliptic Curves
11	extended-gcd.cpp	Extended Euclid and Linear Diophantine Equations. Extended gcd, modular inverse for any modulus, and integer solutions of ax + by = c	Extended Euclid
12	factorial-mod.cpp	Factorials modulo a Prime for Huge n. V_p(n!) (Legendre), n! with all factors p removed modulo p for n up to 1e18, and C(n, k) mod p via it	Factorial mod p
13	factorization.cpp	Miller-Rabin and Pollard-Rho Factorization. Deterministic primality test and fast prime factorization for every 64-bit integer	Factorization
14	fast-factorial.cpp	Fast Factorial mod a Prime (n up to 1e9, many queries). N! mod p for any prime p < 2^31 and n up to p - 1 (so up to ~2e9), answering many queries after one O(sqrt p log p)-ish build	Fast Factorial
15	fast-mod.cpp	Fast Modular Arithmetic (Barrett, Montgomery, 64-bit mulmod). Run-time modulus reduction without division (Barrett), a Montgomery modint for odd moduli, and a * b mod m for 64-bit m	Fast Modulo
16	fibonacci.cpp	Fibonacci Numbers (fast doubling, Pisano period, LCM of Fibonacci numbers). F(n) mod m in O(log n), the period of Fibonacci numbers modulo m, and lcm(F(a_1), …, F(a_k)) mod p	Fibonacci
17	floor-sum-general.cpp	Generalized Floor Sum. Sum over x = 0..n of x^k1 * floor((a x + b) / c)^k2 modulo a prime, for all k1 + k2 <= K at once	Floor Sum
18	floor-sum.cpp	Floor Sum. Computes sum_{i=0}^{n-1} floor((a * i + b) / m) in O(log m) with a Euclid-like recursion	Floor Sum
19	min25-sieve.cpp	Min_25 Sieve. Prefix sums f(1) + … + f(v) of a multiplicative f, for every v = floor(n / k), when f(p) is a polynomial in p	Min_25 Sieve
20	mod-linear.cpp	Min / Max / First Hit of (a x + b) mod m	Linear Congruence
21	mod-sqrt.cpp	Square Root Modulo a Prime (Tonelli-Shanks). Finds x with x^2 = a (mod p) for a prime p, or reports that a is a quadratic non-residue	Tonelli-Shanks
22	modint.cpp	Modular Integer. Integer arithmetic modulo a compile-time or run-time modulus with automatic reduction	Modular Arithmetic
23	modint64.cpp	64-bit Modular Integer (moduli up to ~9e18). Like MInt but for moduli above 2^31 (e.g	Modular Arithmetic
24	multiplicative-order.cpp	Multiplicative Order, Carmichael Function, Jacobi Symbol, Pohlig-Hellman, Pollard p - 1	Multiplicative Order
25	number-theory-misc.cpp	Number Theory Miscellany	Miscellany
26	pell.cpp	Pell’s Equation. Fundamental solution of x^2 - D y^2 = 1 (and = -1 when it exists) via the continued fraction of sqrt(D), plus the next solutions	Pell Equation
27	power-tower.cpp	Power Towers (generalized Euler theorem). A_l ^ (a_{l+1} ^ (… ^ a_r)) mod m for any modulus, using a^x = a^(x mod phi(m) + phi(m)) when x >= log2 m	Power Towers
28	powerful-number-sieve.cpp	Powerful Number Sieve (prefix sums of multiplicative functions). F(n) = sum_{i <= n} f(i) for multiplicative f when an easy multiplicative g with g(p) = f(p) and known prefix sums G exists	Powerful Numbers
29	prime-counting.cpp	Prime Counting (Lucy_Hedgehog). Computes pi(v), the number of primes <= v, for every value v = floor(n / k) at once in O(n^{3/4})	Prime Counting
30	primitive-root.cpp	Primitive Root, Multiplicative Order and Discrete k-th Root. Smallest primitive root modulo m, order of an element, and solutions of x^k = a (mod p) for prime p	Primitive Root
31	quotient-blocks.cpp	Quotient Blocks. Iterates over the O(sqrt n) maximal blocks of i on which floor(n / i) is constant, and indexes all distinct values of floor(n / i)	Harmonic Lemma
32	segmented-sieve.cpp	Segmented Sieve of Eratosthenes. Enumerates the primes in a range [lo, hi) block by block using O(sqrt(hi) + block) memory	Segmented Sieve
33	sieve.cpp	Linear Sieve. Primes, smallest prime factors and optionally Euler phi and Mobius mu for all numbers up to n, with O(log x) factorization	Linear Sieve
34	squarefree-count.cpp	Counting Squarefree Numbers up to 1e18. Q(n) = number of squarefree integers in [1, n] = sum_{d <= sqrt n} mu(d) floor(n / d^2), computed in about O(n^(2/5))	Squarefree Count
35	sum-of-two-squares.cpp	Sums of Two Squares. Write a prime p = 1 (mod 4) as a^2 + b^2, list all representations n = x^2 + y^2, and count them (r2)	Two Squares

numerical/ — integration and root finding

#	Template	What it does	Notes
1	integration.cpp	Numerical Integration (Adaptive Simpson). Integrates a function over [a, b] with adaptive Simpson’s rule, refining only where the error estimate is large	Integration
2	poly-roots.cpp	Real Roots of a Polynomial. Finds all distinct real roots of a polynomial by recursing on the derivative and bisecting monotone pieces	Polynomial Roots
3	romberg.cpp	Romberg Integration and Golden-Section Search. Definite integral of a smooth function by Richardson-extrapolated trapezoids, and the minimum of a unimodal function	Integration
4	root-finding.cpp	Root Finding (bisection, Newton, secant) and Complex Numbers	Newton’s Method

polynomial/ — FFT / NTT, formal power series, recurrences, transforms

#	Template	What it does	Notes
1	berlekamp-massey.cpp	Berlekamp-Massey. Finds the shortest linear recurrence that generates a given sequence over a field	Berlekamp-Massey
2	bitwise-convolution.cpp	Bitwise Convolutions (XOR / AND / OR / Subset) and Set Power Series. C[k] = sum of a[i] * b[j] over i op j = k for op in xor, and, or, and the subset convolution	Walsh-Hadamard Transform
3	bostan-mori.cpp	Bostan-Mori (k-th Coefficient of a Rational Series). [x^k] P(x) / Q(x) and the k-th term of a linear recurrence of order up to ~1e5, with NTT	Bostan-Mori
4	chirp-z.cpp	Chirp-Z Transform (evaluation and interpolation on a geometric progression). Values f(a), f(a z), f(a z^2), …, f(a z^(m-1)) of a polynomial with one convolution	Bluestein
5	counting-series.cpp	Counting Sequences with Power Series (Stirling rows / columns, Bell, Bernoulli, partitions, power sums). O(n log n) generating-function versions of the classic combinatorial sequences, modulo an NTT prime	Counting Series
6	cyclotomic.cpp	Cyclotomic Polynomials and the Factorization of x^n - 1. Exact integer coefficients of Phi_n(x), and x^n - 1 = prod over d / n of Phi_d(x) (its factorization over the rationals)	Cyclotomic
7	fft.cpp	Fast Fourier Transform. Complex FFT with precise roots: real and exact-integer convolution, and convolution modulo any m < 2^31	Fast Fourier Transform
8	fwht-any-base.cpp	Digitwise Convolutions in Any Base (generalized XOR / OR / AND)	Digit Convolutions
9	gf2-field.cpp	Finite Field GF(2^64) and Carry-Less Arithmetic. Field elements as 64-bit masks (polynomials over GF(2) modulo x^64 + x^4 + x^3 + x + 1): add = xor, multiply, power, inverse	GF(2^64)
10	karatsuba.cpp	Karatsuba Multiplication (any ring). Polynomial product for coefficient types without an FFT: u64 arithmetic mod 2^64, mod any m, matrices,	Karatsuba
11	lagrange-interpolation.cpp	Lagrange Interpolation. Evaluates the polynomial through f(0), …, f(n-1) at any x in O(n), or builds it from arbitrary points in O(n^2)	Lagrange Interpolation
12	linear-recurrence.cpp	K-th Term of a Linear Recurrence (Kitamasa). Computes a_k for a_i = c_1 a_{i-1} + … + c_d a_{i-d} by computing x^k mod the characteristic polynomial	Linear Recurrences
13	min-plus-convolution.cpp	Min-Plus Convolution. C_k = min over i + j = k of a_i + b_j when a is convex and b is convex too or arbitrary	Min-Plus Convolution
14	newton-basis.cpp	Newton Basis Conversion (monomial <-> Newton form on any nodes). Converts f = sum_i f_i x^i to the Newton form f = sum_i c_i prod_{j<i} (x - x_j) and back, for arbitrary (also repeated) nodes	Newton Basis
15	ntt-2d.cpp	2D Convolution (NTT). C[i][j] = sum a[x][y] * b[i - x][j - y] for two matrices modulo an NTT prime	2D Convolution
16	ntt.cpp	Number Theoretic Transform (+ exact 3-prime convolution). In-place NTT and polynomial multiplication modulo an NTT-friendly prime P = c * 2^k + 1	Number Theoretic Transform
17	online-convolution.cpp	Online (Relaxed) Convolution. Returns h_i = sum f_j g_{i-j} as soon as f_i and g_i are known, so f and g may depend on h_0..h_{i-1}	Online Convolution
18	p-recursive.cpp	P-Recursive Sequences (linear recurrences with polynomial coefficients). Finds a relation sum_{i=0}^{r} P_i(n - i) a[n - i] = 0 (deg P_i <= d) from the first terms, and extends the sequence with it	P-Recursive
19	poly-composition.cpp	Power Series Composition and Compositional Inverse. F(g(x)) mod x^n, and h with g(h(x)) = x (reversion of a series), over mint	Composition
20	poly-euclid.cpp	Polynomial GCD and Inverse Modulo a Polynomial (Half-GCD). Gcd(a, b) and x with a x = 1 (mod b) for polynomials over mint, in O(n log^2 n)	Polynomial GCD
21	poly-factor-mod-p.cpp	Polynomials over F_p: Roots and Factorization (Cantor-Zassenhaus). All roots of a polynomial modulo a prime, number of distinct roots, and the complete factorization into monic irreducible factors	Factorization
22	poly.cpp	Polynomials and Formal Power Series. Polynomial class over mint: + - *, inverse, division, log, exp, pow, sqrt, multipoint evaluation, interpolation	Polynomial Arithmetic
23	polynomial-sums.cpp	Sums of Polynomials (sum a^i f(i), binomial basis)	Polynomial Sums
24	reeds-sloane.cpp	Reeds-Sloane (shortest linear recurrence modulo any integer). Berlekamp-Massey for a composite modulus m: finds the shortest recurrence of a sequence mod m and computes its n-th term	Reeds-Sloane
25	resultant.cpp	Resultant and Naive Polynomial Euclid over a Field. Resultant Res(A, B) and polynomial remainder / gcd by schoolbook division, for any field type (no NTT needed)	Resultant
26	sparse-fps.cpp	Sparse Formal Power Series (inv / exp / log / pow / sqrt in O(n k)). First n coefficients of 1 / f, exp f, log f, f^M and sqrt f when f has only k non-zero terms	Sparse Series
27	subset-sum-count.cpp	Counting Subset Sums (#P Subset Sum via log / exp). For every s = 0..t, the number of subsets of a multiset of positive integers with sum s (mod 998244353)	Subset Sum Counting
28	taylor-shift.cpp	Taylor Shift and Shift of Sampling Points. Coefficients of f(x + c); values f(m), …, f(m + cnt - 1) from f(0), …, f(n - 1); sums of C(a_i, k) for all k	Taylor Shift

range-queries/ — segment trees, Fenwick trees, sparse tables, Mo, wavelets, offline range tricks

#	Template	What it does	Notes
1	cdq.cpp	CDQ Divide and Conquer (3D Dominance Counting). For every point, the number of other points that are <= it in all three coordinates, offline	CDQ Divide and Conquer
2	disjoint-sparse-table.cpp	Disjoint Sparse Table. O(1) range queries on a static array for any associative operation (sum, product, matrix, …)	Disjoint Sparse Table
3	distinct-in-range.cpp	Distinct Values in Ranges. Number of distinct values in each query range, offline with a Fenwick tree (also an online variant)	Distinct in Range
4	dynamic-range-kth.cpp	Dynamic Range K-th (Fenwick of Value Segment Trees). Point assignment, range k-th smallest and range rank queries on an array of values in [0, V)	Dynamic Range K-th
5	dynamic-segment-tree.cpp	Dynamic (Sparse) Segment Tree. Range add and range sum over a huge coordinate range [lo, hi), creating nodes on demand	Dynamic Segment Tree
6	fenwick-2d-range.cpp	2D Fenwick Tree with Range Update and Range Query. Add v to every cell of a rectangle and ask the sum over a rectangle, both in O(log n log m)	2D Fenwick
7	fenwick-2d.cpp	2D Fenwick Tree. Point add and rectangle sum on a grid, dense or offline over compressed coordinates	2D Fenwick
8	fenwick-nd.cpp	N-Dimensional Fenwick Tree. Point add and box sum in any fixed number of dimensions with compile-time sizes	Multidimensional Fenwick
9	fenwick-range.cpp	Fenwick Tree with Range Update. Range add and range sum with two Fenwick trees	Range Fenwick
10	fenwick.cpp	Fenwick Tree (Binary Indexed Tree). Point add, prefix/range sum and k-th element search on an array	Fenwick Tree
11	kinetic-segment-tree.cpp	Kinetic Segment Tree	Kinetic Segment Tree
12	lazy-segment-tree-iterative.cpp	Iterative Lazy Segment Tree (bottom-up). Non-recursive range update / range query with lazy tags (AtCoder Library style), with maxRight/minLeft	Lazy Propagation
13	lazy-segment-tree.cpp	Lazy Segment Tree. Range update (Tag) and range query (Info) with lazy propagation, plus binary search on the tree	Lazy Propagation
14	linear-rmq.cpp	Linear RMQ (O(n) build, O(1) query). Range minimum queries with O(n) preprocessing using 64-element blocks with bitmask stacks	Linear Range Minimum
15	merge-sort-tree.cpp	Merge Sort Tree. Segment tree whose nodes store their range sorted, to count elements below a value in a range	Merge Sort Tree
16	mo-dsu.cpp	Connectivity over Edge Ranges (Mo + Rollback DSU). For queries [l, r), the number of connected components using only edges l..r-1	Mo Connectivity
17	mo-online.cpp	Online Mo (Precomputed Block Ranges). Answers range queries online with point updates by keeping a structure for every pair of blocks	Online Mo
18	mo-rollback.cpp	Mo’s Algorithm with Rollback	Rollback Mo
19	mo-second-offline.cpp	Mo’s Algorithm, Second Offline (range pair counting in O(n sqrt q) with O(1) queries)	Second Offline Mo
20	mo-two-ranges.cpp	Mo’s Algorithm on Two Ranges (4D Mo). Offline queries about the multiset union of two windows [l1, r1) and [l2, r2) over the same array	Two-Range Mo
21	mo-with-updates.cpp	Mo’s Algorithm with Updates. Offline range queries mixed with point updates, by moving a window over (l, r, time)	Mo with Updates
22	mo.cpp	Mo’s Algorithm. Answers offline range queries by moving a window [l, r) with add/remove callbacks in Hilbert order	Mo’s Algorithm
23	offline-range-min.cpp	Offline Range Minimum (Arpa’s Trick). Answers all range-minimum queries offline in near-linear time with a monotone stack and a DSU	Arpa’s Trick
24	offline-rectangle.cpp	Offline Rectangle Queries (rectangle sum, rectangle add + point get, rectangle add + rectangle sum)	Rectangle Queries
25	permutation-tree.cpp	Permutation Tree (析合树). Tree of all “intervals” of a permutation (subarrays whose values are consecutive), built in O(n log n)	Permutation Tree
26	persistent-lazy-segment-tree.cpp	Persistent Lazy Segment Tree (range add, range sum). Every range addition creates a new version; range sums can be asked on any version	Persistent Lazy Segment Tree
27	persistent-segment-tree.cpp	Persistent Segment Tree. Point add creating a new version, range sum on any version, and k-th search between two versions	Persistent Segment Tree
28	range-lis.cpp	Range LIS Queries (seaweed / unit-Monge, Tiskin)	Range LIS
29	range-mode.cpp	Static Range Mode Query (online, O(sqrt n) per query). Most frequent value of a[l..r) and its frequency, online, for a static array	Range Mode
30	segment-tree-2d-dynamic.cpp	Dynamic 2D Segment Tree. Online point addition and rectangle sum over huge coordinates [0, X) x [0, Y), nodes created on demand	Dynamic 2D Segment Tree
31	segment-tree-2d.cpp	2D Segment Tree. Point assignment and rectangle query on an n x m grid for any commutative monoid (sum, min, max, gcd, xor)	2D Queries
32	segment-tree-ap.cpp	Segment Tree with Arithmetic Progression Updates. Add a, a + d, a + 2d, … to a range and ask range sums (works over i64 or any modint)	Arithmetic Progression Updates
33	segment-tree-beats.cpp	Segment Tree Beats. Range chmin, range chmax and range add with range sum, min and max queries	Segment Tree Beats
34	segment-tree-history.cpp	Segment Tree with Historic Maximum (range add / assign, max, historic max)	Historic Maximum
35	segment-tree-iterative.cpp	Iterative Segment Tree (bottom-up). Non-recursive point update / range query segment tree for any monoid, with maxRight/minLeft	Iterative Segment Tree
36	segment-tree-merge.cpp	Segment Tree Merging and Splitting. Many dynamic segment trees over values [0, n) in one node pool: merge two trees, split by value or by count, k-th, range count	Segment Tree Merging
37	segment-tree.cpp	Segment Tree. Point update and range query for any monoid Info, with binary search on the tree	Segment Tree
38	sortable-segment-tree.cpp	Sortable Segment Tree (point set, range sort, range fold)	Sortable Segment Tree
39	sparse-table-2d.cpp	2D Sparse Table. O(1) rectangle queries for an idempotent operation (min, max, gcd, and, or) on a static grid	2D Sparse Table
40	sparse-table.cpp	Sparse Table. O(1) range queries for an idempotent operation (min, max, gcd, and, or) on a static array	Sparse Table
41	sqrt-decomposition.cpp	Sqrt Decomposition. Block decomposition template with range add, range sum and range min	Sqrt Decomposition
42	sqrt-tree.cpp	Sqrt Tree. O(1) range queries for any associative operation (not only idempotent ones), point update in O(sqrt n)	Sqrt Tree
43	static-to-dynamic.cpp	Static to Dynamic Transformation (Binary Grouping). Turns any static structure (build once, query many) with decomposable queries into one that supports insertions	Static to Dynamic
44	wavelet-matrix.cpp	Wavelet Matrix. Static array answering range k-th smallest, range count of values below x, range frequency and predecessor/successor	Wavelet Matrix
45	wavelet-tree.cpp	Wavelet Tree. Range k-th smallest, rank, frequency and sum of values <= x, plus swapping adjacent elements	Wavelet Tree
46	xor-segment-tree.cpp	XOR Segment Tree. Sum of a[p ^ x] over a range of positions p, for any xor mask x, with point additions	XOR Segment Tree

strings/ — matching, hashing, suffix structures, palindromes, LCS

#	Template	What it does	Notes
1	aho-corasick-dynamic.cpp	Dynamic Aho-Corasick (insert / delete patterns online)	Dynamic Aho-Corasick
2	aho-corasick.cpp	Aho-Corasick Automaton. Multi-pattern matching automaton with suffix links, dictionary links and complete goto transitions	Aho-Corasick
3	bitset-lcs.cpp	Bit-Parallel LCS. Longest common subsequence lengths in O(n m / 64): stream a against a fixed b and query LCS(a so far, any prefix of b)	Bit-Parallel LCS
4	bitset-matching.cpp	Bitset String Matching (Shift-And with updates)	Bitset Matching
5	bracket-sequence.cpp	Bracket Sequences (matching, nesting forest, range queries)	Brackets
6	bwt.cpp	Burrows-Wheeler Transform. BWT of a string (with a sentinel) via the suffix array, and its inverse	Burrows-Wheeler Transform
7	de-bruijn.cpp	De Bruijn Sequence. The lexicographically smallest cyclic sequence over k symbols that contains every length-n word exactly once	De Bruijn
8	distinct-substrings-in-range.cpp	Distinct Substrings in a Range (offline, suffix automaton + link-cut tree). For many queries [l, r), the number of distinct non-empty substrings of s[l..r)	Distinct Substrings
9	hashing-extra.cpp	Hashing Extras (2D grids, point updates, deques)	Hashing
10	isomorphic-substrings.cpp	Isomorphic Substrings (hashing per letter). Answers “are s[x, x+len) and s[y, y+len) isomorphic” (a letter bijection maps one to the other) in O(sigma log sigma) per query	Isomorphic Substrings
11	lcs-variants.cpp	LCS Variants (all substrings, cyclic rotations, semi-local seaweeds). LCS of s with every substring t[i, j] in O(/s/ /t/) total, and the maximum LCS of A with any rotation of B in O(/A/ /B/)	Longest Common Subsequence
12	lyndon.cpp	Lyndon Factorization and Minimal Rotation. Duval’s algorithm for the Lyndon factorization of a string and the lexicographically smallest cyclic rotation	Lyndon Words
13	manacher.cpp	Manacher’s Algorithm. Longest palindrome around every center in linear time, giving O(1) palindrome checks for substrings	Manacher
14	palindrome-factorization.cpp	Palindromic Factorization (eertree series links). For every prefix, the minimum number of palindromes it splits into (and one optimal split), in O(n log n)	Palindromic Factorization
15	palindromes-in-range.cpp	Counting Palindromic Substrings in a Range. Number of palindromic substrings (counted by position) of s[l, r), online, in O(log n) per query	Range Palindromes
16	palindromic-tree-rollback.cpp	Palindromic Tree with Rollback (quick links)	Eertree
17	palindromic-tree.cpp	Palindromic Tree (Eertree). All distinct palindromic substrings of a string, built online, with occurrence counts and palindromic suffix counts	Eertree
18	pattern-containment.cpp	Pattern Containment Relation (which patterns are substrings of which). For a set of k strings, the full relation “pattern i occurs inside pattern j”, via Aho-Corasick and a bitset transitive closure	Pattern Containment
19	prefix-function.cpp	Prefix Function (KMP). Prefix function, KMP pattern search, occurrence counts of every prefix and the prefix automaton	Knuth-Morris-Pratt
20	runs.cpp	Runs (Maximal Repetitions). All runs of a string - maximal substrings s[l, r) with smallest period t and r - l >= 2t - by Main-Lorentz divide and conquer	Runs
21	string-hashing.cpp	String Hashing (mod 2^61 - 1). Polynomial rolling hash with a random base modulo 2^61 - 1: O(1) substring hashes, LCP and comparison of substrings	Hashing
22	subsequence-automaton.cpp	Subsequence Automaton (next occurrence table). For every position and letter, the next occurrence; answers “is t a subsequence of s” in O(/t/), and counts distinct subsequences	Subsequence Automaton
23	suffix-array-linear.cpp	Linear-Time Suffix Array (SA-IS) and LCP (Kasai). Suffix array in O(n + alphabet) by induced sorting, plus the LCP array in O(n)	SA-IS
24	suffix-array.cpp	Suffix Array. Sorted suffixes, their ranks and the Kasai LCP array, with O(1) LCP queries and pattern search	Suffix Array
25	suffix-automaton.cpp	Suffix Automaton. Minimal automaton of all substrings of one or several strings: distinct substrings, occurrence counts, longest common substring	Suffix Automaton
26	suffix-tree.cpp	Suffix Tree (Ukkonen). Online compressed trie of all suffixes, built character by character with Ukkonen’s algorithm	Suffix Tree
27	trie.cpp	Trie. Prefix tree over a multiset of strings: insert, erase, count copies of a word and words with a given prefix	Trie
28	wildcard-matching.cpp	Wildcard Pattern Matching. All positions where a pattern matches a text when a wildcard symbol on either side matches any single symbol, with NTT	Wildcard Matching
29	z-function.cpp	Z-Function. Z[i] = longest common prefix of s and s[i, n), plus the LCP of a pattern with every suffix of a text	Z-Function

trees/ — LCA, HLD, centroid / top trees, link-cut, tree DP helpers

#	Template	What it does	Notes
1	binarize-tree.cpp	Binarize a Tree	Binarization
2	centroid-decomposition.cpp	Centroid Decomposition. Centroid tree (parent and level of every vertex) with the distance from each vertex to all its centroid ancestors	Centroid Decomposition
3	centroid-queries.cpp	Centroid Tree Queries (nearest marked vertex, sum of distances, contour sums). Online point updates and distance queries on a tree through the centroid decomposition (dynamic “point divide”)	Centroid Decomposition
4	distance-counting.cpp	Counting Paths of Every Length in a Tree (Centroid + FFT). Cnt[d] = number of unordered pairs of vertices at distance d (edges), for every d	Path Length Counting
5	dsu-on-tree.cpp	DSU on Tree (Small-to-Large / Sack). Answers a query for every subtree by keeping the heavy child’s data and re-adding only light subtrees	Small to Large
6	dynamic-diameter.cpp	Dynamic Tree Diameter (edge weight updates). Maintains the diameter of a weighted tree under edge weight changes, online	Dynamic Diameter
7	edge-centroid-decomposition.cpp	Edge-Centroid Decomposition	Edge Centroid
8	euler-tour-tree.cpp	Euler Tour Tree. Dynamic forest (link, cut, reroot) with connectivity, component size/sum and subtree sums, as treaps over Euler tours	Euler Tour Tree
9	hld-path-queries.cpp	HLD + Lazy Segment Tree (path and subtree updates / queries). Ready-to-submit tree path toolkit: add to / query sum and max on any path or subtree, with vertex or edge values	Heavy-Light Decomposition
10	hld.cpp	Heavy-Light Decomposition. Rooted tree toolkit: LCA, distance, k-th ancestor, re-rooted queries, and O(log n) position ranges for any path or subtree	Heavy-Light Decomposition
11	kruskal-reconstruction-tree.cpp	Kruskal Reconstruction Tree. Binary tree of Kruskal merges: answers bottleneck-path queries and lists the vertices reachable using edges of weight <= x	Kruskal Reconstruction Tree
12	ladder-kth-ancestor.cpp	k-th Ancestor in O(1) (Ladder Algorithm). Level ancestor queries in O(1) after O(n log n) preprocessing, using binary lifting plus long-path ladders	Ladder Algorithm
13	lca-binary-lifting.cpp	Binary Lifting (LCA, k-th Ancestor, Path Aggregates). Jump tables over a weighted rooted tree for LCA, k-th ancestor and an aggregate of the edge weights on any path	Binary Lifting
14	lca-rmq.cpp	LCA in O(1) (Euler Tour + Sparse Table). Lowest common ancestor in O(1) per query after an O(n log n) sparse-table build over the DFS order	Lowest Common Ancestor
15	link-cut-tree.cpp	Link-Cut Tree. Dynamic forest with link, cut, reroot, connectivity, LCA and ordered path aggregates in O(log n) amortized	Link-Cut Tree
16	long-path-decomposition.cpp	Long-Path Decomposition. Lays out depth-indexed subtree DP arrays so that every vertex inherits its deepest child’s array in O(1), for O(n) total merging	Long Path
17	mo-on-tree.cpp	Mo’s Algorithm on Tree Paths. Offline path queries with add/remove callbacks by running Mo’s algorithm over the 2n-length Euler tour	Mo on Trees
18	path-utils.cpp	Tree Path Utilities (on path, k-th vertex on a path, path intersection). Common O(log n) questions about paths of a rooted tree, built on binary lifting	Path Utilities
19	persistent-centroid.cpp	Persistent Centroid Tree (sum of distances to a set, any version). Versions of a vertex multiset (each version = previous + one vertex) with online queries “sum of dist(v, x) over x in version k”	Persistent Centroid
20	prufer-code.cpp	Prufer Code. Linear-time bijection between labeled trees on n vertices and sequences of n-2 labels	Prüfer Code
21	rerooting.cpp	Rerooting DP. Computes a subtree DP for every choice of root at once, in O(n) calls of the combine functions	Rerooting
22	static-top-tree.cpp	Static Top Tree (tree DP with point updates in O(log n))	Static Top Tree
23	top-tree.cpp	Top Tree (path and subtree queries on a dynamic forest). Link/cut forest supporting path aggregates, subtree aggregates (w.r.t	Top Tree
24	tree-diameter.cpp	Tree Diameter, Center and Centroid. Longest path of a tree (unweighted or with non-negative weights), its center vertices, and the centroid(s)	Diameter
25	tree-hashing.cpp	Tree Isomorphism and Tree Hashing. Exact isomorphism classes of rooted subtrees (AHU), canonical ids of unrooted trees, and an O(n) randomized subtree hash	Isomorphism
26	tree-knapsack.cpp	Tree Knapsack	Tree Knapsack
27	virtual-tree.cpp	Virtual Tree (Auxiliary Tree). Compresses a tree to k marked vertices plus their pairwise LCAs (at most 2k - 1 vertices) in O(k log n)	Virtual Tree