Concepts20
DP on Broken Profile - Plug DP
Plug DP (DP on broken profile with plugs) sweeps a grid cell by cell while remembering how partial path segments cross the frontier as labeled “plugs.”
Matrix Exponentiation - Advanced
Matrix exponentiation turns repeated linear transitions into fast O(n^{3} log k) computation using exponentiation by squaring.
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.