Concepts52
Möbius Function and Inversion
The Möbius function μ(n) is 0 if n has a squared prime factor, otherwise it is (-1)^k where k is the number of distinct prime factors.
Divisor Function Sums
Summing the divisor function d(i) up to n equals counting lattice points under the hyperbola xy ≤ n, which can be done in O(√n) using floor-division blocks.
Sqrt Decomposition on Queries
Sqrt decomposition on queries (time blocking) processes Q operations in blocks of size about \(\sqrt{Q}\) to balance per-query overhead and rebuild cost.
Polynomial Operations
Fast polynomial operations treat coefficients like numbers but use FFT/NTT to multiply in O(n \log n) time instead of O(n^2).
Convolution Applications
Convolution turns local pairwise combinations (like matching characters or adding two dice) into a single fast transform–multiply–inverse pipeline.
NTT (Number Theoretic Transform)
The Number Theoretic Transform (NTT) is an FFT-like algorithm that performs discrete convolutions exactly using modular arithmetic instead of floating-point numbers.
Mo's Algorithm - With Updates
Mo's algorithm with updates treats array modifications as a third dimension called time and answers range queries on the correct version of the array.
DSU on Tree (Sack)
DSU on Tree (also called the Sack technique) answers many subtree queries in O(n \log n) by keeping data from the heavy child and temporarily re-adding light subtrees.
Rectangle Union Area
The union area of many axis-aligned rectangles can be computed efficiently using a sweep line over x and a segment tree tracking covered y-length.
Suffix Array Construction
A suffix array stores the starting indices of all suffixes of a string in lexicographic order, enabling fast substring queries and many string operations.
Slope Trick
Slope Trick is a technique to maintain a convex piecewise-linear function implicitly using two heaps and a running constant.
Subset Sum Convolution
Subset Sum Convolution (often called Subset Convolution) computes C[S] by summing A[T]×B[U] over all disjoint pairs T and U whose union is S.