Codebook for programming I store some Advanced Algorithms and data structures here. Of course, everything here is implemented
I tried to explain the algorithm in the code
Template c++
- Basic Template
- Super Template
Number Theory
- Baby Step-Giant Step
- Phi Function
- Linear Seive
- PRIME TEST(miller_robin)
- PRIME TEST (BPSW)(100%)
- NUMBER OF PRIME FACTOR(10^18)
- NUMBER OF PRIME FACTOR(SQUFOF) Faster (10^18)
- NUMBER OF DIVISORS (1-10^18)
- Modular Inverse if mod is not prime
- Modular inverse(1 to N)__O(N)
- Factorial modulo (n!%p)
- DIVISORS ___SUM OF DIVISORS____MULT OF DIVISORS____N<=10^16
- ax+by=c everything ____extended euclid
- n! % k^x==0 find x
- Expression solving
- BURNSIDE LEMMA
- floor number sum
- quadric resduie (can any sqrt(x) represents with a number)
- Farey Sequence
- Chinese Remainder Theorem(Garner's)
- Sum of Kth power____Find (1^k+2^k+...+n^k %) mod____O(K)
Graph
- DSU
- MST
- Strongly Connected Component
- Dijkstra
- LCA
- Directed MST
- Floyd Warshall
- Articulation Point
- BellManFord (negative cycle ditect)
- Dinic's-Maxflow
- Dominator Tree
- MaxFlowMinCut(SPFA)
- Centroid Decomposition(normal Implementation)
- Centroid Decomposition(Path Problem)
- Finding the shortest path of two-node in every query
- HopcroftKarp (BPM Unweighted)
- LCA finding ____offline query ___O(1) time each query
- dynamic connectivity problem
- Blossom Algorithm (maximum matching in the general graph)
- BronKerbosch (Maximum clique)
- Kirchhoff matrix theorem(Finding the number of spanning trees)
GEOMETRY
- Point Template
- Line Template
- Segment Template
- Circle Template
- 3D geometry Template
- 3D Plane template
- Line 3D Template
- Finding the area of the union of triangles
- PolyGons
- Picks Theorem (the number of points with integer coordinates that lie strictly inside the polygon)
- Polyhedrons
- Spherical geometry
- Convex hull___NlogN
- Check point for belonging to a convex polygon
- Constructing a convex hull by Graham bypass___Nlogn
- Deleting points from Convex Hull ___(nlogn*q)
- Dynamic Convex hull___Adding Points to an Existing Convex Hull__complexity o(n*q)
- Finding the largest inscribed circle in a convex polygon using a ternary search
Data Structure
- Fenwick Tree
- FenwickTree2D
- Sparse Table
- Merge Sort Tree
- Segment Tree(single update)
- Segment Tree with lazy (range update )
- Sqrt Decomposition (add & sum)
- l to r maximum subarray sum with update
- Mo’s Algorithm (normal, add, remove, query sort)
- Mo’s Algorithm (gilbertorder)
- Mo’s on Tree
- Mo’s with DSU
- Mo’s with update
- Mo's Online
- DSU on Tree
- Sum of all possible triplet product in an array
- NTT & FFT
- Fast Walsh Hadamard Transformation(All pair Xor___AND___OR Sum)
- Trie (subarray xor less than k)
- Trie (Xor Max-Min)
- wavelet tree
- HLD
- Lis in every Query___ when array element sum<=1000000
- Persistent Trie
- Treap
STRING
- Rolling Hash
- 2D hashing
- KMP
- Aho corasick
- palindromic Tree
- Suffix Array O(n)
- Suffix Automaton
XOR ___ GCD___LCM
- basis vector___everything for xor subset
- All pair GCD
- All pair GCD(II)
- All pair LCM
- GCD & XOR (how many pair with same gcd and xor)
- maximum pair lcm in an array
Others
- BigInt with fft(add,mult,div)___nlogn__10^5 length Number
- JAVA BigInteger
- MatExpo
- Number Theory Notes
- Random Genarator
Disclaimer
- Don't use directly in code
- Learn about these algorithms.
- you can find some useful website, tutorial, and motivations Here
- If you want to add more. Fork it. Add them. and give me a pull request.
- Try to customize your own code.
Thank you