Competitive programming stuffs Data structures and algorithms for competitive programming. Note: This is a publish-only repository and all pull requests are ignored. Data Structures Fenwick tree Fenwick tree 2D Disjoint set union DSU w/ rollback Minimum queue Segment tree Segment tree w/ lazy propagation Persistent segment tree Sparse table Ordered set Treap Implicit Treap Merge sort tree Graph Dijkstra Bellman-Ford Floyd-Warshall Kruskal Boruvka Binary lifting Eulerian path Topological sort Centroid decomposition Heavy-light decomposition Edmonds Karp Dinic's algorithm Kosaraju 2-SAT De Bruijn sequence Kuhn's algorithm Dynamic Programming Longest common subsequence Longest palindromic subsequence Longest increasing subsequence - naive O(N^2) Longest increasing subsequence - fenwick tree O(NlogN) Longest increasing subsequence - dp & bns O(NlogN) Travelling salesman problem O(N^2*2^N) Math Discrete logarithm Discrete root Extended GCD Linear sieve for divisors count Linear sieve for divisors sum Linear sieve for Euler's totient function Linear Eratosthenes sieve Least prime factor Matrix exponentiation Euler's totient function Pollard's Rho 128 bit Pollard's Rho Primitive root Rabin–Miller primality test Segmented sieve Modular multiplication 64 bit in O(1) Ternary search Binomial coefficient w/ Lucas Theorem Gaussian elimination Gaussian elimination XOR String Longest palindromic substring O(N^2) Hashing Hashing w/ update Hashing 2D Rabin-Karp Prefix function Prefix automaton Suffix automaton Z function KMP Trie Lyndon factorization (Duval algorithm) Suffix array Longest Common Prefix (Kasai's algorithm) Others Mo's algorithm First element greater than element i from left/right Check ancestor in O(1)
