Competitive-Programming-Repository

Collection of algorithms and data structures in C++ used widely in Competitive programming contests.

The following topics are covered:

Range Updates and Queries

• Range Aggregate Queries :
  • Binary Indexed Trees (BIT) :
  • Point Update Range Query
  • Range Update Range Query
  • Order Statistic Query
  • 2D Binary Indexed Trees
  • Segment Trees (SegTree) :
  • Point Update Range Query
  • Fast Iterative Segtrees
  • Range Update Point Query - Lazy Propogation
  • Max subsegment sum in range
  • 2D Segment Trees
  • Dynamic Segment Trees - Insertion/Deletion between elements
  • Dynamic Segment Trees - Reverse a segment
  • Merge Sort Trees :
  • Merge sort trees
  • Merge sort trees - Order Statistics
  • Sparse Table :
  • Range Minimum Query
  • Mo Algorithm :
  • Mo Algorithm - Arrays
• Dynamic Programming :
  • Dynamic Programming Templates :
  • Digit DP / Bitwise DP
  • Standard DP Problems :
  • Longest Increasing Subsequence
  • Longest Palindromic Subsequence
  • Levenstein Distance / Edit Distance
• Graphs :
  • Single Source Shortest Path Algorithms :
  • Dijkstra in dense graphs
  • Dijkstra using priority queue
  • Kth Shortest Path between Nodes using Dijkstra
  • Bellman Ford Negative cycle detection
  • All Pair shortest path :
  • Using Binary exponentiation
  • Floyd Warshall
  • Cycle Detection :
  • Cycle detection in Undirected/Directed Graphs
  • Minimum Spanning tree :
  • Kruskal Algorithm
  • Topological Sort / Strongly Connected Component :
  • Topological Sort
  • Strongly Connected Component
  • Maxflow/Matching :
  • Hopkroft Karp Max Matching
  • Dinic Max Flow
  • Misc :
  • Bridges in Graph
  • Connectivity
  • Bipartite Check
• Trees :
  • Ancestor queries :
    • Lowest Common Ancestor
    • Kth Ancestor
  • Path queries :
    • Sparse Table *
    • Heavy Light Decomposition Weighted Nodes
    • Heavy Light Decomposition Weighted Edges
  • Misc :
    • Diameter of Tree
    • Preorder/Postorder stamps, Is it in Subtree?
• Binary Exponentiation :
  • Calculate n^m using Binary exponentiation
  • Solving Linear Recurrences
• Strings :
  • String Algorithms :
    • Z Algorithm
    • KMP algorithm
    • Rolling String Hashing
    • Rolling String Hashing for Dynamic Strings
  • String Data Structures :
    • Suffix Array *
• Sorting :
  • Merge Sort
  • Quick Select
• Fast Input/Output, String/Integer Conversion :
  • Fast Input/Output
  • String/Integer Conversion
• Misc. Data Structures :
  • Disjoint Set
  • Disjoint Set (Supports Undo Operation)
  • Max/Min Priority Queue with update
  • Binary Trie for xor maximization/minimization
  • Bigint *
  • Augmented Binary Tree for order statistics and rank query
  • Monotone Priority Queue
  • Trie
• Persistent Data Structures :
  • Persistent Segment Trees (SegTree) :
  • Persistent Segment Tree
  • Persistent Segment Tree - Order Statistics
• Number Theory Algorithms :
  • Primality Check :
    • Fermat's Primality Check
  • Sieve :
    • Sieve of Eratosthenes
    • Segmented Sieve for large primes
    • Counting Prime Factors
  • Polynomial Multiplication :
    • Fast Fourier Tranform
    • Karatsuba
  • Misc :
    • Combinatorial and Catalan - Factorial preprocessing
    • Mobeius Function
    • Euler Totient Function
    • Lucas Theorm - Combinatorics
• Computational Geometry :
  • Convex Hull
• Misc :
  • Sum of floor(x) with x=1:n
  • Sum of cyclic functions *
  • Closest larger element before/after every element
  • Multiply Long Long Integers
  • Multiply Long Long Integers - Overflow detection
  • Scanline - Merge intersecting intervals