vault

Convex Hull Trick

28 min read

Convex Hull Trick

The Convex Hull Trick (CHT) is the dynamic-programming optimization that collapses recurrences of the form dp[i] = min_{j < i} (a_j · x_i + b_j) from O(n^2) to O(n log n) (or O(n) if both a_j and x_i are monotonic) by recognizing that the inner expression a_j · x_i + b_j defines a line L_j(x) = a_j · x + b_j in the plane, indexed by j, and that the per-i query — minimize over j of L_j(x_i) — is exactly evaluating the lower envelope of those lines at the point x_i. The lower envelope of n lines is a piecewise-linear concave function (the pointwise minimum of affine functions is concave; visually it looks like an inverted-V chain that rises to a peak then falls, since the steepest-positive-slope line wins for very negative x and the steepest-negative-slope line wins for very positive x). It can be maintained incrementally: add a line, possibly removing lines that become dominated. Pointwise queries on the envelope are O(log n) via binary search on the envelope’s breakpoints; if the queries arrive in sorted-x order (the so-called monotonic CHT), they are amortized O(1) using a deque-based sweep. The trick was first written down explicitly in competitive-programming circles around 2010 (the cp-algorithms canonical treatment dates from this era; the underlying lower-envelope geometry is classical computational geometry, going back to half-plane intersection algorithms in the 1970s). It is the third DP-optimization technique every senior algorithms candidate should know — alongside Monotonic Queue Optimization (for c1(j) + c2(i) cost decomposition) and Knuth’s Optimization (for quadrangle-inequality DPs). Canonical applications: production scheduling with linear setup costs, segment-cost minimization over a partitioned sequence, “when do I switch operating modes” problems where each “mode” has its own fixed-cost-plus-variable-cost line, and the optimal-pricing problems that gave rise to the technique’s competitive-programming popularity. The Li Chao Tree is a structured generalization that supports arbitrary line additions (no slope-order or monotonic-query assumption) and arbitrary point queries, both in O(log V) per operation (where V is the size of the discretized x-range), using O(V) space — for line insertions; segment insertions add an extra log factor (per oi-wiki, insert is O(log² n) for segments).

1. Intuition — Lines, Lower Envelopes, and Why DP Recurrences Hide a Geometry

The DP recurrence the trick targets:

dp[i] = min_{j < i} (a_j · x_i + b_j)

where a_j, b_j are functions of the index j (typically a_j = dp[j] or a_j = -2 · prefix[j], etc., depending on the source problem) and x_i is some quantity dependent on i (often x_i = arr[i] or x_i = i or x_i = prefix[i]).

Read the inner expression as a function of x:

L_j(x) := a_j · x + b_j     (a line in the plane, slope a_j, y-intercept b_j)

Then for fixed i, the inner minimization is

dp[i] = min_{j < i} L_j(x_i)

— evaluate every line L_j at x = x_i, return the smallest value. Geometrically, this is “evaluate the lower envelope of n lines at the point x_i.” The lower envelope is the function E(x) = min_j L_j(x).

It is concave — and this is the precise structural fact the trick rests on. Affine (linear) functions are simultaneously convex and concave, and the pointwise minimum of concave functions is concave (per Wikipedia: Convex function, pointwise maximum preserves convexity; by negation, pointwise minimum preserves concavity). Equivalently: for n lines, min_j L_j(x) rises while the steepest-positive-slope line dominates (the left end), passes through one or more intermediate transitions, then falls once the steepest-negative-slope line takes over (the right end) — a piecewise-linear curve whose slope only decreases as x increases, which is the defining property of a concave function. So E(x) is the graph of a piecewise-linear concave function: a connected chain of line segments, where each segment is a piece of one of the L_j’s, joined at “transition points” where the active line changes.

On terminology — why call it "Convex Hull Trick" if the envelope is concave?

The name comes from the dual geometric picture. Each line y = a x + b maps to a point (a, b) (slope, intercept). The lines that survive on the lower envelope of the primal correspond to vertices of the lower convex hull of these dual points; the dominated lines correspond to interior points of the hull. So building the lower envelope is building a convex hull in the dual — hence “convex hull trick.” The primal envelope itself is concave; the underlying combinatorial object (the dual hull) is convex.

