The Convex Hull Trick

Why the convex hull trick matters

A huge class of one-dimensional dynamic programs has a transition that looks like this:

dp[i] = min over j < i of ( dp[j] + cost(j, i) )

where the cross term cost(j, i) happens to factor into a part that depends on j multiplied by a value read from i, plus leftovers. Written out, each candidate j contributes a value m_j · x_i + b_j — a straight line evaluated at the query coordinate x_i. The slope m_j and intercept b_j depend only on the earlier state j; the query point x_i depends only on the current state i.

Naively you scan every j for every i: O(n) candidates per state, O(n²) total. But for a fixed query x_i, the minimum over a bunch of lines is not some scattered value — it is exactly the height of the lower envelope of those lines at x = x_i. If you maintain that envelope as you go, each minimization becomes a lookup on a convex piecewise-linear curve: O(log n) with binary search, or O(1) amortized if the queries march monotonically. That is the whole trick, and it is the difference between a solution that times out and one that runs in a fraction of a second on n = 10⁶.

How it works, step by step

Picture each candidate as an infinite line y = m·x + b drawn on the plane. Stack all of them together. For any vertical query line x = x_i, the smallest y among all the lines is what the DP wants. The set of points that are the smallest-y for some x forms the lower envelope — a convex, downward-facing chain of line segments. Only the lines that appear on this envelope can ever be the answer; every other line is dominated everywhere and can be discarded.

The three moving parts are:

• The envelope structure — an ordered list (stack or deque) of the lines that survive, sorted so that as x increases you move along the chain from steeper-negative to shallower slopes (for a lower envelope of a min query, slopes are stored in decreasing order).
• Insertion — add a new line and pop any previously-stored line that the newcomer has made irrelevant.
• Query — find, for a given x_i, which segment of the envelope is active, and evaluate that line there.

Insertion: the pop test

Suppose the stack top holds line L1 then L2 (L2 newer), and we want to add L3. Line L2 is now useless — it never wins on any x — precisely when the intersection of L1 and L3 lies at or before the intersection of L1 and L2. In other words, L3 takes over from L1 before L2 ever gets a turn. To avoid floating-point division, this is tested with cross-multiplied integers:

bad(L1, L2, L3) ⟺ (b3 − b1)·(m1 − m2) ≤ (b2 − b1)·(m1 − m3)

If bad is true, pop L2 and re-test with the new top. Because slopes arrive in monotone order, each line is pushed once and popped at most once — O(1) amortized per insertion, O(n) to build the whole envelope.

Query: binary search or pointer sweep

Each consecutive pair of lines on the envelope crosses at a well-defined x. Those crossing points partition the x-axis into intervals, one line ruling each interval. To answer a query x_i:

• General queries: binary search the crossing points for the interval containing x_i, then evaluate that line — O(log n).
• Monotone queries: if the x_i values are non-decreasing, keep a pointer that only ever advances forward through the envelope. Across all queries the pointer moves O(n) times total — O(1) amortized each.

The Li Chao tree alternative

The stack/deque version has two hard requirements: slopes must be inserted in monotone order, and (for O(1) queries) query points must be monotone too. Real problems often violate both — insertions and queries interleave online, and slopes come in any order. The Li Chao tree, introduced by competitive programmer Li Chao, removes both constraints.

It is a segment tree built over the domain of possible x values (compressed to O(n) distinct coordinates if the domain is large). Each node covers an x-interval and stores the single line that is dominant at that node's midpoint. Inserting a line walks the tree from the root: at each node it compares the incoming line with the stored line at the midpoint, keeps whichever is lower there, and recurses into the half where the other line might still win. Because a pair of lines crosses at most once, the recursion descends only one side — O(log C) per insertion, where C is the coordinate range. A query walks root-to-leaf collecting the minimum over the stored lines on the path — also O(log C).

	Convex hull (stack/deque)	Li Chao tree
Insert order	Monotone slopes required (or sort offline)	Any order
Query order	Any (binary search) / monotone (pointer)	Any
Insert time	O(1) amortized (sorted) / O(log n)	O(log C)
Query time	O(log n) / O(1) amortized	O(log C)
Online interleaving	Hard (deletion is awkward)	Natural
Constant factor	Very small	Larger (tree traversal)
Space	O(n)	O(C) or O(n) compressed

Rule of thumb: if your slopes and queries are both monotone, use the hull — it is simpler and faster by a constant factor. If either is arbitrary or the operations are interleaved online, reach for the Li Chao tree. For fully dynamic line sets with deletions, the "Kinetic Segment Tree" or an std::set-based dynamic hull (the "LineContainer" idiom) generalizes further at O(log n) per operation.

A worked example: batch scheduling

Consider a classic DP. You must partition n jobs (in order) into contiguous batches. Running a batch costs a fixed setup charge S plus a per-job cost that grows with how late the batch finishes. A common form yields:

dp[i] = min over j < i of ( dp[j] + S + (prefix[i] − prefix[j]) · t[i] )

Expand the product: dp[j] + S + prefix[i]·t[i] − prefix[j]·t[i]. Group the parts by who they depend on. The term prefix[i]·t[i] + S is a constant for a fixed i — pull it outside the min. What remains is:

