Templates for competitive programming and DSA library

DS

#Stacks Queues Priority queue Hashmap Linked List Trees Heaps Advanced Trees Tries Segment trees Fenwick tree or Binary indexed trees RMQ SQRT Decomposition Disjoint Data Structure C++ STL (optional) Algo Number Theory

Prime Numbers (Sieve of Eratosthenes) GCD and LCM Euclid’s Algorithm Modular Exponentiation Long arithmetic (Multi, Add) Efficient Prime Factorization Combinatorics(Probability-Combinations-Permutations-Matrix..)

Computational geometry

Primitive Operations Intuition Polygon Inside, Outside Implementing CCW Immutable Point ADT Convex Hull Closest pair problem Line intersection Sorting

QuickSort Counting Sort Merge Sort Searching

Binary Search Ternary Search Graph Theory

Depth First Search (DFS) Breadth First Search (BFS) Dijkstra’s Shortest Path Minimum Spanning Tree Ford Bellman Floyd Warshall LCA (Lowest Common Ancestor) Max Flow / Min Cut Dynamic programming

Knapsack Matrix chain multiplication Coin Change Kadane Longest increasing Subsequence (with RMQ) Strings

Z algorithm Suffix Trees/Arrays Knuth-Morris-Pratt Algorithm (KMP) Rabin-Karp Algorithm Hash Bit Manipulation

Game theory

Nim game Grundy numbers Sprague-Grundy theorem Optional Advanced Algorithms

AVL Trees Graph Coloring Mo's Algorithm Palindromic Tree Heavy Light Decomposition Dynamic Programming by Profile Rod Cutting Topological Sorting DP with Bitmask - Dynamic Programming Diobhantine Equation - Math Flood Fill - Graph

Big O Notation

Prime Numbers (Sieve of Eratosthenes) Efficient Prime Factorization Modular Exponentiation

GCD and LCM Euclid’s Algorithm Long arithmetic (Multi, Sum, Div, Sub) C++ STL:Vector C++ STL:Pairs C++ STL:Iterators

QuickSort Counting Sort C++ STL:String C++ STL:Set C++ STL:Map

Merge Sort Binary Search Ternary Search

Queue (DS) Stack (DS) Breadth First Search Depth First Search C++ STL: Queue C++ STL: Stack

Linked List (DS) Dijkstra’s Shortest Path Minimum Spanning Tree (MST) Floyd Warshall Cycle Detection (Union Find)

Knapsack Coin Change Kadane

Trees (DS) Segment Trees (DS) Range Minimum Query (RMQ) Lowest Common Ancestor (LCA) Topological Sorting

Ford Bellman Max Flow / Min Cut Longest increasing Subsequence (with RMQ) Heavy Light Decomposition

Primitive Operations Intuition Polygon Inside, Outside Implementing CCW Immutable Point ADT Convex Hull Closest pair problem Line intersection

Tries (DS) Suffix Trees/Arrays (DS) Knuth-Morris-Pratt Algorithm (KMP) Rabin-Karp Algorithm

Heaps (DS) Priority queue (DS) Combinatorics

Z algorithm Hash Disjoint Data Structure (DS)

Matrix chain multiplication SQRT Decomposition (DS) Mo's Algorithm Rod Cutting

Nim game Grundy numbers

Sprague-Grundy theorem Fenwick tree or Binary indexed trees (DS)

Bit Manipulation Palindromic Tree AVL Trees

Heavy Light Decomposition Dynamic Programming by Profile Graph Coloring and algo from cp algorithm