A real-world analogy: imagine a set of n taxi companies, each charging a flat dispatch fee b_j plus a per-mile rate a_j. For a trip of x miles, company j charges a_j · x + b_j. The cheapest company depends on x — a low-fixed-cost-high-rate company (small b_j, large a_j) wins for short trips; a high-fixed-cost-low-rate company (large b_j, small a_j) wins for long trips. The “cheapest taxi for a trip of length x” is the lower envelope. As you walk along the x-axis from short to long trips, the cheapest company changes only at finitely many crossover points; between crossovers, one company dominates.

The trick is the realization that the DP’s inner min is not a 1D scalar query — it’s a lower-envelope query, and the lower envelope can be maintained incrementally as you process indices i = 1, 2, ..., n.

The intellectual leap: a generic DP author sees “min over j of an algebraic expression” and writes a for j: ... if cand < best: best = cand inner loop. The CHT-aware author sees the same expression as a line evaluation and reaches for a half-plane / convex-hull data structure. The asymptotics drop from O(n^2) to O(n log n) or O(n).

2. The Geometric Insight — Why the Envelope Is Convex and What That Buys Us

A line in the (x, y) plane has the form y = a · x + b. Two lines L_1: y = a_1 x + b_1 and L_2: y = a_2 x + b_2 (with a_1 ≠ a_2) intersect at the unique point

x* = (b_2 - b_1) / (a_1 - a_2)
y* = a_1 x* + b_1

Below x*, one line is “lower”; above x*, the other is. The lower envelope at any specific x picks whichever is lower.

For n lines, the lower envelope is a concave piecewise-linear function (see §1’s terminology note for why the trick is still named for a convex hull — the duality lives in the dual (slope, intercept) plane, not the primal). The lines that appear on the envelope (the ones that contribute a segment) are the “extreme” lines — those not dominated everywhere by a combination of other lines. The lines that don’t appear (dominated lines) can be discarded; they will never be the answer for any query.

A line L_2 = a_2 x + b_2 is dominated by lines L_1 = a_1 x + b_1 and L_3 = a_3 x + b_3 if and only if L_2 lies above the segment of the envelope between L_1 and L_3. Geometrically, this happens when the intersection of L_1 and L_2 is at or to the right of the intersection of L_1 and L_3. Algebraically:

intersect(L_1, L_2).x ≥ intersect(L_1, L_3).x

Expand:

(b_2 - b_1) / (a_1 - a_2) ≥ (b_3 - b_1) / (a_1 - a_3)

(With careful sign-handling for a_1 > a_2 > a_3 ordering.) This dominance test is the engine of the deque-based CHT: when adding a new line, repeatedly check whether the previous-back line is dominated by the new one and the line before it; if so, pop the previous-back. This is structurally identical to the Monotonic Deque’s “back-pop while dominated” loop but with a 2D geometric dominance condition instead of a scalar comparison.

The convexity of the envelope means each line contributes at most one segment. So an envelope of n lines has at most n segments and at most n - 1 transition points. Storing the envelope as a list of “(line, x-range)” pairs takes O(n) space.

3. Two Operating Regimes

The CHT splits into two regimes depending on assumptions about the input:

3.1 Static/Offline CHT — Lines Sorted by Slope, Queries Sorted by x

If you can sort all lines by slope before adding them, and queries arrive in sorted-x order, both insertions and queries are amortized O(1). Total: O(n) for the envelope build plus O(n) for queries. Best case. Used when the DP’s a_j is monotonic in j (e.g., a_j = dp[j] decreasing, or a_j = -2 · prefix[j] monotonic for monotone prefix).

Slope-order convention

Two equally valid conventions appear in the literature. This note uses decreasing slopes when adding to the min-envelope deque (so the deque’s front is the leftmost-active line — the steepest-positive-slope one — and queries sweep left-to-right popping from the front). cp-algorithms instead adds lines in increasing slope order for minimization (so the deque’s back is the leftmost-active line). The two conventions are mirror images of each other; the dominance test and the worked example below are internally consistent with the decreasing-slope convention. If you port code between sources, mind which end of the deque is the “leftmost-active” end.

3.2 Dynamic/Online CHT — General Lines, General Queries