min over j of ( dp[j] − prefix[j]·t[i] ) = min over j of ( (−prefix[j])·t[i] + dp[j] )

Now it is exactly a line! Candidate j contributes slope m_j = −prefix[j] and intercept b_j = dp[j], queried at x_i = t[i]. Since prefix[j] is non-decreasing, the slopes −prefix[j] arrive in decreasing order — perfect for the monotonic stack. If the query values t[i] are also monotone, the whole DP runs in O(n). Otherwise binary search each query for O(n log n).

How it works in Python (monotonic-stack min hull)

class ConvexHullTrick:
    """Lower envelope for min queries.
    Insert lines with DECREASING slope. Query x may be arbitrary (binary search)."""
    def __init__(self):
        self.m = []   # slopes, stored in decreasing order
        self.b = []   # intercepts

    def _bad(self, l1, l2, l3):
        # True if the middle line l2 is never optimal and can be dropped.
        # Integer cross-product form — no division, no float error.
        # (b3 - b1)*(m1 - m2) <= (b2 - b1)*(m1 - m3)
        return ((self.b[l3] - self.b[l1]) * (self.m[l1] - self.m[l2])
                <= (self.b[l2] - self.b[l1]) * (self.m[l1] - self.m[l3]))

    def add_line(self, m, b):
        # Requires m <= last inserted slope (monotone non-increasing).
        self.m.append(m)
        self.b.append(b)
        while len(self.m) >= 3 and self._bad(len(self.m) - 3,
                                             len(self.m) - 2,
                                             len(self.m) - 1):
            # remove the second-to-last line
            self.m.pop(-2)
            self.b.pop(-2)

    def _eval(self, i, x):
        return self.m[i] * x + self.b[i]

    def query(self, x):
        # Binary search for the line minimizing at x (envelope is convex).
        lo, hi = 0, len(self.m) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if self._eval(mid, x) > self._eval(mid + 1, x):
                lo = mid + 1
            else:
                hi = mid
        return self._eval(lo, x)


# Batch-scheduling DP driver (slopes -prefix[j] decrease, so stack is valid).
def min_batch_cost(prefix, t, S):
    n = len(prefix)
    dp = [0] * n
    cht = ConvexHullTrick()
    cht.add_line(-prefix[0], dp[0])          # line from j = 0
    for i in range(1, n):
        best = cht.query(t[i])               # min_j (-prefix[j]*t[i] + dp[j])
        dp[i] = best + prefix[i] * t[i] + S
        cht.add_line(-prefix[i], dp[i])      # register i as a future candidate
    return dp[n - 1]

If the query values t[i] were guaranteed non-decreasing, you would replace the binary search in query with a monotone pointer that only advances, dropping the per-query cost to O(1) amortized and the whole DP to O(n).

Common misconceptions and pitfalls

• Confusing the envelope with the convex hull of points. The name is a slight misnomer: you are not computing the geometric convex hull of a point set (that is Graham scan). You are computing the lower/upper envelope of a set of lines, which is the dual notion — a line y = mx + b maps to the point (m, b), and the envelope corresponds to the hull of those dual points. Same convexity, different object.
• Using the stack version with out-of-order slopes. If slopes are not monotone, a new line may belong in the middle of the envelope, which the stack cannot insert in O(1). Sort offline first, or use a Li Chao tree. This is the single most common cause of a "wrong answer" on hull-trick problems.
• Mixing up min and max. A min query needs the lower envelope (slopes decreasing); a max query needs the upper envelope (slopes increasing). Get the direction backwards and you silently return the worst candidate. The cleanest fix is to negate all slopes and intercepts, run the min version, and negate the result.
• Floating-point intersection tests. Computing crossing points as (b1 − b2) / (m2 − m1) in floating point corrupts the pop decision on tight inputs. Use the integer cross-product bad test, and beware overflow — intermediate products can reach ~10¹⁸, so use 64-bit or 128-bit integers.
• Assuming monotone queries when they are not. The O(1)-amortized pointer sweep only works if query x values are non-decreasing. If they are not, the pointer can walk backward and the amortized argument collapses — you must binary search instead.
• Duplicate slopes. Two lines with identical slope never cross; keep only the one with the smaller intercept (for a min hull). Feeding both into the pop test can divide by a zero slope difference if you use the division form.

Where it sits in the DP-optimization family

The convex hull trick is one of a handful of techniques that shave a factor of n off a quadratic DP by exploiting structure in the cost function:

• Convex hull trick — applies when the cost splits into slope · query + intercept, i.e. the transition is a min/max of lines.
• Divide-and-conquer optimization — applies when the optimal split point opt[i] is monotone; gives O(n log n) per layer.
• Knuth's optimization — applies to interval DPs where opt[i][j−1] ≤ opt[i][j] ≤ opt[i+1][j] (the quadrangle inequality); gives O(n²).
• SMAWK / Monge matrix — a totally-monotone-matrix row-minima technique underlying several of the above.

All of them are refinements of the same broad idea in dynamic programming: avoid re-examining candidates that provable structure guarantees can never be optimal.