CodeISM Competitve Programming Template Library
The aim of this repository is to provide copy-pastable code snippets. Focus is more on efficiency/performance as opposed to readability.
Code snippets in a file are meant to be self sufficient.
Note: A modern C++ compiler with support of c++14 or later is required although most the files might work with lower versions too. Code is gauranteed to work with GCC/LLVM (Clang) toolchain but most of the code is portable across compilers and architectures.
- BIT/Fenwick Tree: Supports prefix queries and point update in O(log N) after taking O(N) time to build with O(N) space.
- Min Deque: Finding minimum element out of current element in the deque. Overhead of one integer per element, but is quite space efficient in practice.
- Ordered set: Dyanmic Order statistics in O(log N). Uses GNU's policy based data structure (pbds).
- Sparse Table: Static data structure that can answer queries in O(1) after O(NlogN) preprocessing (for some functions).
- DSU/Union-Find: Works in O(alpha(N)) and uses union by size heuristics.
- 2-SAT: solves 2-SAT problem in O(#boolean variables + #clauses) with CNF based formulation.
- DSU on tree: In O(NlogN) answer all queries of type: How many vertices in the subtree of vertex v has some property?.
- Tarjan's Offline LCA: Most optimal algorithm for solving LCA. O(DFS + Q).
- Wheel Factorization: 25% faster than sqrt(n) trial division
- GCD (Greatest Common Divisor): Iterative/Compile time constant
- Extended Euclid: iterative version, much faster than recursive.
- Modular Exponentiation: constexpr version.
- Fibonacci Number: Time: O(logN) but much faster (small constant) than matrix exponentiation version. Uses iterative table doubling method.
- Matrix: highly optimized: multiplication, exponentiation, transpose including versions with modular arithmetic.
- Modular Arithmetic: A convenient and efficient wrapper of plain
intfor modular arithmetic. Functionality provided: add, subtract, multiply, divide, exponentiation, inverse and IO. - Ska Sort: A much faster (2x w.r.t. std::sort) sorting algorithm.
- All Permutations: Generate all permutations of a sequence (iterative) in some order (not lexicographic).
- N-D vector: A less cumbersome declarator of next N-Dimensional
std::vector.
- Update this readme with new (updated) content
- Test the implementation for bugs
Many of the implementations are common in folklore of competitive programming and the authour is unknown. Whenever possible author of the code is added. Kindly contact us in case of any issues.