Abu-Sayed11/Competitive-Programming-2

Data Structures & Algorithms & Some Freqently used basic code

Competitive Programming

Codes of Data Structures , Algorithms and Some freqently used basic code which i am using in competitive programming. I implemented most of them but some of them are collected.

Usefull Links :

• cp-algorithms
• CF Blog
• STL

Table of contents :

• Data Structure :
  • Fundamentals :
    • Squre Root Decomposition / Mo's Algo
    • Sparse Table RMQ
  • Binary Indexed Tree (BIT) :
    • BIT point update rnage query
    • BIT Range Update Range Query
  • Sgement tree :
    • Segment Tree
    • Iterative Segement tree
    • Maximum sub segment sum
  • Other Trees :
    • Disjoint Set Hacker Earth
    • Disjoint Set with undo operation
    • Trie with dynamic memory
    • Trie with array
    • Merge Sort Tree
• Graphs :
  • Graph traversal :
    • BFS
    • BFS in 2D Grid
    • DFS Basic Code
  • Single-source shortest paths :
    • Dijkstra using priority queue
  • All pair shortest paths :
    • Warshal Algorithm with find path
  • Connected components, bridges, articulations points :
    • Articulation Point
    • Articulation Bridge
  • minimum spannig tree :
    • Kruskal Algorithm
    • Prims Algo
  • Trees :
    • Heavy light decomposition Anudeep
    • DSU on tree(heavy-light decomposition style) CF Blog-1 CF Blog-2
  • Miscellaneous :
    • 2 Sat
    • Stable Marriage
• Dynamic Programming :
  • Recursive :
    • Digit Dp
• Maxflow/Matching
  • Maximum Bipartite Matching
  • Dinic Max Flow O(EV^2) Hacker Earth
  • Edmonds-Karp max flow O(VE^2)
• String Processing :
  • Fundamentals :
    • KMP
    • Rabin Carp String Matching
    • Suffix Array
• Back Tracking :
  • Combinition Generation
  • Permutation Generation
  • m-Colouring
• Big Interger :
  • Factorial
• Computetional Geometry :
  • Covex Hull :
    • Jarvis Algorithm
    • Graham Scan
• Binary Exponentiation :
  • Big Mode Recursive
  • Big Mode Non-Recursive
  • Matrix Exponent
• Combinatorics :
  • Inclusion Exclustion Hacker Earth
  • Catalan Number
• Number Theory Algorithms :
  • Sieves :
    • Sieve of Eratosthenes nlogn
    • Sieve of Eratosthenes O(n)
    • Bitwise Sieve
    • Segmented Sieve
    • Eulers Totient Sieve
  • Primality Check :
    • isPrime
    • Miller Rabin Preimality Test
  • Prime factorization :
    • Prime factorization O(sq(n))
    • Prime factorization on log n
  • Number-theoretic functions :
    • Number of Divisors sqrt(n)
    • Number of Divisor in Qube root
    • Sum of divisors
    • Totient Function
  • Miscellaneous :
    • Moduler Inverse
    • Gaussian Elemination
    • Chinese remainder theorem
    • Number of Primes
• Sorting Algorithms :
  • Bubble Sort
  • Insertion Sort
  • Selection Sort
  • Merge Sort
  • Quick Sort
• Miscellaneous :
  • Stern-Brocot tree