faiz28/Competitive-programming

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