Convex Hull Trick

Optimise a DP of the form

$dp[i]={\min }_{j<i}(m_j\cdot x_i+c_j)$

from $O(n^2)$ to $O(n)$ or $O(n\log n)$. Each earlier state contributes a line; the answer at $x_i$ is the lower envelope of those lines evaluated at $x_i$.

The geometry

A set of lines $y=mx+c$ has a lower envelope that is a convex piecewise-linear function. Lines that are never minimal anywhere can be discarded permanently. Maintaining that envelope is the whole technique.

A line is unnecessary if, for lines ${\ell }_1,{\ell }_2,{\ell }_3$ in slope order, ${\ell }_2$ lies above the intersection of ${\ell }_1$ and ${\ell }_3$:

bool bad(Line a, Line b, Line c) {              // is b unnecessary?
    // intersection of a,c is left of or at the intersection of a,b
    return (long double)(c.c - a.c) * (a.m - b.m) <= (long double)(b.c - a.c) * (a.m - c.m);
}

Monotone case — $O(n)$

When slopes are added in monotone order and queries arrive in monotone order, a deque plus a moving pointer gives amortized $O(1)$ per operation.

struct CHT {
    vector<long long> M, C;
    int ptr = 0;
    void add(long long m, long long c) {         // slopes added in decreasing order (for min)
        while (M.size() >= 2 && bad(M.size() - 2, M.size() - 1, m, c)) { M.pop_back(); C.pop_back(); }
        M.push_back(m); C.push_back(c);
    }
    long long query(long long x) {               // x non-decreasing
        ptr = min<int>(ptr, M.size() - 1);
        while (ptr + 1 < (int)M.size() && M[ptr+1]*x + C[ptr+1] <= M[ptr]*x + C[ptr]) ptr++;
        return M[ptr] * x + C[ptr];
    }
};

If slopes are monotone but queries are not, replace the pointer with a binary search — $O(\log n)$ per query.

Arbitrary order — Li Chao tree

When neither slopes nor queries are monotone, use a Li Chao tree: a segment tree over the $x$ range where each node stores the line that is best at its midpoint. Insert and query are both $O(\log C)$, and the code is far shorter than a fully dynamic hull.

struct LiChao {
    struct Line { long long m, c; long long operator()(long long x) const { return m*x + c; } };
    vector<Line> t;                                // sized 4 * range
    void insert(int node, int l, int r, Line nw) {
        int m = (l + r) / 2;
        bool lef = nw(l) < t[node](l), mid = nw(m) < t[node](m);
        if (mid) swap(t[node], nw);
        if (l == r) return;
        if (lef != mid) insert(2*node, l, m, nw);
        else            insert(2*node+1, m+1, r, nw);
    }
    long long query(int node, int l, int r, long long x) {
        if (l == r) return t[node](x);
        int m = (l + r) / 2;
        return min(t[node](x), x <= m ? query(2*node, l, m, x) : query(2*node+1, m+1, r, x));
    }
};

Li Chao also handles arbitrary functions that pairwise cross at most once — not just lines.

Recognising the pattern

The trick applies whenever the transition factorises into a product of something depending on $j$ and something depending on $i$:

$dp[i]={\min }_j(\underset{\text{slope}}{\underbrace{f(j)}}\cdot \underset{x}{\underbrace{g(i)}}+\underset{\text{intercept}}{\underbrace{h(j)}})+(\text{terms in }i\text{ only}).$

Example. $dp[i]={\min }_{j<i}(dp[j]+(a_i-a_j{)}^2)$ expands to
$dp[i]=a_i^2+{\min }_j(\underset{m}{\underbrace{-2a_j}}\cdot \underset{x}{\underbrace{a_i}}+\underset{c}{\underbrace{dp[j]+a_j^2}}).$

Choosing an implementation

Slopes	Queries	Structure	Time
monotone	monotone	deque + pointer	$O(n)$
monotone	arbitrary	vector + binary search	$O(n\log n)$
arbitrary	arbitrary	Li Chao tree	$O(n\log C)$
arbitrary	arbitrary	dynamic hull (multiset)	$O(n\log n)$
lines added and removed	arbitrary	Li Chao + offline segment tree on time	$O(n{\log }^{2}n)$
divide and conquer over the array	—	CHT inside CDQ	$O(n{\log }^{2}n)$

Overflow and precision

The bad test multiplies differences of slopes and intercepts — with values up to $10^9$ and $10^{18}$ this overflows long long. Use __int128 for the comparison, or long double if a small precision risk is acceptable. Li Chao avoids the issue entirely by only ever comparing line values, which is a good reason to prefer it.

See also: Li Chao Tree · D&C DP · Slope Trick