ICPC Template Library

What it is

ICPC style contests allow a printed team notebook, so the templates in it need to be correct, short, and easy to recall under pressure. This library collects the ones I use, ordered by how often they come up, with only the notes needed to remember how each one works.

The full notebook lives in ICPC Templates, and every topic also has a longer write up in the Code section.

What is inside

1. Starter & essentials: starter file, discretization, binary and ternary search on the answer, fast power
2. Data structures: DSU, BIT, sparse table, lazy segment tree, persistent segment tree, FHQ treap, splay, Mo's algorithm, Li Chao tree, segment tree beats, K-D tree
3. Graph & tree: Dijkstra, SPFA, 0-1 BFS, MST, LCA, heavy-light decomposition, Tarjan (SCC, cut vertex, bridge), 2-SAT, Dinic max flow, centroid decomposition, virtual tree
4. Math: exgcd, inverses, sieves, combinatorics, CRT / exCRT, BSGS, matrix power, Gaussian elimination, XOR basis, Möbius inversion
5. Strings, DP, polynomial and misc: hashing, KMP, Manacher, trie, Aho–Corasick, knapsack, LIS / LCS, interval DP, FFT, bignum
6. Appendix: STL cheat sheet, fast I/O, and a stress testing script

How it is built

The notebook is written in Markdown so it renders on this site with syntax highlighting, and kept in a LaTeX version for printing.