Competitive Programming Notebook

66 snippets across 7 categories. Also available as a printable PDF.

Data Structures

Fast Bitset — Fixed-size bitset (compile-time N), faster than std::bitset for shift-heavy workloads (bitset-DP via <<=, |=) because it exposes find_next/find_prev directly instead of forcing a linear scan.
Fenwick — Fenwick tree (BIT).
Fenwick 2d — 2D Fenwick tree.
Link Cut Tree — Link-cut tree over a fixed set of n labeled nodes (1-indexed; node 0 is a null placeholder).
Pbds Order Statistics Tree — Order-statistics tree via GCC's built-in policy-based tree.
Segment Tree Dynamic Lazy — Dynamic (sparsely allocated) segment tree over an implicit range, e.g.
Segment Tree Iterative — Iterative point-update segment tree, no recursion, no lazy propagation.
Segment Tree Lazy — Recursive segment tree, eager array build, range update with lazy propagation.
Segment Tree Max Subarray — Segment tree computing the maximum subarray sum (Kadane's) under point updates, via the merge trick: each node tracks sum / best-prefix / best-suffix / best-subarray.
Sparse Table — Sparse table for static range queries over an idempotent, associative op (default min).
Splay Implicit — Implicit (positional) splay tree: array-as-balanced-BST via splaying.
Splay Ordered Set — Order-statistics multiset via splay tree: insert/erase/find/rank/kth/ predecessor/successor.
Sqrt Decomposition — Sqrt decomposition over a static-size array: range add + range sum via per-block lazy tags and precomputed block sums.
Treap Implicit — Implicit (positional) treap: array-as-balanced-BST via randomized split/merge by subtree size.
Treap Ordered — Key-ordered treap: order-statistics multiset via insert/erase/rank/kth/ predecessor/successor, using split-by-key + priority-based merge (no rotations, no parent pointers).
Xor Trie — Binary trie over BITS-bit integers, multiset semantics via ref-counted soft erase (no physical deletion).

Graphs

Bipartite Check — Bipartiteness check via BFS 2-coloring, handles disconnected graphs.
Bridges — Tarjan bridge-finding via tin/low DFS, handles disconnected graphs.
Centroid Decomposition — Centroid decomposition solving "min #edges among paths of length exactly targetLen" (IOI Race).
Dijkstra — Dijkstra's algorithm on a non-negative-weight directed graph given as an adjacency list.
Dsu — Disjoint set union with path compression + union by size..
Eulerian Circuit — Hierholzer's algorithm for an Eulerian circuit on an undirected multigraph, starting/ending at node 0.
Floyd Warshall — Floyd-Warshall all-pairs shortest paths on a dense distance matrix (dist[i][j] = INF if no edge, dist[i][i] = 0).
Floyd Warshall Incremental — Add a single edge (u, v, w) to an all-pairs-shortest-path matrix already computed by floyd-warshall.h, in O(n^2) instead of recomputing full O(n^3) Floyd-Warshall.
Heavy Light Decomposition — Heavy-light decomposition: flattens a tree into O(\log n) contiguous ranges per root-to-node path.
Lca Binary Lifting — Lowest common ancestor via Euler tour (tin/tout) + binary lifting.
Lex Smallest Path — Lexicographically smallest walk from x to y in an unweighted graph: greedily extend to the smallest-labeled unvisited neighbor that still has a path to y avoiding already-visited nodes..
Small To Large — Small-to-large merging ("DSU on tree"): merge a child's set into the larger of the two and re-insert the smaller one's elements, giving O(n log^2 n) total instead of O(n^2) for per-node subtree aggregate queries.
Topo Sort — DFS topological sort with cycle detection on a directed graph, handles disconnected graphs.
Tree Center — Tree center(s) via leaf-peeling (repeatedly strip degree-1 nodes).

Dynamic Programming

Bitset Subset Sum — Subset-sum reachability via bitset shifts: which totals in [0, cap] are achievable using a subset of a[].
Digit Dp — Digit DP skeleton: count integers in [0, x] satisfying some digit-local constraint.
Edit Distance — Levenshtein edit distance (insert/delete/substitute, unit cost) via top-down memoization.
Edit Distance Bounded — "Is edit distance <= k?" in O(nk) instead of O(nm), by restricting the DP to the diagonal band |i - j| <= k (any optimal alignment outside the band would need > k edits already).
Knapsack 01 — 0/1 knapsack (each item used at most once), 1D rolling array.
Knapsack Unbounded — Unbounded knapsack / coin-change count-of-ways (each item usable any number of times), 1D rolling array.
Lis — Longest strictly-increasing subsequence via patience sorting, with reconstruction.

Strings

Aho Corasick — Aho-Corasick automaton over lowercase letters: add() each pattern (id < 32, tracked via bitmask), then build().
Kmp — KMP prefix function pi[i] = length of the longest proper prefix of s[0..i] that is also a suffix.
Manacher — Manacher's algorithm: longest palindromic substring centered at every position, both odd and even length, in linear time.
String Hashing — Polynomial string hashing, arithmetic mod 2^64-1 (not mod 2^64 — plain mod-2^64 overflow hashing is broken by well-known adversarial test data, e.g.
Suffix Array — Suffix array via radix-sort doubling, with the matching O(n) LCP pass woven into the same construction (kactl's SuffixArray).
Z Function — Z-function z[i] = length of the longest common prefix of s and s[i..].

Math

Euler Phi — Euler's totient function phi(n) (count of integers in [1,n] coprime to n), single-query via trial division, or a sieve for all of [1, maxn)..
Fft — Fast Fourier transform (in-place, iterative) and real-valued polynomial multiplication via the trick of packing two real sequences into one complex FFT..
Floor Sum Block Trick — Block/quotient iteration: floor(n/i) takes O(\sqrt n) distinct values as i ranges over [1, n], each held over a contiguous block [i, floor(n / floor(n/i))].
Inclusion Exclusion — Bitmask inclusion-exclusion: count of integers in [1, x] divisible by at least one of a small list of divisors (e.g.
Matrix Exponentiation — Matrix multiplication and exponentiation mod MOD, for linear recurrences / graph-walk-counting DP sped up via binary exponentiation..
Mod Basics — Modular exponentiation, single modular inverse (Fermat, MOD must be prime), and a linear-sieve inverse table for 1..MAXN-1 (MOD must be prime, MAXN < MOD)..
Ncr Factorials — nCr mod a prime via precomputed factorials + inverse factorials.
Ntt — Number Theoretic Transform (in-place, iterative) and exact polynomial multiplication mod `mod` (must be a prime of the form c*2^k+1 with a known primitive root).
Prime Factorization — Prime factorization via trial division.
Segmented Sieve — Primes in [l, r] for huge r (beyond what a direct sieve up to r would fit in memory), using base primes up to sqrt(r)..
Sieve — Sieve of Eratosthenes.
Xor Basis — XOR linear basis over GF(2), BIT bits wide.
Xor Basis Time — XOR linear basis over GF(2), BIT bits wide, tagged with insertion time.

Geometry

Closest Pair — Closest pair of points via divide and conquer.
Convex Hull — Convex hull via monotone chain.
Point — 2D point/vector primitive.
Point In Polygon — Point-in-polygon test for a simple polygon (convex or not).
Polygon Area — Polygon area via the shoelace formula.
Segment Intersection — Test whether segments (a,b) and (c,d) intersect (including touching at an endpoint or overlapping collinearly)..

Flows

Bipartite Matching — Maximum bipartite matching via augmenting paths (Kuhn's).
Dinic — Dinic's max flow with capacity scaling: process augmenting paths in decreasing order of a capacity threshold (31 phases, thresholds 2^30 down to 2^0) so large-capacity paths get pushed first.
Edmonds Karp — Edmonds-Karp max flow (BFS augmenting paths), same edge-list interface as dinic.h.
Mcmf — Min-cost max-flow via Dijkstra with Johnson's potentials (a PBDS pairing heap gives O(1) decrease-key).