Concepts318
Category
CDQ Divide and Conquer
CDQ divide and conquer is an offline technique that splits the timeline (or one coordinate) and lets updates from the left half contribute to queries in the right half.
Matrix Exponentiation
Matrix exponentiation turns repeated linear transitions into a single fast power of a matrix using exponentiation by squaring.
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.
Half-Plane Intersection
Half-plane intersection (HPI) computes the common region that satisfies many linear side-of-line constraints in the plane.
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.
Small-to-Large Merging
Small-to-large merging is a technique where you always merge the smaller container into the larger one to guarantee low total work.
Mo's Algorithm
Mo's algorithm answers many range queries offline by reordering them to minimize pointer movement along the array.
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.
Pick's Theorem
Pick's Theorem connects area and lattice-point counts for any simple polygon with integer-coordinate vertices.
Meet in the Middle
Meet-in-the-middle splits a hard exponential search into two halves, enumerates each half, and then combines results efficiently.
Closest Pair of Points
The closest pair of points problem asks for the minimum Euclidean distance between any two points in the plane.