When lines arrive in arbitrary order or queries arrive in arbitrary x-order, you need a sorted data structure (balanced BST, sorted vector with binary search, or Li Chao Tree). Insertion: O(log n). Query: O(log n). Total: O(n log n) for the DP. Used when the DP’s a_j is not monotonic or queries are out of order.

The static case is more common in competitive programming because problem-setters frequently arrange the input to make a_j monotonic; the dynamic case is more common in production settings.

4. Tiny Worked Example — Adding Three Lines and Querying

Lines:

  • L_1: y = 2x + 1 (slope 2, intercept 1)
  • L_2: y = 0x + 4 (slope 0, intercept 4) — a horizontal line at y = 4
  • L_3: y = -1x + 6 (slope -1, intercept 6)

We are minimizing, so we want the lower envelope.

4.1 Build the Envelope

Process lines in order of decreasing slope (so the envelope’s leftmost segment is the steepest-positive line, rightmost is the steepest-negative): L_1 (slope 2), L_2 (slope 0), L_3 (slope -1).

After L_1: envelope is just L_1 for all x. Deque: [L_1].

After L_2: intersection of L_1 and L_2: 2x + 1 = 4 → x = 1.5. For x < 1.5, L_1 is lower; for x > 1.5, L_2 is lower. Both contribute. Deque: [L_1, L_2].

After L_3: intersection of L_2 and L_3: 4 = -x + 6 → x = 2. So for x > 2, L_3 is lower than L_2. Now check whether L_2 is dominated by L_1 and L_3:

  • Intersection L_1 ∩ L_2: x = 1.5.
  • Intersection L_1 ∩ L_3: 2x + 1 = -x + 6 → x = 5/3 ≈ 1.667.

Since intersect(L_1, L_2).x = 1.5 < intersect(L_1, L_3).x = 5/3, the line L_2 is not dominated — there’s a region (x ∈ [1.5, 2]) where L_2 is strictly the lowest. Keep L_2. Deque: [L_1, L_2, L_3].

The envelope:

  • For x < 1.5: lowest line is L_1.
  • For 1.5 ≤ x < 2: lowest is L_2.
  • For x ≥ 2: lowest is L_3.

4.2 Query at Specific x

Query: x = 1. Active line: L_1. Value: 2·1 + 1 = 3. Verify: L_2(1) = 4, L_3(1) = 5. Min = 3. ✓

Query: x = 1.7. In [1.5, 2), active line: L_2. Value: 0 · 1.7 + 4 = 4. Verify: L_1(1.7) = 4.4, L_3(1.7) = 4.3. Min = 4. ✓

Query: x = 3. Active: L_3. Value: -3 + 6 = 3. Verify: L_1(3) = 7, L_2(3) = 4. Min = 3. ✓

4.3 Counterexample — When a Line Is Dominated

Add a fourth line L_4: y = 1x + 2.5 (slope 1, intercept 2.5). Slope 1 sits between L_1’s 2 and L_2’s 0, so re-inserting in slope-sorted order, the order would be L_1 (2), L_4 (1), L_2 (0), L_3 (-1).

Check whether L_4 is dominated:

  • Intersection L_1 ∩ L_4: 2x + 1 = x + 2.5 → x = 1.5.
  • Intersection L_4 ∩ L_2: x + 2.5 = 4 → x = 1.5.

Both intersections at x = 1.5! L_4 passes through the meeting point of L_1 and L_2. The dominance test is intersect(L_1, L_4).x ≥ intersect(L_1, L_2).x: 1.5 ≥ 1.5 (equality). By convention, equality means L_4 is barely dominated (it has zero-width segment on the envelope). Drop it. Deque after re-insertion: [L_1, L_2, L_3] — same as before.

This is the typical action in CHT: line additions often trigger a cascade of pops as previously-active lines turn out to be dominated by the new geometry.

5. Pseudocode — Static Min-CHT (Sorted Slopes, Sorted Queries)

