This repository contains algorithms that I learned through my journey on competitive programming:

• Data Structures

  • Segment Tree
  • Binary Indexed Tree
  • Dynamic/Persistent Segment Tree
  • Trie
  • Lichao Segment Tree (Online Convex Hull Trick)/ Integer and Float Version
  • Offline Convex Hull Trick
  • Ordered Set
  • Implicit Treap
  • Splay Tree

• Uncategorized

  • Longest Increase Subsequence
  • 2D Longest Increase Subsequence
  • Inversion Count Offline (Merge-Sort)
  • Mos Query Decomposition
  • Find kth permutation

• Basic 2D Geometry

  • Point/Vector Structure
  • Vector Structure
  • Line/Segment Structure
  • Distance from Point to Line
  • Distance from Point to Segment
  • Distance from Line to Segment
  • Distance from Point to Ray
  • Distance from Segment to Ray
  • Distance from Line to Ray
  • Distance between Segments
  • Distance between Rays
  • Distance between Lines
  • Line-Line Intersection
  • Segment-Segment Intersection
  • Line-Segment Intersection
  • Circle-Circle Intersection Area
  • Circle-Circle Intersection Points (NOT TESTED)
  • Tangent Line to a Circle Given a Point
  • Circle of Radius R Passing Through 2 Given Points
  • Barycenter, Circumcenter, Incenter, Excenter, Orthocenter, Centroid...

• 2D Geometry Algorithms

  • Closest Pair of Points
  • Convex Hull(Monotone Chain) + Perimeter/Area Calculation
  • Smallest Enclosing Circle Randomized Algorithm
  • Check if a Point Lies in Convex Hull
  • Largest quadrilater given a set of distinct points
  • Check if line intersects polygon
  • Maximum dot product queries

• Math and Number Theory

  • Binomial Coefficient
  • Euler Totient
  • Sieve of Erathostenes
  • Miller Rabin Primality Test
  • Count Primes/Divisors for Large Numbers + Sum Of Divisors of a Number
  • Matrix Exponentiation
  • Fast Fourier Transform (Iterative + Recursive)
  • Chinese Remainder Theorem
  • Diophantine Equations
  • Shank's Baby-Step Giant-Steps

• Strings

  • Knuth - Morris - Pratt (KMP)
  • Z-Function
  • Rolling Hash
  • Aho-Corasick
  • Suffix Array + Linear Sorting (O(nlogn) S.Array)

• Graphs

  • LCA
  • Max-Flow (Dinic's Algorithm)
  • Minimum Path Cover in Directed Acyclic Graphs
  • Minimum Edge Cover in Bipartite Graph
  • Minimum Cut in Flow Network
  • Minimum Vertex Cover in Bipartite Graph
  • Bellman Ford Shortest Path Algorithm
    • Dynammic Connectivity for connected(u,v) - query
    • Eulerian Circuit Directed/Undirected Graphs
    • Tarjan Algorithm for Bridges/Articulation Points
    • Heavy-Light Decomposition
    • Centroid Decomposition
    • Kosaraju's Strong Connected Components Algorithm