Competitive Programming

A C++ code library that contains useful data structures and algorithms tailored for competitive programming contests.

PDF Version

[1] You can download an easy printable minified PDF version of this library from here.
[2] You can download Theoretical Computer Science Cheat Sheet from here.

Content

Data Structures

• Sparse Table
• Monotonic Queue
  • Implemented with two stacks
  • Implemented with double ended queue
• Disjoint-Sets (DSU)
• Interval Map
• Trees
  • Fenwick Tree (Binary Indexed Tree)
    • Basic Fenwick Tree
    • Fenwick Tree with Range Update
    • Fenwick Tree as Multiset
  • Segment Tree
    • Basic Segment Tree (static memory allocation)
    • Basic Segment Tree (dynamic memory allocation)
    • Persistent Segment Tree
    • Segment Tree as Multiset
  • Treap
  • Splay Tree (coming soon)
• SQRT Decomposition
  • Mo's Algorithm

Strings

• KMP
• Z-Algorithm
• Trie
  • Implemented with static memory allocation
  • Implemented with dynamic memory allocation
• Suffix Array
  • Suffix Array O(n.log^2(n))
  • Suffix Array O(n.log(n))
• Aho Corasick's Algorithm (coming soon)

Graphs

• Graph Traversal and Representation
  • Optimized Representation
  • DFS
  • BFS
• Topological Sort
  • DFS
  • BFS (Khan's Algorithm)
• Shortest Path
  • Single Source Shortest Path (SSSP)
    • BFS
    • BFS on Complement Graph
    • Dijkstra's Algorithm
    • Bellman Ford's Algorithm
    • Optimized Bellman Ford's Algorithm
  • All Pair Shortest Path (APSP)
    • Floyd Warshal's Algorithm
• Minimum Spanning Tree
  • Kruskal's Algorithm
  • Prim's Algorithm
• Strongly Connected Components (SCC)
  • Kosaraju's Algorithm
• Lowest Common Ancestor (LCA)
  • Implemented with parent sparse table
  • Implemented with Euler walk and RMQ
• Max Flow
  • Edmonds-Karp's Algorithm
• Others
  • Tree Diameter
  • Bipartite Graph Check
  • Graph Bridges
  • Bridge Tree

Math

• Basic Discrete Math & Modular Arithmetics
  • Greatest Common Divisor (GCD)
  • Least Common Multiple (LCM)
  • Bézout's Coefficients (using extended Euclid's method)
  • Fast Power
  • Modular Inverse
  • Combinations (nCr)
  • Combinations (nCr) for Large Numbers
  • Pascal Triangle
  • Check Integer Primality
  • Check Integer Primality using Miller Rabin
  • Generate Prime Numbers (using Sieve of Eratosthenes' algorithm)
  • Generate Divisors (single/bulk operation)
    • All divisors
    • Prime divisors
• Matrix Operations
  • Matrix Class
  • Matrix Power

Geometry

Will be added soon...

Search Algorithms

• Binary Search
• Ternary Search

Sorting Algorithms (coming soon)

• Heap Sort
• Merge Sort
• Quick Sort
• Radix Sort

Other Algorithms

• K-th Order Statistic
• Longest Increasing Sub-sequence (LIS)
• Stress test code
• Code definitions

Thanks

Special thanks to anyone contributed to this repository:

• By teaching me any of these topics.
• By inspiring me any code optimizations.
• By being supportive.