StaticMinCHT:
    deque := empty deque of lines (each line = (slope, intercept))

    add_line(a, b):
        # Lines are added in *decreasing* order of slope (for min-envelope).
        new_line := (a, b)
        # Pop dominated back lines
        while size(deque) >= 2 AND is_dominated(deque[-2], deque[-1], new_line):
            deque.pop_back()
        deque.push_back(new_line)

    query(x):
        # Queries arrive in *increasing* order of x.
        # Front line stops being optimal once x passes its intersection with the next line.
        while size(deque) >= 2 AND value_at(deque[0], x) >= value_at(deque[1], x):
            deque.pop_front()
        return value_at(deque[0], x)

    value_at(line, x):
        return line.a * x + line.b

    is_dominated(L_prev, L_curr, L_new):
        # Returns True iff L_curr is below the lower envelope of L_prev and L_new
        # (i.e., L_curr never beats both at the same x).
        # Test: intersect(L_prev, L_new).x <= intersect(L_prev, L_curr).x
        return cross(L_prev, L_curr, L_new) <= 0

    cross(L1, L2, L3):
        # Cross-product test for dominance, integer-safe form:
        # L_2 is dominated iff (L_2.b - L_1.b) * (L_1.a - L_3.a) >= (L_3.b - L_1.b) * (L_1.a - L_2.a)
        # (signs depend on slope ordering; check the sign convention for your slope direction.)
        ...

The exact cross-product form depends on whether slopes are increasing or decreasing; cp-algorithms gives both forms.

6. Python Implementation — Static Monotonic Min-CHT

from collections import deque
from typing import Tuple
 
class MinCHT:
    """Static convex hull trick for minimization.
 
    Assumes:
    - Lines are added with strictly decreasing slope (for min-envelope).
    - Queries arrive in strictly increasing x.
 
    Time: O(1) amortized per add and per query.
    """
 
    def __init__(self) -> None:
        self.dq: deque[Tuple[float, float]] = deque()
 
    @staticmethod
    def _intersect_x(L1: Tuple[float, float], L2: Tuple[float, float]) -> float:
        """Return the x-coordinate of intersection of L1 and L2."""
        a1, b1 = L1
        a2, b2 = L2
        # a1 x + b1 = a2 x + b2  =>  x = (b2 - b1) / (a1 - a2)
        return (b2 - b1) / (a1 - a2)
 
    def add_line(self, a: float, b: float) -> None:
        new_line = (a, b)
        # Pop dominated back lines: a line at the back is dominated if
        # its intersection with the previous-back is at or after its
        # intersection with the new line.
        while len(self.dq) >= 2:
            L_prev = self.dq[-2]
            L_curr = self.dq[-1]
            if self._intersect_x(L_prev, new_line) <= self._intersect_x(L_prev, L_curr):
                self.dq.pop()
            else:
                break
        self.dq.append(new_line)
 
    def query(self, x: float) -> float:
        # Pop front lines that are no longer optimal at this x.
        while len(self.dq) >= 2:
            L_front = self.dq[0]
            L_next = self.dq[1]
            if L_front[0] * x + L_front[1] >= L_next[0] * x + L_next[1]:
                self.dq.popleft()
            else:
                break
        a, b = self.dq[0]
        return a * x + b
 
 
# Sanity check matching §4
cht = MinCHT()
# Add lines in decreasing slope order: L_1 (slope 2), L_2 (slope 0), L_3 (slope -1)
cht.add_line(2.0, 1.0)
cht.add_line(0.0, 4.0)
cht.add_line(-1.0, 6.0)
 
# Queries in increasing x order
assert cht.query(1.0) == 3.0   # L_1: 2*1 + 1 = 3
assert cht.query(1.7) == 4.0   # L_2: 0*1.7 + 4 = 4
assert cht.query(3.0) == 3.0   # L_3: -1*3 + 6 = 3

7. Application — Production Scheduling (Toy Worked DP)

A classic CHT application: you produce widgets over n days. On each day i, you can either produce widgets at a rate of r_i per dollar, or you can pay a fixed setup cost s_i and switch to a different machine. The cumulative cost dp[i] of having produced target_i widgets by day i follows a recurrence like

dp[i] = min_{j < i} (dp[j] + s_i + r_j · (target_i - target_j))

After algebraic manipulation:

dp[i] = s_i + target_i · min_{j < i} ( -r_j · target_i_normalized? + ... )

