Concepts116
Category
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.
Line Sweep
Line sweep (plane sweep) is a technique that processes geometric objects by moving an imaginary line and handling events in sorted order.
Polygon Area and Centroid
The signed area of a simple polygon can be computed in O(n) using the shoelace formula, which sums cross products of consecutive vertices.