Template library

Copy-paste implementations of the algorithms that win contests: C++ and Python, each with a problem to test it on.

Data Structures

disjoint sets

DSU (Union-Find)O(α(n)) per operation

range queries

Segment TreeO(log n) per query Lazy Segment TreeO(log n) per operation Fenwick Tree (BIT)O(log n) per operation Sparse TableO(1) query, O(n log n) build

offline queries

Mo's AlgorithmO((n + q)·√n)

Graph Algorithms

shortest paths

DijkstraO(m log n)0-1 BFSO(n + m)Bellman-FordO(n·m)Floyd-WarshallO(n³)

spanning trees

Kruskal (MST)O(m log m)Prim (MST)O(m log n)

connectivity

SCC (Kosaraju)O(n + m)SCC (Tarjan)O(n + m)Bridges & Articulation PointsO(n + m)

dags & satisfiability

Topological Sort (Kahn)O(n + m)2-SATO(n + m)

euler tours

Euler Circuit / Path (Hierholzer)O(n + m)

matchings & flows

Bipartite Matching (Kuhn)O(V·E)Dinic (Max Flow)O(V²E), O(E√V) bipartite Min-Cost Max-FlowO(F·V·E) worst case Hungarian AlgorithmO(n²m)

Tree Algorithms

LCA (Binary Lifting)O(log n) per query Heavy-Light DecompositionO(log² n) per path query Euler Tour (Subtree Flattening)O(n) build Centroid DecompositionO(n log n) build Tree Isomorphism (AHU)O(n log n)

Dynamic Programming

classics

LIS (Patience Trick)O(n log n)0/1 KnapsackO(n·W)

bitmask

Enumerating Subsets & SubmasksO(2^n), submasks O(3^n) total Bitmask DP (Hamiltonian Paths)O(2^n · n²)SOS DP (Sum over Subsets)O(2^n · n)

digits & optimization

Digit DPO(digits · states · 10)Li Chao Tree (CHT)O(log C) per line / query

Strings

KMP (Prefix Function)O(n)Z AlgorithmO(n)ManacherO(n)Rolling HashO(1) per substring hash TrieO(|s|) per operation Aho-CorasickO(total pattern length + text)Suffix Array + LCPO(n log² n)

Mathematics

Modular ArithmeticO(log e) per power/inverse Extended GCD & CRTO(log min(a, b))Sieve (Smallest Prime Factor)O(n log log n)Binomial Coefficients (nCr)O(1) per query after O(n) setup Matrix ExponentiationO(k³ log e)NTT (Convolution)O(n log n)

Geometry

Geometry PrimitivesO(1) per operation Convex Hull (Monotone Chain)O(n log n)Closest Pair of PointsO(n log n)