The key step is rewriting the inner minimization as min_{j} (a_j · x_i + b_j) for some appropriate definitions of a_j, b_j, x_i derived from the problem’s structure. Once in CHT form, the DP runs in O(n log n) instead of O(n^2).

A more concrete LeetCode-style example: Cut a Rod / Splitting a Sequence with Linear Cost. Given a sequence of values v_1, ..., v_n, partition it into contiguous segments; each segment of values v_j, ..., v_i costs a · S^2 + b · S + c where S = sum of values in the segment. Minimize total cost. Naïve DP: O(n^2). With CHT after expanding (prefix[i] - prefix[j])^2, the recurrence becomes dp[i] = prefix[i]^2 - 2 · prefix[i] · prefix[j] + dp[j] + prefix[j]^2 + ..., and the min_j over the linear-in-prefix[i] term -2 · prefix[i] · prefix[j] + (dp[j] + prefix[j]^2) is exactly a CHT query with a_j = -2 prefix[j], b_j = dp[j] + prefix[j]^2, x_i = prefix[i]. Total: O(n log n).

def split_sequence_min_cost(prefix: list[int]) -> float:
    """dp[i] = prefix[i]^2 + min_j (-2 prefix[i] prefix[j] + dp[j] + prefix[j]^2)."""
    n = len(prefix) - 1
    dp = [0.0] * (n + 1)
    cht = MinCHT()
    cht.add_line(-2.0 * prefix[0], dp[0] + prefix[0] ** 2)
    for i in range(1, n + 1):
        # Query: min over j < i of a_j * prefix[i] + b_j
        x = float(prefix[i])
        dp[i] = prefix[i] ** 2 + cht.query(x)
        # Add the line for j = i
        cht.add_line(-2.0 * prefix[i], dp[i] + prefix[i] ** 2)
    return dp[n]

This runs in O(n) total because both prefix is monotonic (so queries arrive in sorted-x order) and the slopes -2 · prefix[j] are monotonically decreasing in j.

8. Complexity

VariantInsertQueryTotal for n insertions + n queries
Static (sorted slopes + sorted queries)O(1) amortizedO(1) amortizedO(n)
Static (sorted slopes, arbitrary queries)O(1) amortizedO(log n)O(n log n)
Dynamic (sorted set of lines)O(log n)O(log n)O(n log n)
Li Chao Tree (segment tree of lines, line inserts)O(log V)O(log V)O(n log V) time, O(V) space
Li Chao Tree (segment inserts, not full lines)O(log² V)O(log V)O(n log² V) time, O(V) space

The amortized analysis of the static deque variant is identical to the Monotonic Deque’s: each line enters the deque at most once and leaves at most once; total deque operations across n insertions are ≤ 2n. Query operations have a similar amortized bound — each “front-pop while no longer optimal” can be charged to the line being popped, which leaves the deque at most once.

Compared to naïve O(n^2) DP: for n = 10^5, the naïve version is 10^{10} ops (~100 seconds), CHT is ~n to ~n log n (10 ms to 200 ms). The five-orders-of-magnitude speedup is exactly why CHT is taught and why it’s a senior-level interview / contest fixture.

9. Variants and Generalizations

9.1 Max-CHT

For dp[i] = max_{j} (a_j x_i + b_j), use the upper envelope instead. Symmetrically: build the envelope of n lines where you keep the upper boundary; lines are added in increasing slope order; the dominance condition flips sign. The Python implementation negates one of the algebraic signs and the comparator in the pop loop.

9.2 Li Chao Tree

When neither the slope nor the query order can be made monotonic, build a Li Chao Tree: a segment tree over a discretization of the x-axis where each node stores the single line that is “best” at the midpoint of its interval, and inserts recurse into the half where the new line might still beat the stored one. Inserting a full line is O(log V) where V is the size of the discretized x-range (per cp-algorithms, which gives the bound as O(log[C·ε⁻¹])). Inserting a line segment — a line defined only on a sub-interval [l, r] — splits into O(log V) canonical segment-tree intervals, each requiring an O(log V) recursive descent, for O(log² V) per insert (per oi-wiki). Query is O(log V) either way: descend the segment tree, take the minimum of the stored line at every visited node. Space is O(V) — one line slot per segment-tree node, and the tree has O(V) nodes.

