CP Reference Codes

My implementations of various data structures and algorithms for competitive programming.

Contents

0. Basic Template
   0.1. C++ Basic Template
   

1. Data Structure
   1.1. Union Find
   1.2. Segment Tree
   1.3. Merge Sort Tree
   1.4. Fenwick Tree
   1.5. Li Chao Tree
   

2. Graph
   2.1. Dijkstra's, Bellman-Ford, Floyd-Warshall
   2.2. Minimum Spanning Tree
   2.3. Topological Sort
   2.4. SCC, 2-SAT
   2.5. BCC
   2.6. Euler Circuit
   

3. Tree
   3.1. LCA in O(logN) (Sparse Table)
   3.2. Euler Tour Technique
   3.3. Heavy-Light Decomposition
   3.4. Centroid Decomposition
   

4. Network Flow
   4.1. Maximum Flow
   4.2. Dinic's Algorithm
   4.3. Bipartite Matching
   4.4. Hopcroft-Karp Algorithm
   4.5. MCMF
   

5. String
   5.1. Rabin-Karp Algorithm
   5.2. KMP Algorithm
   5.3. Trie
   5.4. Aho-Corasick
   5.5. Suffix Array
   5.6. Manacher's Algorithm
   5.7. Z Algorithm
   

6. Geometry
   6.1. CCW Algorithm
   6.2. Convex Hull
   6.3. Rotating Callipers
   6.4. Ray Casting
   6.5. Sort by Angular
   6.6. Bulldozer Trick
   6.7. Minimum Enclosing Circle
   

7. Math
   7.1. Basic Sqrt-Time Algorithms
   7.2. Sieve
   7.3. Euclidean Algorithms
   7.4. Fermat's Little Theorem
   7.5. Euler's Phi Function
   7.6. Chinese Remainder Theorem
   7.7. Binomial Coefficient
   7.8. Matrix
   7.9. Catalan Number, Derangement Number
   7.10. FFT
   7.11. Gauss-Jordan Elimination
   7.12. Miller-Rabin Test, Pollard Rho Factorization
   

8. Misc
   8.1. Coordinate Compression
   8.2. 2D Prefix Sum
   8.3. DP Opt
   8.4. Sqrt Decomposition, Mo's Algorithm
   8.5. Fraction Data Type
   8.6. Rotation Matrix, Manhattan Distance, Chebyshev Distance
   8.7. Random
   8.8. Ternary Search
   8.9. LIS in O(NlogN)
   8.10. System of Difference Constraints
   8.11. SIMD