README.md

Data structures and algorithms library.

Repository with implementations and explanations of the following data structures and algorithms used in competitive programming.

Searching:

• Binary search
• Jump search
• Exponential search
• Ternary search
• Quick select

Sorting:

• Selection sort
• Bubble sort
• Insertion sort
• Quick sort
• Merge sort
• Heap sort
• Counting sort
• Radix sort

Basic Data Structures:

• Linked list
• Doubly linked list
• Stack
• Queue
• Heap
• Hash table

Graphs:

Fundamentals:

• DFS
• BFS
• Topological sort
• Find cycles
• Number of paths of fixed length
• Find bridges
• Find articulation points
• Dijkstra
• Belman Ford
• Floyd Warshall
• Prim
• Kruskal
• Max flow (Edmonds Karp)

Advanced:

• Shortest Path Faster Algorithm (SPFA)
• Strongly connected components (Koraraju)
• Boolean 2 satisfiability (2-SAT)
• K-th ancestor
• Lowest common ancestor (LCA)
• Max flow (Dinic)
• Max flow (MPM)
• Min cost max flow (assignment problem)
• Virtual tree
• A*

String matching:

• Rolling hash
• Rabin Karp
• Trie (Prefix Tree)
• Knuth Morris Pratt (KMP)
• Aho corasick (KMP Generalization)
• Suffix array
• Hash segment tree

Range Query:

• Sqrt decomposition
• Sparse table
• 2D Sparse table
• Fenwick tree (BITree)
• Segment tree
• 2D Segment Tree
• Merge sort segment tree
• Implicit treap

Persistance:

• Persitent array
• Persistent segment tree

Math:

• Fast pow
• Matrix fast pow
• Sieve of Eratosthenes
• Fast Fourier transform

Geometry:

• Convex hull (Graham Scan)
• KD tree