Concepts5
Overflow Prevention Techniques
Integer overflow happens when a computed value exceeds the range of its type; in C++ this silently wraps for unsigned and is undefined for signed, so prevention is crucial.
Fast Exponentiation
Fast exponentiation (binary exponentiation) computes a^n using repeated squaring in O(log n) multiplications.
Chinese Remainder Theorem
The Chinese Remainder Theorem (CRT) reconstructs an integer from its remainders modulo pairwise coprime moduli and guarantees a unique answer modulo the product.
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.
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.