Concepts36
Category
Minkowski Sum
The Minkowski sum A β B adds every point of set A to every point of set B, and for convex polygons it can be computed in O(n + m) by merging edge directions.
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.
Lyndon Factorization
A Lyndon word is a string that is strictly smaller (lexicographically) than all of its nontrivial rotations.
Broken Profile DP
Broken Profile DP is a dynamic programming technique that sweeps a grid one cell or one column at a time while encoding the boundary between processed and unprocessed cells as a compact state.
Slope Trick
Slope Trick is a technique to maintain a convex piecewise-linear function implicitly using two heaps and a running constant.
Aliens Trick (WQS Binary Search)
Aliens Trick (WQS Binary Search) converts a hard βexactly k itemsβ optimization into an unconstrained problem by adding a penalty Ξ» per chosen item.
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.
Divide and Conquer DP Optimization
Divide and Conquer DP optimization speeds up DP transitions of the form dp[i][j] = min over k of dp[i-1][k] + C(k, j) when the optimal k is monotone in j.
Convex Hull Trick - Dynamic (LineContainer)
Dynamic Convex Hull Trick (LineContainer) maintains the lower or upper envelope of lines y = m x + b with O(log n) insertion and O(log n) query for arbitrary insertion order.
Convex Hull Trick (CHT)
The Convex Hull Trick (CHT) speeds up dynamic programs where each state is a minimum over linear functions, such as dp[i] = min_j (dp[j] + b[j] Γ a[i]).