C++ Templates for Competitive Programming
Main file is Data Structures.cpp
See also: zscoder's template
List of things (in order):
-
Segment/Fenwick tree
-
String algorithms
- Prefix function (KMP)
- Z-algorithm
- Trie
- Suffix Array
-
Graph theory
- Algorithms/DS
- DSU (Disjoint-set union)
- Kruskal
- Dijkstra
- Floyd-Warshall
- SPFA (Shortest path faster algorithm)/Bellman-Ford
- Dinic Flow O(V^2E)
- Edmonds-Karp: Min Cost Max Flow
- Hopcroft-Karp matching (max-cardinality bipartite matching/MCBM)
- Strongly connected component (SCC): Tarjan's algorithm
- Common Techniques
- Euler tour compression
- Heavy-light decomposition (HLD)
- Lowest Common Ancestor (LCA)
- Euler tour method: O(log n) query
- Depth method: O(log n) query
- Sparse table: O(1) query but long
- Centroid decomposition: solving for all paths crossing current centroid
- Algorithms/DS
-
Data structures
- Sparse table
- Convex hull trick (CHT)
- Dynamic version: O(log n) query
- Offline version: O(1) query
-
Maths
- Combinatorics
- Modular operations: Add, mult, inverse, binary exponentiation, binomial coefficients, factorials
- getpf(): O(sqrt(n)) prime factorization
- Matrix exponentiation
- Number theory
- Combinatorics
-
Square root decomposition/Mo's algorithm
-
Fast Fourier Transform (FFT)
-
Miscellaneous
- Randomizer (Mersenne prime twister, mt19937)
- unordered_map/hash map custom hash (http://xorshift.di.unimi.it/splitmix64.c)
- Binary converter: print numbers in binary
- Grid movement: 4/8 directions
- Nearest pair of points