competitive_programming_codebook

This is a Codebook for programming. I try to store some Advanced Algothims and data structures here

Some algorithms will be added later

You can fork it and add more

Template c++

• Basic Template
• Super Template

Numer Theory

• PRIME TEST(miller_robin)
• NUMBER OF PRIME FACTOR(SQUFOF) Faster (10^18)
• Expression solving
• BURNSIDE LEMMA
• NUMBER OF DIVISORS (1-10^18)
• floor number sum
• Modular Inverse if mod is not prime
• PRIME TEST (BPSW)(100%)
• ax+by=c everything ____extended euclid
• Farey Sequence
• NUMBER OF PRIME FACTOR(10^18)
• Modular inverse(1 to N)__O(N)
• n! % k^x==0 find x
• Baby Step-Giant Step
• Phi Function
• quadric resduie (can any sqrt(x) represents with a number)
• Chinese Remainder Theorem(Garner's)
• Factorial modulo (n!%p)
• DIVISORS ___SUM OF DIVISORS____MULT OF DIVISORS____N<=10^16
• Linear Seive
• Sum of Kth power____Find (1^k+2^k+...+n^k %) mod____O(K)

Graph

• Dominator Tree
• dynamic connectivity problem
• MaxFlowMinCut(SPFA)
• Articulation Point
• BellManFord (negative cycle ditect)
• Blossom Algorithm (maximum matching in genarel graph)
• BronKerbosch (Maximum clique)
• Centroid Decomposition(normal Implementation)
• Centroid Decomposition(Path Problem)
• Dijkstra
• Dinic's-Maxflow
• Directed MST
• DSU
• Finding the shortest path of two node in every query
• HopcroftKarp (BPM Unweighted)
• Floyed Warshall
• Kirchhoff matrix theorem(Finding the number of spanning trees)
• LCA
• LCA finding ____offline query ___O(1) time each query
• MST
• Strongly Connected Component

GEOMETRY

• Convex hull___NlogN
• Deleting points from Convex Hull___(nlogn*q)
• Finding the area of ​​the union of triangles
• Constructing a convex hull by Graham bypass___Nlogn
• 3D geometry Template
• 3D Plane template
• Check point for belonging to a convex polygon
• Circle Template
• 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
• Line Template
• Line 3D Template
• Picks Theorem (the number of points with integer coordinates that lie strictly inside the polygon)
• Point Template
• PolyGons
• Polyhedrons
• Segment Template
• Spherical geometry

Data Structure

• Dsu on Tree
• Fenwick Tree
• Merge Sort Tree
• Mo’s Algorithm (gilbertorder)
• Segment Tree with lazy (range update )
• Sqrt Decomposition (add & sum)
• Sum of all possible triplet product in an array
• Fast Walsh Hadamard Transformation(All pair Xor___AND___OR Sum)
• FenwickTree2D
• HLD
• l to r maximum subarray sum with update
• Lis in every Query ___ when array element sum<=1000000
• Mo's Online
• Mo’s Algorithm (normal, add, remove, query sort)
• Mo’s on Tree
• Mo’s with DSU
• Mo’s with update
• NTT & FFT
• Persistent Trie
• Segment Tree(single update)
• Sparse Table
• Treap
• Trie (subarray xor less then k)
• Trie (Xor Max Min)
• wavelet tree

STRING

• 2D hashing
• Aho corasick
• KMP
• palindromic Tree
• Rolling Hash
• Suffix Array O(n)
• Suffix Automaton

XOR ___ GCD___LCM

• basis vector
• All pair GCD
• All pair GCD(II)
• All pair LCM
• GCD & 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