🐬 Snippets

Every reusable C++ struct and function defined in the notes (831 entries) with the note that defines and tests it. Later notes reuse these names (DSU, Fenwick, Mint, LCA, …) without redefining them.

Name	Kind	Defined in
`abs_`	function	Points, Vectors and Orientation
`adaptive`	function	Root Finding and Integration
`addBounded`	function	Knapsack and Subset Sum
`addGroup`	function	Knapsack and Subset Sum
`addMod`	function	Fast I/O and Constant Factor
`addUnb`	function	Knapsack and Subset Sum
`Affine`	struct	Polygon Clipping and Union
`AhoCorasick`	struct	Trie and Aho-Corasick
`aliens`	function	Aliens Trick
`allCollectedBy`	function	Probability and Expectation
`allPairsMinCutSum`	function	Gomory-Hu Tree
`alphabeta`	function	Game DP, Minimax and Game Search
`alphaBeta`	function	Game DP, Minimax and Game Search
`angle`	function	Points, Vectors and Orientation
`Angle`	struct	Circle Union and Angular Sweep
`angleDiff`	function	Circle Union and Angular Sweep
`angleFromSides`	function	Triangles
`angleLess`	function	Points, Vectors and Orientation
`answer`	function	Interactive Problems
`antsTimes`	function	Sorting and Ordering Observations
`anyIntersection`	function	Sweep Line and Segment Intersections
`apFree`	function	Sequence and Number Constructions
`apIntersection`	function	Number Theory Miscellany
`apply`	function	Treaps and Balanced BSTs
`Arc`	struct	Delaunay and Voronoi
`area`	function	Polygons
`assignmentDP`	function	Assignment Problem
`AStar`	struct	A, IDA and Branch and Bound
`badCharTable`	function	Other Pattern Matching
`ballotPaths`	function	Catalan Numbers and Lattice Paths
`Barrett`	struct	Barrett and Montgomery Reduction
`batchInverse`	function	Modular Arithmetic
`Beats`	struct	Segment Tree Beats and Historic Values
`bellmanFord`	function	Shortest Paths
`bellNumbers`	function	Counting Fundamentals
`bellSeries`	function	Counting with Power Series
`bentleyOttmann`	function	Sweep Line and Segment Intersections
`berlekampMassey`	function	Linear Recurrences
`bernoulli`	function	Counting with Power Series
`bestApproximation`	function	Continued Fractions and Pell Equations
`bestUCT`	function	Game DP, Minimax and Game Search
`bfs01`	function	Shortest Paths
`bidirectional`	function	Meet in the Middle
`Big`	struct	Big Integers and Fractions
`binaryGcd`	function	GCD and Extended Euclid
`BinaryTrie`	struct	Binary Trie
`BinomialAnyMod`	struct	Factorials and Binomials mod p
`binomialPrefix`	function	Binomial Identities
`binomialPrefixQueries`	function	Binomial Identities
`binomialResidueSums`	function	Binomial Identities
`binomialSumsAll`	function	Composition and Taylor Shift
`binomTopLarge`	function	Counting Fundamentals
`bipartiteEdgeColoring`	function	Graph Coloring
`birthdayNoCollision`	function	Probability and Expectation
`bitap`	function	Other Pattern Matching
`BitLCS`	struct	LIS, LCS and Edit Distance
`bitLowerBound`	function	Binary Search
`BitsetMatcher`	struct	Other Pattern Matching
`BitVec`	struct	Range Order Statistics and Wavelets
`Blossom`	struct	General Matching
`BNode`	struct	Tree Basics, Diameter and Center
`boruvka`	function	Minimum Spanning Trees
`boundedKnapsackCounts`	function	Counting with Power Series
`boundedRsk`	function	Young Tableaux and RSK
`boundingFractions`	function	Continued Fractions and Pell Equations
`boyerMooreSearch`	function	Other Pattern Matching
`bracketForest`	function	String Basics and Parsing
`BracketInfo`	struct	String Basics and Parsing
`brent`	function	Cycles and Functional Graphs
`build`	function	Sqrt Decomposition
`buildLPS`	function	Prefix Function and Z-Function
`buildProduct`	function	Power Series Operations
`Cactus`	struct	Special Graph Classes
`canonical`	function	Lines and Segments
`carmichaelLambda`	function	Primitive Roots and Discrete Log
`ceilDiv`	function	Modular Arithmetic
`ceildiv`	function	C++ for Competitive Programming
`centroid`	function	Triangles
`CentroidTree`	struct	Centroid Decomposition
`cfSqrt`	function	Continued Fractions and Pell Equations
`characteristicPolynomial`	function	Characteristic Polynomial
`chinesePostman`	function	Euler Tours
`Chordal`	struct	Special Graph Classes
`chromaticNumber`	function	Graph Coloring
`ChromaticPolynomial`	struct	Graph Coloring
`cipolla`	function	Quadratic Residues and Modular Roots
`Circle`	struct	Minimum Enclosing Circle
`circleCircle`	function	Circles and Inversion
`circleFrom`	function	Minimum Enclosing Circle
`circleLine`	function	Circles and Inversion
`circleUnionArea`	function	Circle Union and Angular Sweep
`circulantDeterminant`	function	Sparse and Structured Matrices
`circumcenter`	function	Triangles
`circumradius`	function	Triangles
`ckmax`	function	C++ for Competitive Programming
`ckmin`	function	C++ for Competitive Programming
`clip`	function	Polygons
`clipPolygon`	function	Polygon Clipping and Union
`clmul`	function	Convolution Variants
`closure`	function	DAGs and Topological Sort
`ColorfulMatroid`	struct	Matroid Intersection
`comb`	function	LIS, LCS and Edit Distance
`Comb`	struct	Modular Arithmetic
`complementBFS`	function	BFS, DFS and Grids
`compose`	function	Counting Fundamentals
`composeFast`	function	Composition and Taylor Shift
`compositionalInverse`	function	Composition and Taylor Shift
`compositionalInverseFast`	function	Composition and Taylor Shift
`connected`	function	Top Trees
`continuedFraction`	function	Continued Fractions and Pell Equations
`conv`	function	Knapsack and Subset Sum
`convergents`	function	Continued Fractions and Pell Equations
`convexHull`	function	Convex Hull
`convexHull3D`	function	3D Geometry and 3D Hull
`convexIntersectionArea`	function	Polygon Clipping and Union
`convexLayers`	function	Convex Hull
`convexMatching`	function	Bipartite Matching
`convexPolygonDistance`	function	Rotating Calipers
`convexTangents`	function	Rotating Calipers
`convolution2D`	function	Convolution Variants
`convolutionAnyMod`	function	Factorials and Binomials mod p
`convolutionCRT`	function	Factorials and Binomials mod p
`convolutionLL`	function	Factorials and Binomials mod p
`coprimeBasis`	function	Number Theory Miscellany
`coprimePairs`	function	Arithmetic Functions and Möbius
`cornacchia`	function	Quadratic Residues and Modular Roots
`CostScaling`	struct	Min-Cost Flow
`countArborescences`	function	Matrix-Tree Theorem
`countAtDepth`	function	Euler Tour, Subtree and Path Queries
`countBoundedBrute`	function	Counting Fundamentals
`countBoundedIndividual`	function	Counting Fundamentals
`countBoundedUniform`	function	Counting Fundamentals
`countByValue`	function	Subarray Aggregates and Mex
`countDiophantine`	function	Factorials and Binomials mod p
`countDistinctSubsequences`	function	Suffix Automaton
`countFourCycles`	function	Special Graph Classes
`countHamPaths`	function	Hamiltonian Paths and TSP
`countIntervals`	function	Permutation Tree
`countInv`	function	Sorting, Selection and Inversions
`countKthPowers`	function	Number Theory Miscellany
`countLess`	function	Fast I/O and Constant Factor
`countMazePaths`	function	Backtracking and Pruning
`countPathsOfLength`	function	Centroid Decomposition
`countProductAtMost`	function	Counting DP Techniques
`countResiduesInRange`	function	Number Theory Miscellany
`countSolutions`	function	Linear Congruences and CRT
`countSpanningTrees`	function	Matrix-Tree Theorem
`countSquareRootsOfOne`	function	Number Theory Miscellany
`countUnlabelledTrees`	function	Tree Isomorphism and Prüfer Codes
`countUpTo`	function	Digit DP
`countXor`	function	Counting DP Techniques
`couponAll`	function	Probability and Expectation
`Cover`	struct	Offline and 2D Range Queries
`cover`	function	Exact Cover and Dancing Links
`CoverTree`	struct	Sweep Line and Segment Intersections
`cross`	function	Points, Vectors and Orientation
`crosses`	function	Lines and Segments
`crtMerge`	function	Linear Congruences and CRT
`crtMod`	function	Factorials and Binomials mod p
`cutFromRoot`	function	Virtual Tree
`CutInfo`	struct	Minimum Cut
`cycleDecomposition`	function	Counting Fundamentals
`cyclicArgmax`	function	Rotating Calipers
`cyclotomic`	function	Polynomial Factorization
`dayOfWeek`	function	C++ for Competitive Programming
`daysBefore`	function	C++ for Competitive Programming
`daysIn`	function	C++ for Competitive Programming
`deBruijn`	function	Euler Tours
`decodePermutation`	function	Burnside and Pólya
`decompose`	function	Flow Modeling
`degree`	function	Backtracking and Pruning
`delannoyTable`	function	Stirling, Bell and Partition Numbers
`densestSubgraph`	function	Flow Modeling
`derangements`	function	Stirling, Bell and Partition Numbers
`detMod`	function	Matrix-Tree Theorem
`diameterDP`	function	Tree Basics, Diameter and Center
`diffConstraints`	function	Shortest Path Techniques
`digitAddConvolution`	function	Convolution Variants
`digitMaxConvolution`	function	Convolution Variants
`digitMinConvolution`	function	Convolution Variants
`DigitRing`	struct	Convolution Variants
`dijkstra`	function	Shortest Paths
`Dinic`	struct	Maximum Flow
`diophantine`	function	Linear Congruences and CRT
`directedMST`	function	Directed MST
`DirectedMST`	struct	Directed MST
`discreteLog`	function	Primitive Roots and Discrete Log
`discreteRoots`	function	Primitive Roots and Discrete Log
`DisjointSparseTable`	struct	Sparse Table
`dist`	function	Points, Vectors and Orientation
`DistanceSum`	struct	Centroid Decomposition
`distinct`	function	Offline and 2D Range Queries
`distinctDiffPerm`	function	Constructive Algorithms
`distinctInRanges`	function	Range Order Statistics and Wavelets
`DistinctOnline`	struct	Range Order Statistics and Wavelets
`distinctPartitions`	function	Stirling, Bell and Partition Numbers
`DistinctSubstringsInRange`	struct	Suffix Array and LCP
`distPointLine`	function	Rotating Calipers
`distPointSegment`	function	Rotating Calipers
`distSegments`	function	Rotating Calipers
`distToLine`	function	Points, Vectors and Orientation
`distToSegment`	function	Points, Vectors and Orientation
`divisorCountAndSum`	function	Primes and Sieves
`divisorMobius`	function	Counting DP Techniques
`divisors`	function	Primitive Roots and Discrete Log
`divisorsFrom`	function	Primality Testing and Factorization
`divisorsFromFactors`	function	Primitive Roots and Discrete Log
`divisorsOf`	function	GCD and Extended Euclid
`divisorsTrial`	function	Primitive Roots and Discrete Log
`divisorZeta`	function	Counting DP Techniques
`divmod`	function	Power Series Operations
`dominantIndices`	function	Heavy-Light and Long-Path Decomposition
`dominatingColourSums`	function	Small to Large (DSU on Tree)
`Dominator`	struct	Dominator Tree
`dominoTilings`	function	Broken Profile DP
`dpll`	function	Satisfiability
`DSU`	struct	Disjoint Set Union
`DsuOnTree`	struct	Small to Large (DSU on Tree)
`DuSieve`	struct	Arithmetic Functions and Möbius
`duval`	function	Lyndon Words and Minimal Rotation
`Dyadic`	struct	Hackenbush and Partizan Games
`DynamicAhoCorasick`	struct	Trie and Aho-Corasick
`DynamicBitset`	struct	Other Pattern Matching
`DynamicDiameter`	struct	Tree Basics, Diameter and Center
`DynamicHull`	struct	Dynamic Convex Hull
`dynamicMST`	function	Minimum Spanning Trees
`DynamicTreeMIS`	struct	Dynamic DP
`DynSeg`	struct	Dynamic and Persistent Segment Trees
`DynSubmask`	struct	Counting DP Techniques
`earClipping`	function	Polygon Clipping and Union
`ECPoint`	struct	Number Theory Miscellany
`edf_split`	function	Polynomial Factorization
`Eertree`	struct	Eertree and Palindromic Factorization
`eggDrop`	function	Classic DP Problems
`elementarySymmetricUpTo`	function	Matrix Exponentiation DP
`elementwiseMin`	function	Fast I/O and Constant Factor
`elemSym`	function	Counting DP Techniques
`EllipticCurve`	struct	Number Theory Miscellany
`encodePermutation`	function	Burnside and Pólya
`eppstein`	function	K Shortest and Disjoint Paths
`equalizeByXor`	function	Invariant-Based Constructions
`ErasableHeap`	struct	Heaps
`eratosthenes`	function	Primes and Sieves
`eulerianTable`	function	Stirling, Bell and Partition Numbers
`eulerPhi`	function	Primitive Roots and Discrete Log
`EulerTour`	struct	Euler Tour, Subtree and Path Queries
`EulerTourTree`	struct	Euler Tour Tree
`eulerWalk`	function	Euler Tours
`Ev`	struct	Sweep Line and Segment Intersections
`evalPoly`	function	Root Finding and Integration
`evalRec`	function	Multipoint Evaluation and Interpolation
`Event`	struct	Sweep Line and Segment Intersections
`exactGcdPairs`	function	Primes and Sieves
`excenter`	function	Triangles
`expectedMaxDice`	function	Probability and Expectation
`expectedSteps`	function	Probability and Expectation
`ExprParser`	struct	String Basics and Parsing
`extendPRecursive`	function	Linear Recurrences
`extgcd`	function	GCD and Extended Euclid
`extGcd`	function	Factorials and Binomials mod p
`extremeVertex`	function	Rotating Calipers
`Eytzinger`	struct	Fast I/O and Constant Factor
`factorize`	function	Primality Testing and Factorization
`factorizeTrial`	function	Primitive Roots and Discrete Log
`factorRec`	function	Primality Testing and Factorization
`factorXnMinus1`	function	Polynomial Factorization
`faddeevLeVerrier`	function	Characteristic Polynomial
`farthest`	function	Tree Basics, Diameter and Center
`FastFactorial`	struct	Factorials and Binomials mod p
`FastMod32`	struct	Barrett and Montgomery Reduction
`fastRsk`	function	Young Tableaux and RSK
`FastSet`	struct	Fast Set and Integer Structures
`fastSieve`	function	Primes and Sieves
`Fenwick`	struct	Fenwick Tree
`Fenwick2D`	struct	Fenwick Tree
`FGH`	struct	Harmonic Lemma and Floor Sums
`findAll`	function	Prefix Function and Z-Function
`findCelebrity`	function	Celebrity Problem
`findDirectedCycle`	function	Cycles and Functional Graphs
`findPRecursive`	function	Linear Recurrences
`firstPlayerWins`	function	Combinatorial Games and Nim
`floorDiv`	function	Modular Arithmetic
`floordiv`	function	C++ for Competitive Programming
`floorFGH`	function	Harmonic Lemma and Floor Sums
`floorSum`	function	Harmonic Lemma and Floor Sums
`FloorValues`	struct	Harmonic Lemma and Floor Sums
`floyd`	function	Shortest Paths
`foot`	function	Lines and Segments
`forEachPythagorean`	function	Number Theory Miscellany
`fortune`	function	Delaunay and Voronoi
`Frac`	struct	Continued Fractions and Pell Equations
`fracBinarySearch`	function	Continued Fractions and Pell Equations
`from2`	function	Minimum Enclosing Circle
`from3`	function	Minimum Enclosing Circle
`fromBalancedTernary`	function	Modular Arithmetic
`fromBinomialBasis`	function	Counting with Power Series
`fromFactoradic`	function	Burnside and Pólya
`fromNegativeBase`	function	Modular Arithmetic
`fromNewtonBasis`	function	Multipoint Evaluation and Interpolation
`fubini`	function	Stirling, Bell and Partition Numbers
`FunctionalGraph`	struct	Cycles and Functional Graphs
`fwht`	function	Bitwise Convolutions
`gallaiEdmonds`	function	General Matching
`gamblersRuin`	function	Probability and Expectation
`garner`	function	Linear Congruences and CRT
`garsiaWachs`	function	Knuth-Yao Optimization
`gauss`	function	General Matching
`gaussianElimination`	function	Gaussian Elimination, Rank and Inverse
`gaussJordan`	function	Gaussian Elimination, Rank and Inverse
`gcdLcmPairs`	function	Arithmetic Functions and Möbius
`GeneralMatching`	struct	Games on Graphs and Matchings
`generate`	function	Lyndon Words and Minimal Rotation
`geographyFirstWins`	function	Games on Graphs and Matchings
`getPath`	function	Top Trees
`getSubtree`	function	Top Trees
`GF64`	struct	Convolution Variants
`ggcd`	function	Number Theory Miscellany
`GI`	struct	Number Theory Miscellany
`girthUnweighted`	function	Shortest Path Techniques
`goldenMin`	function	Ternary and Golden-Section Search
`gomoryHu`	function	Gomory-Hu Tree
`gquot`	function	Number Theory Miscellany
`GraeffeLevels`	struct	Composition and Taylor Shift
`grahamScan`	function	Convex Hull
`GraphCounting`	struct	Counting Graphs and Trees
`GraphicMatroid`	struct	Matroid Intersection
`gray`	function	Gray Code
`grayInverse`	function	Gray Code
`greedySetCover`	function	Approximation Algorithms
`gridPaths`	function	Catalan Numbers and Lattice Paths
`grundy`	function	Sprague-Grundy
`guessPermutation`	function	Interactive and Output-Only Constructions
`hackenbush`	function	Combinatorial Games and Nim
`hafnian`	function	Determinants and Permanents
`half`	function	Points, Vectors and Orientation
`halfPlaneIntersection`	function	Half-Plane Intersection
`hamiltonianCycles`	function	Broken Profile DP
`hamiltonianPath`	function	Hamiltonian Paths and TSP
`hanoi`	function	Tower of Hanoi
`Hash`	struct	Randomized Algorithms
`Hashing`	struct	String Hashing
`HashMap`	struct	Containers, Hashing and Choosing a Structure
`hatGuesses`	function	Prisoners and Hats
`havelHakimi`	function	Graph Constructions
`heavyCoin`	function	Counterfeit Coin and 12 Coins
`heron`	function	Triangles
`hilbert`	function	Mo’s Algorithm
`hirschberg`	function	LIS, LCS and Edit Distance
`HLD`	struct	Heavy-Light and Long-Path Decomposition
`HopcroftKarp`	struct	Bipartite Matching
`HP`	struct	Half-Plane Intersection
`hullArea`	function	3D Geometry and 3D Hull
`hullVolume6`	function	3D Geometry and 3D Hull
`hungarian`	function	Assignment Problem
`incenter`	function	Triangles
`inConvex`	function	Polygons
`inConvexPolygon`	function	Rotating Calipers
`IncReach`	struct	DAGs and Topological Sort
`incrementalSCC`	function	SCC and 2-SAT
`Info`	struct	LIS, LCS and Edit Distance
`inPolygon`	function	Polygons
`inradius`	function	Triangles
`insert`	function	XOR Basis
`inside`	function	Minimum Enclosing Circle
`integrate`	function	Root Finding and Integration
`inter`	function	Half-Plane Intersection
`intersectionPoint`	function	Lines and Segments
`IntervalMap`	struct	Chtholly Tree (Interval Map)
`inTriangle`	function	Polygons
`inverse`	function	Power Series Operations
`inverseBwt`	function	Burrows-Wheeler Transform
`inverseMod2`	function	Gaussian Elimination, Rank and Inverse
`inversePermutation`	function	Counting Fundamentals
`inversesUpTo`	function	Modular Arithmetic
`invertCircle`	function	Circles and Inversion
`invertLine`	function	Circles and Inversion
`invertPoint`	function	Circles and Inversion
`invMod`	function	GCD and Extended Euclid
`invTable`	function	Counting with Power Series
`isBalanced`	function	String Basics and Parsing
`isConvex`	function	Points, Vectors and Orientation
`isGraphical`	function	Special Graph Classes
`island`	function	DAG and Expected-Value DP
`isLeap`	function	C++ for Competitive Programming
`IsomorphicSubstrings`	struct	String Hashing
`isPal`	function	Palindromes and Manacher
`isPrime`	function	Primality Testing and Factorization
`isPrimeTrial`	function	Primitive Roots and Discrete Log
`isqrtNewton`	function	Root Finding and Integration
`isRepetition`	function	String Basics and Parsing
`isTangent`	function	Convex Polygon Queries and Tangents
`isTournamentScore`	function	Special Graph Classes
`isWinningCombinedGame`	function	Sprague-Grundy
`jacobi`	function	Primitive Roots and Discrete Log
`josephus`	function	Classic Puzzles
`josephusFast`	function	Classic Puzzles
`kahn`	function	DAGs and Topological Sort
`kangaroo`	function	Counting DP Techniques
`karatsuba`	function	Fast Fourier Transform
`kargerStein`	function	Global Minimum Cut
`kasai`	function	Suffix Array and LCP
`KD`	struct	KD-Tree and Spatial Structures
`kmpSearch`	function	Prefix Function and Z-Function
`knightDist`	function	BFS, DFS and Grids
`knightsTour`	function	Backtracking and Pruning
`knightsTourOnce`	function	Knight’s Tour and N Queens
`knuth`	function	Knuth-Yao Optimization
`konigCover`	function	Bipartite Matching
`kruskal`	function	Minimum Spanning Trees
`KST`	struct	Li Chao and Kinetic Segment Trees
`kthCoefficient`	function	Multipoint Evaluation and Interpolation
`kthPermutation`	function	Counting Fundamentals
`Kuhn`	struct	Bipartite Matching
`kummerCarries`	function	Factorials and Binomials mod p
`kWalks`	function	K Shortest and Disjoint Paths
`LadderAncestor`	struct	Lowest Common Ancestor
`lagrangeAt`	function	Counting with Power Series
`lahTable`	function	Stirling, Bell and Partition Numbers
`largestRectangle`	function	Monotonic Stack
`lastOccurrence`	function	Range Order Statistics and Wavelets
`LazySegTree`	struct	Lazy Propagation
`LCA`	struct	Lowest Common Ancestor
`lcmSafe`	function	GCD and Extended Euclid
`lcpArray`	function	Burrows-Wheeler Transform
`lcsBitParallel`	function	Bitset and Word-Level Parallelism
`lcsRow`	function	LIS, LCS and Edit Distance
`leastRotation`	function	Lyndon Words and Minimal Rotation
`legendreExp`	function	Factorials and Binomials mod p
`LiChao`	struct	Li Chao and Kinetic Segment Trees
`lightsOut`	function	Lights Out
`Line`	struct	Li Chao and Kinetic Segment Trees
`linearCongruence`	function	Linear Congruences and CRT
`LinearMatroid`	struct	Matroid Intersection
`linearRecurrenceMod`	function	Linear Recurrences
`LinearSieve`	struct	Primes and Sieves
`linearTransformation`	function	Circle Union and Angular Sweep
`LineContainer`	struct	Convex Hull Trick
`lineDist`	function	3D Geometry and 3D Hull
`lineHullIntersection`	function	Convex Polygon Queries and Tangents
`lineInter`	function	Lines and Segments
`lineIntersect`	function	Lines and Segments
`lineIntersection`	function	Rotating Calipers
`linePlaneIntersection`	function	3D Geometry and 3D Hull
`link`	function	Top Trees
`LinkCut`	struct	Link-Cut Tree
`lisLdsPerm`	function	Permutation Constructions
`LNode`	struct	Heaps
`logSeries`	function	Power Series Operations
`longestPalindrome`	function	Palindromes and Manacher
`LongPath`	struct	Heavy-Light and Long-Path Decomposition
`loopyGrundy`	function	Loopy Games and Retrograde Analysis
`loopyOutcome`	function	Loopy Games and Retrograde Analysis
`loopySumOutcome`	function	Loopy Games and Retrograde Analysis
`LowerBoundFlow`	struct	Flow Modeling
`Lowlink`	struct	Bridges and Biconnectivity
`LPSolver`	struct	Linear Programming
`LucasP`	struct	Factorials and Binomials mod p
`Lucy`	struct	Sublinear Sieves and Prime Counting
`magicSquare`	function	Grid and Matrix Constructions
`make`	function	Treaps and Balanced BSTs
`Manacher`	struct	Palindromes and Manacher
`matchBrackets`	function	String Basics and Parsing
`matching`	function	General Matching
`MatchingClassifier`	struct	Bipartite Matching
`matchingSize`	function	General Matching
`Matrix`	struct	Matrices and Matrix Power
`matrix_power`	function	Matrices and Matrix Power
`maxAntichain`	function	Bipartite Matching
`maxClosure`	function	Flow Modeling
`maxCollinear`	function	Point Location and Point Counting
`maxPointsInCircle`	function	Circle Union and Angular Sweep
`maxProfit`	function	Classic DP Problems
`maxWeightMatchingDP`	function	Weighted General Matching
`MCMF`	struct	Min-Cost Flow
`mcts`	function	Game DP, Minimax and Game Search
`MDST`	struct	Minimum Spanning Trees
`medianLength`	function	Triangles
`meld`	function	Heaps
`merge`	function	Classic Array Problems
`MergeSeg`	struct	Segment Tree Merging and Splitting
`mexToZero`	function	When the Answer Is Small
`minBoundingRectangle`	function	Rotating Calipers
`MinCostBFlow`	struct	Min-Cost Flow
`minimizeDFA`	function	Automata and Formal Languages
`minCostNonDecreasing`	function	Slope Trick
`minDiameterTree`	function	Minimum Spanning Trees
`minEnclosingCircle`	function	Minimum Enclosing Circle
`minkowski`	function	Minkowski Sum
`minkowskiSum`	function	Rotating Calipers
`minMeanCycle`	function	Shortest Path Techniques
`minOpsFromOne`	function	Observation Toolkit
`minPalCuts`	function	Classic DP Problems
`minPalindromicFactorization`	function	Eertree and Palindromic Factorization
`minPathCover`	function	Flow Modeling
`minPlusConvexArbitrary`	function	Convolution Variants
`minPlusConvexConvex`	function	Convolution Variants
`MinPlusMatrix`	struct	Matrices and Matrix Power
`minSteps`	function	Water Jug
`MInt`	struct	Factorials and Binomials mod p
`mintSqrt`	function	Counting with Power Series
`misereWins`	function	Combinatorial Games and Nim
`MisOps`	struct	Top Trees
`MonoCHT`	struct	Convex Hull Trick
`monotoneChain`	function	Convex Hull
`Montgomery64`	struct	Barrett and Montgomery Reduction
`mooreLoses`	function	Combinatorial Games and Nim
`moRollback`	function	Mo’s Algorithm
`morrisInorder`	function	Tree Basics, Diameter and Center
`motzkin`	function	Stirling, Bell and Partition Numbers
`mul2D`	function	Composition and Taylor Shift
`mulm`	function	Primality Testing and Factorization
`mulMod`	function	Primitive Roots and Discrete Log
`mulmod64`	function	Barrett and Montgomery Reduction
`mulOverflows`	function	Modular Arithmetic
`mulSlow`	function	Modular Arithmetic
`multipleMobius`	function	Counting DP Techniques
`multipleZeta`	function	Counting DP Techniques
`multiplicativeOrder`	function	Primitive Roots and Discrete Log
`multiply`	function	Matrices and Matrix Power
`multiplyBig`	function	Fast Fourier Transform
`multiplyNTT`	function	Number-Theoretic Transform
`muUpTo`	function	Arithmetic Functions and Möbius
`narayanaTable`	function	Stirling, Bell and Partition Numbers
`NearestMarked`	struct	Centroid Decomposition
`negamax`	function	Game DP, Minimax and Game Search
`negascout`	function	Game DP, Minimax and Game Search
`negativeCycle`	function	Shortest Paths
`NetworkSimplex`	struct	Min-Cost Flow
`newton`	function	Root Finding and Integration
`noAdjacentConsecutive`	function	Permutation Constructions
`Node`	struct	Classic Array Problems
`numberGame`	function	Hackenbush and Partizan Games
`offlineArgmin`	function	Range Minimum Query
`OfflineConnectivity`	struct	Dynamic Connectivity
`offlineLCA`	function	Lowest Common Ancestor
`oneD1D`	function	Monotone Queue, 1D1D and SMAWK
`OnlineBridges`	struct	Bridges and Biconnectivity
`OnlineMSF`	struct	Link-Cut Tree
`onRange`	function	Treaps and Balanced BSTs
`onSegment`	function	Points, Vectors and Orientation
`optimalCutoff`	function	Secretary Problem
`OrderStatFenwick`	struct	Counting Fundamentals
`ordinal`	function	C++ for Competitive Programming
`orient`	function	Points, Vectors and Orientation
`orient3`	function	3D Geometry and 3D Hull
`orthocenter`	function	Triangles
`outside`	function	Half-Plane Intersection
`P3`	struct	3D Geometry and 3D Hull
`pairsDisjoint`	function	Digit DP
`PalindromesInRange`	struct	Palindromes and Manacher
`partition3`	function	Sorting, Selection and Inversions
`partitionNumbers`	function	Counting Fundamentals
`partitionSeries`	function	Counting with Power Series
`partitionsIntoParts`	function	Stirling, Bell and Partition Numbers
`pascal`	function	Counting Fundamentals
`PathAddSubtreeSum`	struct	Euler Tour, Subtree and Path Queries
`pathsAvoiding`	function	Catalan Numbers and Lattice Paths
`pathsBetweenLines`	function	Catalan Numbers and Lattice Paths
`patternContainment`	function	Other Pattern Matching
`patternWaitingTime`	function	Probability and Expectation
`pellFundamental`	function	Continued Fractions and Pell Equations
`permanent`	function	Determinants and Permanents
`permutantDeterminant`	function	Sparse and Structured Matrices
`PermutationGroup`	struct	Burnside and Pólya
`permutationRank`	function	Counting Fundamentals
`permutationRoot`	function	Burnside and Pólya
`permutationSort`	function	When the Answer Is Small
`PermutationTree`	struct	Permutation Tree
`permutationXorValues`	function	Determinants and Permanents
`permWithInversions`	function	Permutation Constructions
`perp`	function	Points, Vectors and Orientation
`PersistentCentroid`	struct	Centroid Decomposition
`phiOf`	function	Arithmetic Functions and Möbius
`phiUpTo`	function	Arithmetic Functions and Möbius
`planarFaces`	function	Planar Graphs and Faces
`Plane`	struct	3D Geometry and 3D Hull
`pohligHellman`	function	Primitive Roots and Discrete Log
`Point`	struct	Triangles
`Point3`	struct	3D Geometry and 3D Hull
`polarLess`	function	Triangles
`pollard`	function	Primality Testing and Factorization
`pollardPm1`	function	Primitive Roots and Discrete Log
`pollardRho`	function	Primitive Roots and Discrete Log
`Poly`	struct	Multipoint Evaluation and Interpolation
`PolyEuclid`	struct	Polynomial GCD and Resultant
`polyGcd`	function	Sparse and Structured Matrices
`polygonUnionArea`	function	Polygon Clipping and Union
`polyInverseMod`	function	Polynomial GCD and Resultant
`polyMod`	function	Sparse and Structured Matrices
`polyMul`	function	Linear Recurrences
`polyMulMod`	function	Linear Recurrences
`polyRoots`	function	Root Finding and Integration
`polyStrip`	function	Sparse and Structured Matrices
`posetMobius`	function	Inclusion-Exclusion and Derangements
`pourSteps`	function	Water Jug
`powCap`	function	Arithmetic Functions and Möbius
`power`	function	Matrix Exponentiation DP
`powerProjection`	function	Composition and Taylor Shift
`powerSums`	function	Counting with Power Series
`PowerTower`	struct	Number Theory Miscellany
`powm`	function	Primality Testing and Factorization
`powMod`	function	Primitive Roots and Discrete Log
`precompute`	function	Counting Fundamentals
`prefixFunction`	function	Prefix Function and Z-Function
`primDense`	function	Minimum Spanning Trees
`primeFactorsOf`	function	Primitive Roots and Discrete Log
`primeTwoSquares`	function	Quadratic Residues and Modular Roots
`primitiveRootPrime`	function	Primitive Roots and Discrete Log
`print`	function	Big Integers and Fractions
`projection`	function	Rotating Calipers
`properIntersect`	function	Points, Vectors and Orientation
`pruferDecode`	function	Tree Isomorphism and Prüfer Codes
`pruferEncode`	function	Tree Isomorphism and Prüfer Codes
`PSeg`	struct	Dynamic and Persistent Segment Trees
`PST`	struct	Persistent Data Structures
`pull`	function	Treaps and Balanced BSTs
`push`	function	Treaps and Balanced BSTs
`PushRelabel`	struct	Push-Relabel
`QBinomial`	struct	Stirling, Bell and Partition Numbers
`qBinomialTable`	function	Stirling, Bell and Partition Numbers
`queens`	function	Backtracking and Pruning
`query`	function	Sqrt Decomposition
`QueueUndo`	struct	Offline Techniques
`rabinKarp`	function	Other Pattern Matching
`RadixHeap`	struct	Heaps
`radixSort`	function	Theoretical Algorithms Catalog
`RangeFenwick`	struct	Fenwick Tree
`RangeGraph`	struct	Shortest Path Techniques
`RangeLIS`	struct	Range LIS
`rank`	function	Gaussian Elimination, Rank and Inverse
`rankF2`	function	Gaussian Elimination, Rank and Inverse
`rankMod2`	function	Gaussian Elimination, Rank and Inverse
`rankOneDeterminant`	function	Sparse and Structured Matrices
`reachableByKSwaps`	function	Operations and Reachable States
`readInt`	function	Fast I/O and Constant Factor
`rectangleFits`	function	Rotating Calipers
`rectangleUnionArea`	function	Sweep Line and Segment Intersections
`rectangleUnionPerimeter`	function	Sweep Line and Segment Intersections
`rectSum`	function	Offline and 2D Range Queries
`ReedsSloane`	struct	Linear Recurrences
`reedsSloane`	function	Linear Recurrences
`reflectAcross`	function	Points, Vectors and Orientation
`reflection`	function	Rotating Calipers
`RelaxedConvolution`	struct	Online Convolution
`remove`	function	Knapsack and Subset Sum
`remUnb`	function	Knapsack and Subset Sum
`ReplacementPaths`	struct	Shortest Path Techniques
`reroot`	function	Tree DP and Rerooting
`rerootedSubtree`	function	Euler Tour, Subtree and Path Queries
`reservoir`	function	Randomized Algorithms
`residueDist`	function	Knapsack and Subset Sum
`resultant`	function	Sparse and Structured Matrices
`retrograde`	function	Loopy Games and Retrograde Analysis
`reversalsToAlternate`	function	Ad Hoc on Arrays and Strings
`riverCrossing`	function	River Crossings
`RollbackDSU`	struct	Disjoint Set Union
`RootedTree`	struct	Tree Basics, Diameter and Center
`rootsModP`	function	Polynomial Factorization
`rotate`	function	Treaps and Balanced BSTs
`roundDiv`	function	Number Theory Miscellany
`rskShape`	function	Young Tableaux and RSK
`runs`	function	Runs and Periodicity
`saDoubling`	function	Burrows-Wheeler Transform
`safe`	function	Wolf Goat Cabbage
`SafeHash`	struct	C++ for Competitive Programming
`saIs`	function	Burrows-Wheeler Transform
`SAM`	struct	Suffix Automaton
`samplingShift`	function	Composition and Taylor Shift
`saNaive`	function	Burrows-Wheeler Transform
`scaleTo`	function	Points, Vectors and Orientation
`SCC`	struct	SCC and 2-SAT
`SchieberVishkin`	struct	Lowest Common Ancestor
`schroder`	function	Stirling, Bell and Partition Numbers
`search`	function	A, IDA and Branch and Bound
`seaweedBraid`	function	Range LIS
`secondBestMST`	function	Minimum Spanning Trees
`Seg`	struct	Sweep Line and Segment Intersections
`Segment`	struct	Sweep Line and Segment Intersections
`segmentAngles`	function	Circle Union and Angular Sweep
`segmentBelow`	function	Point Location and Point Counting
`segmentDist`	function	3D Geometry and 3D Hull
`segmentedSieve`	function	Primes and Sieves
`segmentInPolygon`	function	Polygons
`segmentIntersection`	function	Rotating Calipers
`segmentsIntersect`	function	Lines and Segments
`segToSeg`	function	Points, Vectors and Orientation
`SegTree`	struct	Segment Tree
`SeriesFactorials`	struct	Counting with Power Series
`SetHashing`	struct	Randomized Algorithms
`shermanMorrison`	function	Sparse and Structured Matrices
`shiftOr`	function	Other Pattern Matching
`sidonSet`	function	Sequence and Number Constructions
`signature`	function	Counting DP Techniques
`simp`	function	Root Finding and Integration
`simplest`	function	Big Integers and Fractions
`simplestBetween`	function	Number Theory Miscellany
`simpson`	function	Root Finding and Integration
`simulatedAnnealing`	function	Heuristic Optimization
`slidingSolvable`	function	Parity, Coloring and Mod Observations
`SlopeTrick`	struct	Slope Trick
`smallestFromPattern`	function	Greedy Constructions
`smallestPeriod`	function	String Basics and Parsing
`smallestRotation`	function	Lyndon Words and Minimal Rotation
`smallestWithDivisors`	function	Arithmetic Functions and Möbius
`smallestWithZeros`	function	Factorials and Binomials mod p
`smawk`	function	Monotone Queue, 1D1D and SMAWK
`solvable`	function	A, IDA and Branch and Bound
`solve`	function	Divide and Conquer
`solveSudoku`	function	Backtracking and Pruning
`sparseCertificate`	function	Global Minimum Cut
`sparseExp`	function	Counting with Power Series
`sparseInv`	function	Counting with Power Series
`sparseLog`	function	Counting with Power Series
`sparsePow`	function	Counting with Power Series
`sparsePowUnit`	function	Counting with Power Series
`sparseSqrt`	function	Counting with Power Series
`SparseTable`	struct	Sparse Table
`splay`	function	Treaps and Balanced BSTs
`split`	function	Treaps and Balanced BSTs
`sqrtMod`	function	Quadratic Residues and Modular Roots
`sqrtModPrimePower`	function	Quadratic Residues and Modular Roots
`squarefreeCount`	function	Sublinear Sieves and Prime Counting
`stableRoommates`	function	Stable Matching
`StaticTopTree`	struct	Top Trees
`sternBrocotAncestor`	function	Continued Fractions and Pell Equations
`sternBrocotDecode`	function	Continued Fractions and Pell Equations
`sternBrocotDepth`	function	Continued Fractions and Pell Equations
`sternBrocotEncode`	function	Continued Fractions and Pell Equations
`sternBrocotLca`	function	Continued Fractions and Pell Equations
`sternBrocotRange`	function	Continued Fractions and Pell Equations
`sternBrocotWalk`	function	Continued Fractions and Pell Equations
`stickyProduct`	function	Range LIS
`stickyRec`	function	Range LIS
`stirling1Column`	function	Counting with Power Series
`stirling1Row`	function	Counting with Power Series
`stirling1Table`	function	Stirling, Bell and Partition Numbers
`stirling2`	function	Stirling, Bell and Partition Numbers
`stirling2Column`	function	Counting with Power Series
`stirling2Row`	function	Counting with Power Series
`stirling2Table`	function	Stirling, Bell and Partition Numbers
`stirlingColumn`	function	Counting with Power Series
`stirlingSecondKind`	function	Counting Fundamentals
`stNumbering`	function	Bridges and Biconnectivity
`stoerWagner`	function	Global Minimum Cut
`strangePrinter`	function	Interval DP
`StringHash`	struct	String Hashing
`strongOrientation`	function	Bridges and Biconnectivity
`subarrayGcdCounts`	function	GCD and Extended Euclid
`SubsequenceAutomaton`	struct	Suffix Automaton
`subsetConv`	function	Submasks, Supermasks and SOS DP
`subsetSum`	function	Meet in the Middle
`subsetSumCounts`	function	Counting with Power Series
`subsetSums`	function	Bitset and Word-Level Parallelism
`successProbability`	function	100 Prisoners
`suffixArray`	function	Suffix Array and LCP
`suffixArrayLinear`	function	Burrows-Wheeler Transform
`sumExpTimesPoly`	function	Counting with Power Series
`sumExpTimesPolyLimit`	function	Counting with Power Series
`sumFloorDiv`	function	Harmonic Lemma and Floor Sums
`sumMod`	function	Harmonic Lemma and Floor Sums
`sumSigmaMod`	function	Arithmetic Functions and Möbius
`sumSubarrayMins`	function	Contribution and Complementary Counting
`SWAG`	struct	Two Pointers and Sliding Window
`synthetic`	function	Power Series Operations
`table`	function	Observation Toolkit
`tangentPoints`	function	Convex Polygon Queries and Tangents
`taylorShift`	function	Composition and Taylor Shift
`taylorShiftBy`	function	Composition and Taylor Shift
`ternaryMin`	function	Ternary and Golden-Section Search
`thomas`	function	Sparse and Structured Matrices
`threeEdgeCC`	function	Bridges and Biconnectivity
`to_str`	function	C++ for Competitive Programming
`toBalancedTernary`	function	Modular Arithmetic
`toBinomialBasis`	function	Counting with Power Series
`toFactoradic`	function	Burnside and Pólya
`toNegativeBase`	function	Modular Arithmetic
`toNewtonBasis`	function	Multipoint Evaluation and Interpolation
`TopK`	struct	Heaps
`TopTreeNode`	struct	Top Trees
`tour`	function	Backtracking and Pruning
`tournamentPath`	function	Hamiltonian Paths and TSP
`tower`	function	Arithmetic Functions and Möbius
`trailingZerosBase`	function	Factorials and Binomials mod p
`transitiveClosure`	function	Bitset and Word-Level Parallelism
`trap`	function	Monotonic Stack
`TreeCanon`	struct	Tree Isomorphism and Prüfer Codes
`treeCenters`	function	Tree Basics, Diameter and Center
`treeCentroids`	function	Tree Basics, Diameter and Center
`TreeHash`	struct	Tree Isomorphism and Prüfer Codes
`treeKnap`	function	Tree DP and Rerooting
`Treewidth2`	struct	Special Graph Classes
`treeWithDiameter`	function	Graph Constructions
`TrianglePointCounter`	struct	Point Location and Point Counting
`Trie`	struct	Trie and Aho-Corasick
`TrieNode`	struct	Trie and Aho-Corasick
`TrygubNumber`	struct	Modular Arithmetic
`twoColour`	function	Bipartite Graphs
`TwoSat`	struct	SCC and 2-SAT
`twoSquares`	function	Quadratic Residues and Modular Roots
`uncover`	function	Exact Cover and Dancing Links
`unite`	function	Treaps and Balanced BSTs
`Upd`	struct	Mo’s Algorithm
`update`	function	Sqrt Decomposition
`UpperHull`	struct	Dynamic Convex Hull
`vandermondeDeterminant`	function	Sparse and Structured Matrices
`vandermondeInverse`	function	Sparse and Structured Matrices
`VeniceHeap`	struct	Heaps
`vertexConnectivity`	function	Minimum Cut
`vertexCover2`	function	Approximation Algorithms
`virtualTree`	function	Virtual Tree
`viterbi`	function	DAG and Expected-Value DP
`vizing`	function	Graph Coloring
`volume6`	function	3D Geometry and 3D Hull
`WaveletMatrix`	struct	Range Order Statistics and Wavelets
`WaveletTree`	struct	Palindromes and Manacher
`WeightedBlossom`	struct	Weighted General Matching
`WeightedDSU`	struct	Disjoint Set Union
`weightedMatroidIntersection`	function	Matroid Intersection
`welzl`	function	Minimum Enclosing Circle
`wildcardMatch`	function	Other Pattern Matching
`wildcardScores`	function	Other Pattern Matching
`winningMove`	function	Combinatorial Games and Nim
`without`	function	Prefix Sums and Difference Arrays
`wordSearch`	function	Backtracking and Pruning
`writeInt`	function	Fast I/O and Constant Factor
`wythoffLoses`	function	Combinatorial Games and Nim
`XorBasis`	struct	XOR Basis
`XorWalks`	struct	Shortest Path Techniques
`zFunction`	function	Prefix Function and Z-Function
`zMatch`	function	Runs and Periodicity
`zSearch`	function	Prefix Function and Z-Function

whoashish's cp notes

Directory

🐬 Snippets

Graph View