Optimization

Techniques for accelerating searches, transitions, and convolutions.

Headers

Header	Summary
adaptive_simpson.hpp	Numerically integrate a smooth real function on [left, right] with adaptive Simpson subdivision and an absolute error target.
convex_hull_trick.hpp	Monotone convex-hull trick for decreasing slopes and queries. Obsolete middle lines are removed by cross multiplication. Because query coordinates are also decreasing, the current optimum moves monotonically along the same stack and can be popped permanently.
larsch.hpp	LARSCH algorithm for online row-minima of totally monotone matrices. Alternating row and column reductions recursively discard columns that can no longer be minimal. Total monotonicity makes row argmins nondecreasing, so each discarded candidate is charged once and rows can be exposed online.
li_chao_tree.hpp	Affine function slope*x + intercept used by li_chao_tree.
max_plus_convolution.hpp	Max-plus convolution of two concave sequences.
parallel_binary_search.hpp	Run parallel binary search over prefixes of a common update list. ok must be a known true boundary and ng a known false boundary. Calling check(q) after t calls to update represents the predicate at prefix t.
simplex.hpp	Maximize cx subject to Ax <= b and x >= 0 with a two-phase simplex tableau; reports optimal, infeasible, or unbounded.
smawk.hpp	SMAWK algorithm: compute row minima of a totally monotone matrix. A stack reduction leaves at most one candidate column per row, recursion solves the odd rows, and monotone argmins bound the scan that interpolates each even row. Every row and column is discarded or scanned only O(1) times.