Convex Hull Trick & Li Chao Tree

Many DP transitions look like

dp[i] = min_{j < i} ( cost[j] · x[i] + dp[j] ) + toll[i]

That is exactly: maintain lines y = k·x + b and query the minimum at x = x[i].

Naive enumeration is O(n²). With the convex hull trick (CHT) or a Li Chao tree you get O(n log n) (or O(n) amortized when slopes are monotone).

This lesson follows CP-Algorithms — Convex hull trick and Li Chao tree.

Motivating DP

n cities on a line at positions x₁ < … < xₙ. Gas costs costₖ in city k; entering city k costs tollₖ. One liter per kilometer, tank starts empty:

dp[i] = toll[i] + min_{j < i} ( cost[j] · (x[i] − x[j]) + dp[j] )

Rewrite as lines: for each previous j, the candidate is

y = cost[j] · x + (dp[j] − cost[j] · x[j])

evaluated at x = x[i]. Insert line after finishing i, then query at the next position.

Convex hull trick

Treat line kx + b as point (k, b). Minimizing kx + b at a fixed x is the same as finding the point with least dot product against (x, 1). That optimum lies on the lower convex envelope of the points.

When CHT is easy

Scenario	Structure
Slopes k inserted monotone	Deque / vector hull, O(1) amortized insert
Offline: all lines first, then queries	Sort + hull, then binary search
Online arbitrary slopes	Balanced BST of hull edges (harder) or √ rebuild
Fully online, any lines	Prefer Li Chao tree

Insert (increasing k, minimize)

Keep hull points and inward normals of edges. While the last turn is not counter-clockwise (dot of last normal with new − last < 0), pop. Then push the new point.

typedef long long ftype;
typedef complex<ftype> point;
#define x real
#define y imag

ftype dot(point a, point b) { return (conj(a) * b).x(); }
ftype cross(point a, point b) { return (conj(a) * b).y(); }

vector<point> hull, vecs;

void add_line(ftype k, ftype b) {
    point nw = {k, b};
    while (!vecs.empty() && dot(vecs.back(), nw - hull.back()) < 0) {
        hull.pop_back();
        vecs.pop_back();
    }
    if (!hull.empty())
        vecs.push_back(point(0, 1) * (nw - hull.back())); // rotate 90°
    hull.push_back(nw);
}

(Use 1i * (nw - hull.back()) in C++ as in the article.)

Query

Binary-search the first normal directed counter-clockwise from (x, 1). The left endpoint of that edge is optimal:

ftype get(ftype x0) {
    point query = {x0, 1};
    auto it = lower_bound(vecs.begin(), vecs.end(), query,
        [](point a, point b) { return cross(a, b) > 0; });
    return dot(query, hull[it - vecs.begin()]);
}

If query x is also monotone, walk a pointer on the hull instead of lower_bound → overall O(n).

🧪 CHT: insert increasing slopes, query min

Interactive CHT

Watch lines with increasing slopes join the lower envelope, then evaluate min at several x.

Check: CHT

Quiz

Convex hull trick

1 / 4

dp[i] = min_j (k[j]·x[i] + b[j]) is solved by…

Pick an answer to see if you are right.

Li Chao tree

Assume any two functions intersect at most once (true for distinct lines). Keep a segment tree on the x-domain. Each node stores one function such that on every root-to-leaf path, some stored function is optimal at that leaf.

Insert f_new at node [l, r)

Let f_old be stored. Let m = ⌊(l+r)/2⌋. Compare f_new and f_old at l and m to see which half contains the intersection. Keep the lower function at m in this node; recurse into the other half with the upper one.

typedef long long ftype;
typedef complex<ftype> point;
#define x real
#define y imag

ftype dot(point a, point b) { return (conj(a) * b).x(); }
ftype f(point a, ftype xv) { return dot(a, {xv, 1}); }

const int maxn = 2e5;
point line[4 * maxn]; // init to 0·x + ∞

void add_line(point nw, int v = 1, int l = 0, int r = maxn) {
    int m = (l + r) / 2;
    bool lef = f(nw, l) < f(line[v], l);
    bool mid = f(nw, m) < f(line[v], m);
    if (mid) swap(line[v], nw);
    if (r - l == 1) return;
    if (lef != mid) add_line(nw, 2 * v, l, m);
    else add_line(nw, 2 * v + 1, m, r);
}

ftype get(int xv, int v = 1, int l = 0, int r = maxn) {
    int m = (l + r) / 2;
    if (r - l == 1) return f(line[v], xv);
    if (xv < m) return min(f(line[v], xv), get(xv, 2 * v, l, m));
    return min(f(line[v], xv), get(xv, 2 * v + 1, m, r));
}

Complexity: O(log (C/ε)) per insert/query. For huge coordinates or doubles, use a dynamic segment tree.

Li Chao works online with arbitrary insertion order — ideal when CHT’s monotone-slope assumption fails (or for tree DP with segment-tree merges).

Choosing a tool

Need	Use
Slopes & queries monotone	Deque CHT — O(n)
Slopes monotone, queries offline/arbitrary	Vector CHT + binary search
Arbitrary lines, online	Li Chao
Lines on a tree / mergeable	Li Chao + small-to-large or segtree merge

Check: Li Chao

Quiz

Li Chao tree

1 / 4

Li Chao assumes pairs of functions…

Pick an answer to see if you are right.

Practice drills

Activity: Eval line

k b x → print k*x + b.

Contest problems

C. Kalila and Dimna in the Logging Industry

Judge: Codeforces 319C

Cut trees with monotone heights/b costs. Classic dp[i] = min_j dp[j] + b[j]·a[i] → CHT with decreasing slopes.

Why this lesson?

Textbook monotone CHT DP.

Cheat sheet

Goal	Tool
min_j kⱼ x + bⱼ	CHT / Li Chao
Monotone k & x	Deque — O(n)
Monotone k, any x	Hull + lower_bound
Arbitrary online lines	Li Chao O(log C)
√n rebuild	Simple online CHT without BST

Previous: Continued Fractions · Basic Geometry

Source: CP-Algorithms — Convex hull trick and Li Chao tree