The Li Chao Tree is named after a Chinese-language treatment by an author writing under the name Li Chao (李超), popularized in East-Asian olympiad circles and translated into the English-language CP literature around 2015. Used for problems where lines arrive in arbitrary order or where the query x values aren’t known in advance. The dynamic CHT data structure of choice for online streaming problems with line additions.

9.3 Kinetic Segment Tree / Kinetic Convex Hull

For problems where the lines themselves change over time (slopes shift, intercepts shift), kinetic data structures track the changing envelope. Niche; appears in dynamic-graph algorithms and some game-theoretic optimization. Out of scope for typical interviews.

9.4 Convex Hull (Geometric)

The static CHT data structure is dual to the Convex Hull computation in computational geometry. Each line y = a x + b corresponds to a point (a, b) (or more carefully, a line in projective duality), and the lower envelope corresponds to the lower convex hull of the points. So building the lower envelope of n lines is equivalent to running Andrew’s Monotone Chain (planned) or Graham Scan (planned) on the dual point set. This is why competitive-programming sources use the name “Convex Hull Trick” — the underlying algorithm is a convex-hull computation.

9.5 Dynamic Programming Optimizations Family

CHT is one of three major DP-speedup techniques every senior algorithms interview/competitive-programming candidate should know:

  • CHT for dp[i] = min_j (a_j x_i + b_j) — linear function in x_i.
  • Monotonic Queue Optimization for dp[i] = c2(i) + min_j (dp[j] + c1(j)) — additive cost decomposition.
  • Knuth’s Optimization for dp[i][j] = min_k (dp[i][k] + dp[k][j] + cost(i, j)) with quadrangle-inequality cost — used in matrix-chain-multiplication-style 2D DPs.
  • (Plus Divide and Conquer DP for “argmin is monotonically non-decreasing” 2D DPs.)

CHT is the “linear-in-x_i” specialization. Recognize the recurrence pattern and reach for the matching technique.

10. When to Use CHT — The Recognition Signal

The recurrence pattern: dp[i] = min_j (something_j · x_i + something_else_j) + constant_i. Two key features:

  1. The inner expression is linear in some quantity x_i derived from i.
  2. The slope and intercept of that line are functions of j only (not i).

If the cost is not linear in x_i (e.g., quadratic), see if you can pre-square or otherwise transform the recurrence to expose the linearity. The classic trick: (a - b)^2 = a^2 - 2ab + b^2, so a quadratic cost (prefix[i] - prefix[j])^2 + dp[j] decomposes into prefix[i]^2 - 2 · prefix[i] · prefix[j] + (dp[j] + prefix[j]^2) — the middle term is linear in prefix[i], and the rest is constant w.r.t. i or constant w.r.t. j. After this expansion, CHT applies.

If the cost is purely additive (no i × j cross-term), it’s Monotonic Queue Optimization territory, not CHT.

If the cost has the quadrangle-inequality structure — cost(a, c) + cost(b, d) ≤ cost(a, d) + cost(b, c) for a ≤ b ≤ c ≤ d — it’s Knuth’s Optimization territory.

11. Pitfalls

11.1 Wrong Slope Order at Insertion

For min-envelope, lines must be added in decreasing slope order (equivalently, in slope order such that each new line has slope strictly less than the previous, given the convention). For max-envelope, increasing slope. Mixing the conventions makes the deque non-monotonic; the “pop dominated back” check fails to fire correctly; wrong answers.

11.2 Wrong Query Order

For O(1) amortized queries, the query x must arrive in the order matching the envelope’s left-to-right scan (increasing for min-envelope with the standard “decreasing slope” convention; specifics depend on signs). If queries are out of order, use binary search (O(log n) per query).

11.3 Floating-Point Imprecision in Intersection Test

The intersection-x computation (b2 - b1) / (a1 - a2) is a division of floats; if a1 - a2 is small, the result is large and imprecise. For competitive programming with integer inputs, use the integer cross-product form of the dominance test:

is_dominated(L_prev, L_curr, L_new):
    # Equivalent to intersect(L_prev, L_new).x <= intersect(L_prev, L_curr).x,
    # but uses only integer arithmetic.
    return (L_curr.b - L_prev.b) * (L_prev.a - L_new.a) >= (L_new.b - L_prev.b) * (L_prev.a - L_curr.a)

