- Graph Traversal
- Single Source Shortest Path (SSSP)
- All Pair Shortest Path (APSP)
- Minimum Spanning Tree
- Articulation
- Miscellaneous
- Power & Modulus
- Extended Euclidean Algorithm
- nCr
- Sieve of Eratosthenes
- General Sieve : O( N log(logN) ) , Memory : O(N)
- Bit Sieve : O( N log(logN) ) , Memory : N bit
- Segmented Sieve : O( (R-L+1) log(logR) + sqrt(R) log(log(sqrt(R))) ) , Memory : O(R-L+1)
- Prime Factorization
- Using all primes : O( (sqrt(N)/log(sqrt(N)) * logN )
- Using only smallest prime factor : O(logN)
- Divisors
- Euler Totient
- Linear Diophantine
- Highest Composite Number
- Factorials
- Number of digits in N factorial
- Prime Factorization of N Factorial O(N*log(N))
- Find the first K digits of N!
- Chinese Remainder Theorem
- Suffix Array : O( NlogN )
- Longest Common Prefix (LCP) Array Construction : O(N)
- Prefix Function (KMP ALgorithm) : O(N)
- Disjoint Set
- Binary Indexed Tree / Fenwick Tree
- 1D BIT
- Point Update , Range Query , lower_bound , upper_bound
update , query : O(logN)
lower_bound , upper_bound : binary search - O( (logN)^2 ) , binary lifting - O(logN) - Range Update , Point Query
update , query : O(logN)
- Point Update , Range Query , lower_bound , upper_bound
- 2D BIT
- 1D BIT
- Segment Tree
- Range Sum
- Point Update , Range Query
( Possible Variations : Range [ Multiplication , Min , Max , GCD , LCM , and , or , xor ] )
build : O(n)
update , query : O(logN) - Range Update , Range Query (Lazy Propagation)
- Point Update , Range Query
- Maximum Prefix Sum & Maximum Suffix Sum & Maximum Contiguous SubArray Sum
- Range Sum
- Merge Sort Tree
- Range Query
build : O( NlogN )
query : O( (logN)^2 )
memory : O( NlogN ) - Point Update , Range Query
build : O( N (logN)^2 )
update , query : O( (logN)^2 )
memory : O( NlogN )
- Range Query
- Sweep Line Algorithm
- Mo's Algorithm (Square Root Decomposition)
- Suffix Array
- Priority Queue
- STL
- Policy Based Data Structure
- Set
- Multiset
- Implementation 1 (erase doesn't work)
- Implementation 2
- LCS Variant
- LIS Variant
- Coin Change
- Matrix Variant
- Knapsack Variant
- Digit DP Variant
- Bitmask DP
- Miscellaneous
-
Operator Overloading for sorting / STL Data Structure
-
Geometry Template
Computer Science & Engineering Department , BUET