CP-codes

My coding library for Competitive Programming.
Contains snippets for various Data Structures and Algorithms one finds in CP.

Index

Data Structures

• Disjoint Set Union
• Fenwick Tree
• Fenwick Tree 2D
• Ordered Set
• Persistent Segment Tree
• Segment Tree (lazy propagation included)
• Segment Tree 2D
• Segment Tree for Subarry Sum
• Trie For String
• Trie for Bits

Dynamic Programming

• Line Container for Convex Hull Trick
• Divide and Conquer DP optimisation trick
• Sum over Subsets (SOS) DP example

Graphs

• 2 Satisfiability Problem
• Articulation Points and Bridges
• 2D Breadth First Search
• Biconnected Components
• Bridge Tree
• Strongly Connected Components

Math

• Convex Hull
• Extended Euclidean Algorithm and Chinese Remainder Theorem
• Binomial Coefficients
• Fast Fourier Transform (iterative)
• Fast Fourier Transform (recursive)
• Matrix Exponentiation
• Miller Rabin Primality Test
• Mobius function using linear sieve
• Binomial Coefficients (simple)
• Point Structure
• Pollard's Rho Algorithm for fast integer factorization
• Binary Exponentiation (Power function)
• Primitive Root
• Reduce Fraction function
• Linear Sieve
• Segmented Sieve
• Sieve
• Totient function (linear sieve)
• Totient function

Strings

• Knuth Morris Pratt Algorithm
• Manacher's Algorithm
• Suffix Array - N(logN)^2
• Suffix Array - NlogN
• Z Algorithm

Tree

• Centroid Decomposition
• DSU on trees
• Euler Path - Hierholzer's Algorithm
• Euler Tour
• Heavy Light Decomposition
• Lowest Common Ancestor - Binary Lifting

Z_extra

• The Big int
• Counting Inversions
• Custom Hash for Unordered Map and Set
• Debugging-code
• Josephus problem
• XOR Maximization (SPOJ problem)
• Modulo operations
• Mo's algorithm
• N-dimensional Vector Template
• Random number generator
• Ternary Search

Template