(Sign-flip if slopes are negative or the envelope is upper, etc. — details in cp-algorithms.) The integer form avoids floating-point error and works exactly.

11.4 Forgetting to Add the dp[i] Constant Outside the CHT Query

dp[i] = constant_i + cht.query(x_i) — the constant_i (e.g., prefix[i]^2 in the segment-cost example) is added after the CHT returns its min. Forgetting it gives a corrupted DP. Check by tracing on a small example.

11.5 Misidentifying What Becomes the Slope vs Intercept

For dp[i] = c2(i) + min_j (a_j · x_i + b_j), the slope is a_j and the intercept is b_j — both depend on j only. If your derivation puts something dependent on i into a_j or b_j, you’ve decomposed wrong. Re-derive.

11.6 Reaching for CHT When Monotonic Queue Suffices

If the recurrence is dp[i] = c2(i) + min_j (dp[j] + c1(j)) (no j × i cross-term), it’s Monotonic Queue Optimization — the deque stores f(j) = dp[j] + c1(j) directly, with O(1) per query, no slope/intercept geometry. CHT works but is overkill; the deque is simpler and faster.

11.7 Not Handling Empty Deque on First Query

The first query happens before any line has been added. Either pre-add a “sentinel” line (e.g., +infinity constant) or guard the query with if not dq: return INF.

11.8 Confusing CHT With Convex Hull Algorithm

CHT is a DP optimization; computational-geometry convex hull is the algorithm for finding the boundary of a 2D point set. They are dual — and the static CHT envelope build is a convex hull computation in the dual space — but problem statements rarely mention “convex hull” when CHT is the right tool. The “trick” is recognizing the underlying geometry without it being stated.

11.9 Slope Ties Cause Equality Cases

Two lines with the same slope but different intercepts: only the lower-intercept one is on the lower envelope. The dominance check should drop the higher-intercept line; the equality case (same slope, same intercept) is degenerate (drop one). Most CHT implementations handle this implicitly via the ≥ / ≤ in the dominance check; double-check the comparator is ≥ (not >) for the strict dominance case.

11.10 Forgetting Li Chao Tree’s Range Discretization

Li Chao Tree requires you to specify the range of possible query x values up-front (so the segment tree can be built over [X_min, X_max]). For real-valued x, you must discretize first. Forgetting this leads to “missing” insertions or queries.

11.11 Integer Overflow in the Cross-Product Test

The integer cross-product (L_curr.b - L_prev.b) * (L_prev.a - L_new.a) can overflow 64-bit integers for problems with large slopes/intercepts. Use 128-bit integers (__int128 in GCC) or rational arithmetic when needed. Python is immune.

12. Diagram — The Lower Envelope of Three Lines

flowchart LR
    L1["L1: y = 2x + 1<br/>(slope 2)"]
    L2["L2: y = 0x + 4<br/>(slope 0)"]
    L3["L3: y = -x + 6<br/>(slope -1)"]

    X0["x < 1.5<br/>L1 dominates"]
    X1["1.5 ≤ x < 2<br/>L2 dominates"]
    X2["x ≥ 2<br/>L3 dominates"]

    L1 -->|"steep rising line<br/>best for small x"| X0
    L2 -->|"flat line<br/>best in middle"| X1
    L3 -->|"steep falling line<br/>best for large x"| X2

    X0 -->|"intersect at x=1.5"| X1
    X1 -->|"intersect at x=2"| X2

What this diagram shows. The lower envelope of three lines, drawn as a sequence of “active intervals” along the x-axis. Each box represents one piece of the piecewise-linear envelope. Far left (x < 1.5): line L_1, the steepest-rising of the three, is lowest because at very small x its low intercept (1) makes it dip below L_2 (constant 4) and L_3 (intercept 6). Middle (1.5 ≤ x < 2): line L_2, the flat (zero-slope) line, dominates because L_1 has risen above 4 (at x = 1.5) and L_3 hasn’t yet fallen below 4 (which it does at x = 2). Far right (x ≥ 2): line L_3 dominates because its negative slope eventually pulls it lower than the constant L_2 = 4. The transition points — x = 1.5 and x = 2 — are the intersections of consecutive lines on the envelope, and they are the only places the “active line” changes. As we sweep x left-to-right, we visit each line on the envelope exactly once; the deque-based CHT exploits this by storing lines in a deque ordered by their first-active x-coordinate, and front-popping as queries cross transition points. The concavity of the envelope — the slope of the active line is monotonically decreasing as x increases (2 → 0 → -1) — is the structural property that lets the trick work: each line, if it appears on the envelope at all, occupies a single contiguous interval, so dominated lines never re-enter the picture, and the deque needs only one pass.

13. Common Interview / Competitive-Programming Problems

ProblemSourceWhat’s tested
Concave Allocation (Codeforces)classical CPRecognize CHT-shaped recurrence
K Inverse Pairs / Partition SequencesclassicalQuadratic-cost DP, expand into linear-in-prefix form
USACO 2015 February Land AcquisitionUSACO GoldSort + CHT
LeetCode 410 Split Array Largest SumLC 410Binary search on answer; CHT shows up in advanced editorials
Build the Equator (CP)classical CPGeneric linear-in-x DP optimization
Coverage problems (CP)classicalDP shape f(i) = min_j (cost(i, j)) with linear-in-i cost
LeetCode 2818 Apply Operations to Maximize ScoreLC 2818Multiple optimizations stacked; CHT is a sub-routine
Codeforces 311B Cats TransportCFClassical CHT problem
Codeforces 932F Escape Through LeafCFTree DP + Li Chao Tree
Codeforces 1083E Hot Start UpCFDP with linear-in-prefix optimization
ATCoder DP Z (Frog Jump)ATCClassic CHT introductory problem
USACO 2018 January LifeguardsUSACO PlatinumDP + CHT

CHT is rare in standard FAANG-style coding interviews (typically the question would reduce to a simpler pattern like Monotonic Queue Optimization) but is a frequent “this would be too hard for a beginner; senior algorithm interviews ask it” question at Citadel, Jane Street, Bridgewater, DE Shaw, and competitive-programming-heavy hiring at quantitative funds. In olympiad / Codeforces problem sets, it is a rite of passage at the Div 1 / orange-purple level.

14. Open Questions

  • What’s the right online dynamic CHT data structure when the lines arrive in arbitrary order with arbitrary slopes? The Li Chao Tree gives O(log n) per operation but uses O(n log n) space if the x-range is large. A balanced BST of lines (sorted by slope) supports O(log n) per operation in O(n) space, but the implementation is intricate. For most competitive-programming use, Li Chao Tree is preferred for simplicity.
  • Can CHT be combined with Knuth’s Optimization for hybrid recurrences? In principle yes, but problems falling exactly into this niche are uncommon; usually one optimization or the other suffices.
  • How does CHT degrade in the presence of numerical errors? With floating-point, dominance tests near intersections can flip sign, leading to incorrect deque structure. The integer cross-product form is the standard mitigation; for inherently floating-point problems, use rational arithmetic or careful epsilon handling.
  • Are there alternatives to the Li Chao Tree for dynamic CHT that achieve O(1) amortized in some structured cases? Not that I’m aware of; the lower bound for “arbitrary line insertions, arbitrary point queries” appears to be O(log n) per operation by a comparison argument.

Uncertain

Verify: the precise origin and date of the “Convex Hull Trick” name and of the “Li Chao Tree” data structure. Reason: the underlying lower-envelope geometry is classical (Kirkpatrick & Seidel 1986, with antecedents in half-plane intersection from the 1970s) and well-documented; but the DP-optimization framing under the “CHT” name lives in Russian and Chinese olympiad write-ups whose authoritative dates I could not pin to a primary source within this pass — secondary English sources (cp-algorithms, codeforces blog 63823, oi-wiki) describe the technique without dating it, and oi-wiki gives no biographical information on Li Chao either. To resolve: locate (i) the original Russian/Chinese olympiad post introducing the deque-based CHT as a DP optimization, and (ii) the original Chinese post or contest editorial that introduced the Li Chao Tree under that name. Until then, treat the dates “around 2008–2010” for CHT and “around 2015” for Li Chao Tree as folklore, not citation.

15. See Also

Graph View

Backlinks