Convex hull trick and Li Chao tree: minimum over lines

Why this matters when you build with AI

A common DP transition looks like this: dp[i] is the best over all earlier j of dp[j] plus a product of a value from j and a value from i. An AI tool that sees a product in the transition will often write a double loop over i and j. That is O(n^2), and at n = 2 * 10^5 it does 2 * 10^10 steps. The sample passes, and the judge does not.

The convex hull trick (CHT) turns this into a line query. Each earlier j gives one line, and each new i asks for the lowest line at one point. The Li Chao tree does the same job with a different structure, and it works when the points come in any order. Both are short to write, and both have failure modes that a generated answer often misses: overflow in a cross product, a wrong tie rule, and a pointer that moves the wrong way. This lesson builds both and checks them against a brute force.

A prompt that asks for the reduction in writing, so a wrong line is easy to catch:

Write C++17 code for this problem. Input: n, then n pairs a_i b_i with a_i >= 1 and |b_i| <= 10^4.
Cut the array into consecutive segments. With prefix sums A[i] = a_1 + ... + a_i and
B[i] = b_1 + ... + b_i, a segment (j, i] costs (A[i] - A[j]) * B[i]. Minimise the total of all segments.
Before the code, write the transition for dp[i], then rewrite it as a line f_j(x) = m_j * x + k_j
and say which value is the query point. Say which of your numbers can exceed 64 bits and why.
Then give the code and its output on the sample "4 / 2 1 / 3 -2 / 1 4 / 5 -1". The output must be 7.

A good answer writes dp[i] = A[i] * B[i] + min over j of (dp[j] - A[j] * B[i]), names the line slope -A[j] and intercept dp[j], names B[i] as the query point, and prints 7. A bad answer leaves out the A[i] * B[i] term, or it multiplies two intercept differences in plain long long without a bound. Check the answer against a brute force, as in the stress section below.

Terms used

A line is a function f(x) = m * x + k. Here m is the slope and k is the intercept.
The lower envelope of a set of lines is, for each x, the smallest value among the lines. The hull is the set of lines that appear on the envelope.
A query is a question "what is the smallest line value at x?"
A cross product here means comparing two fractions by multiplying across, so no division is needed.
A Li Chao tree is a binary tree over the query points. Each node keeps one line that is the best at the middle point of its range.
Coordinate compression replaces large values by their rank among the sorted distinct values.
__int128 is a 128-bit integer type in GCC and Clang. It is not part of the C++ standard.

The idea: a transition is a line query

Take the sample: n = 4, a = 2 3 1 5, b = 1 -2 4 -1. Prefix sums are A = 0, 2, 5, 6, 11 and B = 0, 1, -1, 3, 2. A segment (j, i] costs (A[i] - A[j]) * B[i]. The cheapest split costs 7, and this is the one the program prints.

Here is the rewrite, step by step. Let dp[0] = 0 and dp[i] be the cheapest cost of cutting the first i items. Then

dp[i] = min over j < i of  dp[j] + (A[i] - A[j]) * B[i]

Expand the bracket. The part that depends on j alone is dp[j] - A[j] * B[i]. The term A[i] * B[i] does not depend on j, so it can be taken out of the minimum:

dp[i] = A[i] * B[i] + min over j of ( (-A[j]) * B[i] + dp[j] )

Now each j is a line with slope m_j = -A[j] and intercept k_j = dp[j]. The query point is x = B[i]. The state dp[i] is computed by one query, and then its line is added for later use.

Check dp[1] by hand. Only j = 0 exists, with line slope 0 and intercept 0. The query at x = B[1] = 1 gives 0. So dp[1] = 0 + A[1] * B[1] = 2 * 1 = 2. Check dp[2]: the lines are slope 0 intercept 0, and slope -2 intercept 2. At x = B[2] = -1, the values are 0 and 4. The minimum is 0, so dp[2] = 0 + 5 * (-1) = -5. The brute force gives the same: from j = 0, cost 5 * (-1) = -5; from j = 1, cost 2 + 3 * (-1) = -1. The smaller one is -5.

Why the answer needs the hull

With many lines, most are never the minimum. A line is useful only on an interval of x where it is below all others. The set of useful lines, in order of x, is the lower envelope. A new line can make some old lines useless, and those can be removed.

The rule that removes a line is the core of the method. Take three lines l1, l2, l3 with slopes m1 > m2 > m3, added in that order. Line l2 is useless when l1 and l3 cross at an x no greater than the x where l1 and l2 cross. In formulas, with intersection points x12 = (k2 - k1) / (m1 - m2) and x13 = (k3 - k1) / (m1 - m3), the middle line is useless when x13 <= x12. Both denominators are positive, so this is the same as

(k3 - k1) * (m1 - m2) <= (k2 - k1) * (m1 - m3)

This is the cross product. It is where overflow appears, and the code uses __int128 for it.

The slopes -A[j] are added in non-increasing order, since A grows. For the lower envelope, a line with a larger slope is better on the left, so the lines on the hull are stored in the order they were added, and the hull is searched by x.

Binary search on the hull

For a fixed x, the values along the hull go down, then up. So a binary search finds the bottom. Compare the value at mid with the value at mid + 1: if the left is larger, the minimum is to the right.

ll query(ll x) const {
    int lo = 0, hi = (int)h.size() - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (h[mid].at(x) > h[mid + 1].at(x)) lo = mid + 1;
        else hi = mid;
    }
    return h[lo].at(x);
}

This is O(log n) per query. It works for any query order.

Monotone pointer: when the queries are sorted

If the query points come in non-decreasing order, a pointer can walk along the hull and never go back. This is O(1) amortised per query, because the pointer only moves right. The condition for it is strict: the queries must be sorted. Here B[i] is sorted only when every b_i >= 0. For general b it is not.

ll query(ll x) {
    while (ptr + 1 < h.size() && h[ptr + 1].at(x) <= h[ptr].at(x)) ptr++;
    return h[ptr].at(x);
}

The pointer must also be kept inside the hull when lines are removed from the back. The code does this with if (ptr >= h.size()) ptr = h.size() - 1; after each add. The stress test below checks this version on inputs with all b_i >= 0.

Li Chao tree: any slopes, any queries

The Li Chao tree avoids the cross product and the hull order altogether. It keeps one line per node of a binary tree over the sorted query points xs. Each node stores the line that is best at the middle point of its range. When a new line comes in, the node compares the two lines at the left end and the middle. The worse line at the middle moves down to the child that might still win there.

Because the query points are known in advance (the input gives all b values before the answer is needed in the DP order), the tree can be built over the sorted distinct B values. Each insert and query walks one path, so each costs O(log n). Here is the insert:

void insert(int node, int l, int r, Line nw) {
    int mid = (l + r) / 2;
    bool leftBetter = nw.at(xs[l]) < t[node].at(xs[l]);
    bool midBetter = nw.at(xs[mid]) < t[node].at(xs[mid]);
    if (midBetter) swap(t[node], nw);  // the node keeps the better line at mid
    if (l == r) return;
    if (leftBetter != midBetter) insert(2 * node, l, mid, nw);
    else insert(2 * node + 1, mid + 1, r, nw);
}

The rule for going down is the standard one: after the swap, the line in the node is the better one at mid. The line that was dropped can only be better in the half where it was better at one end, so it goes to that half. If the two lines agree on the left end and at mid, the loser can only win on the right, and it goes right.

Worked example: the full program

This program runs three methods: the binary-search hull, the monotone pointer hull, and the Li Chao tree. It also has the naive O(n^2) reference. The file is the same one the stress test includes. It compiles with g++ -O2 -std=c++17.

// Lesson 08: line-cost partition. Cut the array 1..n into consecutive segments.
// Prefix sums A[i] = a_1 + ... + a_i and B[i] = b_1 + ... + b_i (a_i >= 1, b_i may be negative).
// A segment (j, i] costs (A[i] - A[j]) * B[i]. dp[0] = 0 and
// dp[i] = min over j < i of dp[j] + (A[i] - A[j]) * B[i]. Print dp[n].
// Rewritten as lines: dp[i] = A[i]*B[i] + min over j of (-A[j]) * B[i] + dp[j].
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128;
 
struct Line {
    ll m, b;
    ll at(ll x) const { return m * x + b; }
};
 
// Returns true when line mid is never strictly below both neighbours l1 and l3 (slopes m1 > m2 > m3).
// Compare the x positions where l1 meets l3 and where l1 meets l2. The products can need about 10^23,
// so they are computed in __int128.
static bool useless(const Line& l1, const Line& l2, const Line& l3) {
    return (i128)(l3.b - l1.b) * (l1.m - l2.m) <= (i128)(l2.b - l1.b) * (l1.m - l3.m);
}
 
// Lower envelope of lines added in non-increasing slope order. Queries use binary search.
struct Hull {
    vector<Line> h;
    void add(Line nw) {
        if (!h.empty() && h.back().m == nw.m) {
            if (h.back().b <= nw.b) return;  // same slope, the new line is not lower anywhere
            h.pop_back();
        }
        while (h.size() >= 2 && useless(h[h.size() - 2], h.back(), nw)) h.pop_back();
        h.push_back(nw);
    }
    ll query(ll x) const {
        // The values along the hull go down, then up, for a fixed x. Find the bottom.
        int lo = 0, hi = (int)h.size() - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (h[mid].at(x) > h[mid + 1].at(x)) lo = mid + 1;
            else hi = mid;
        }
        return h[lo].at(x);
    }
};
 
// Same hull, but queries must come in non-decreasing x. A pointer only moves right.
struct HullPointer {
    vector<Line> h;
    size_t ptr = 0;
    void add(Line nw) {
        if (!h.empty() && h.back().m == nw.m) {
            if (h.back().b <= nw.b) return;
            h.pop_back();
        }
        while (h.size() >= 2 && useless(h[h.size() - 2], h.back(), nw)) h.pop_back();
        h.push_back(nw);
        if (ptr >= h.size()) ptr = h.size() - 1;
    }
    ll query(ll x) {
        while (ptr + 1 < h.size() && h[ptr + 1].at(x) <= h[ptr].at(x)) ptr++;
        return h[ptr].at(x);
    }
};
 
// Li Chao tree over the sorted distinct query points xs. Each node keeps one line.
// Works for any query order and any slopes, and is O(log n) per insert and query.
struct LiChao {
    vector<ll> xs;
    vector<Line> t;
    LiChao(const vector<ll>& pts) : xs(pts) {
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        t.assign(4 * max<size_t>(1, xs.size()), Line{0, LLONG_MAX / 4});  // "no line yet"
    }
    void insert(int node, int l, int r, Line nw) {
        int mid = (l + r) / 2;
        bool leftBetter = nw.at(xs[l]) < t[node].at(xs[l]);
        bool midBetter = nw.at(xs[mid]) < t[node].at(xs[mid]);
        if (midBetter) swap(t[node], nw);  // the node keeps the better line at mid
        if (l == r) return;
        if (leftBetter != midBetter) insert(2 * node, l, mid, nw);
        else insert(2 * node + 1, mid + 1, r, nw);
    }
    void add(Line nw) { insert(1, 0, (int)xs.size() - 1, nw); }
    ll query(ll x) const {
        int idx = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
        int node = 1, l = 0, r = (int)xs.size() - 1;
        ll best = LLONG_MAX / 4;
        while (true) {
            best = min(best, t[node].at(x));
            if (l == r) break;
            int mid = (l + r) / 2;
            if (idx <= mid) { node = 2 * node; r = mid; }
            else { node = 2 * node + 1; l = mid + 1; }
        }
        return best;
    }
};
 
// Reference: try every j for every i. O(n^2).
ll solveNaive(const vector<ll>& a, const vector<ll>& b) {
    int n = a.size();
    vector<ll> A(n + 1, 0), B(n + 1, 0), dp(n + 1, 0);
    for (int i = 1; i <= n; i++) { A[i] = A[i - 1] + a[i - 1]; B[i] = B[i - 1] + b[i - 1]; }
    for (int i = 1; i <= n; i++) {
        ll best = LLONG_MAX;
        for (int j = 0; j < i; j++) best = min(best, dp[j] + (A[i] - A[j]) * B[i]);
        dp[i] = best;
    }
    return dp[n];
}
 
// Builds the prefix arrays, then runs the lines. kind: 0 binary-search hull, 1 pointer hull, 2 Li Chao.
ll solveFast(const vector<ll>& a, const vector<ll>& b, int kind) {
    int n = a.size();
    vector<ll> A(n + 1, 0), B(n + 1, 0), dp(n + 1, 0);
    for (int i = 1; i <= n; i++) { A[i] = A[i - 1] + a[i - 1]; B[i] = B[i - 1] + b[i - 1]; }
    Hull hull;
    HullPointer hp;
    LiChao lc(vector<ll>(B.begin() + 1, B.end()));
    hull.add(Line{0, 0});
    hp.add(Line{0, 0});
    lc.add(Line{0, 0});
    for (int i = 1; i <= n; i++) {
        ll best;
        if (kind == 0) best = hull.query(B[i]);
        else if (kind == 1) best = hp.query(B[i]);
        else best = lc.query(B[i]);
        dp[i] = best + A[i] * B[i];
        Line nw{-A[i], dp[i]};
        hull.add(nw);
        hp.add(nw);
        lc.add(nw);
    }
    return dp[n];
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
    cout << solveFast(a, b, 0) << "\n";
    return 0;
}

Run it on the two inputs below. The output is from the real build.

$ printf "4\n2 1\n3 -2\n1 4\n5 -1\n" | ./cht
7
$ printf "1\n2 3\n" | ./cht
6

The second case is one segment with A = 2 and B = 3, so the cost is 2 * 3 = 6.

The trace below shows the hull for the sample. It is the real output of a trace program that calls the same Hull code.

A = 0 2 5 6 11
B = 0 1 -1 3 2
after line j=0 (slope 0, intercept 0): [m=0 b=0]
i=1 query x=B[i]=1 best line value=0 dp[i]=2  hull: [m=0 b=0] [m=-2 b=2]
i=2 query x=B[i]=-1 best line value=0 dp[i]=-5  hull: [m=0 b=0] [m=-5 b=-5]
i=3 query x=B[i]=3 best line value=-20 dp[i]=-2  hull: [m=0 b=0] [m=-5 b=-5] [m=-6 b=-2]
i=4 query x=B[i]=2 best line value=-15 dp[i]=7  hull: [m=0 b=0] [m=-5 b=-5] [m=-11 b=7]
dp[n] = 7

Two steps show the removal rule at work. At i = 2 the line [m=-2 b=2] is dropped when [m=-5 b=-5] arrives. Its cross-product check is (-5 - 0) * (0 - (-2)) = -10 on the left and (2 - 0) * (0 - (-5)) = 10 on the right, and -10 <= 10, so it is useless. It is never the minimum: it would have to be below 0 at x > 1, but there the line with slope -5 is already below it.

How it was tested

Three checks, all on my machine with g++ 15.2.0 at -O2:

6000 random small inputs (n from 1 to 40, values up to 50 for a and up to 60 in size for b). The naive answer was compared with the binary-search hull and the Li Chao tree. On the 3000 cases where all b_i >= 0, the monotone pointer was also compared.
2000 tie-heavy inputs (n up to 30, a from 1 to 3, b from -2 to 2, so many lines share slopes and intercepts). The hull and Li Chao matched the naive answer on all of them.
Larger inputs with a up to 100 and b in [-100, 100] (n = 20000 for the naive reference, and n = 200000 for the two fast methods, which agree with each other).

All of these checks passed. This is evidence on random inputs. The rules above are the argument for why the code is right.

The overflow that breaks plain long long

The cross product in useless is the risky part. With a up to 10^4, |b| up to 10^4 and n up to 2 * 10^5, the prefix sums reach about 2 * 10^9. The intercepts (the dp values) reach about 4 * 10^15, and the slope differences reach about 2 * 10^9. Their product is about 10^25, which is above the 9.2 * 10^18 limit of a 64-bit signed integer.

I built a copy of the program with the __int128 casts replaced by plain long long, and ran it on the same random input as the correct one. Real output:

n=20000, a up to 10000, |b| up to 10000, naive:             -70051180961591
n=20000, binary-search hull with __int128:                  -70051180961591
n=20000, binary-search hull with plain long long:           -69809038334812
n=200000, binary-search hull with __int128:                 -4542322775466146
n=200000, Li Chao tree (no cross product):                  -4542322775466146
n=200000, binary-search hull with plain long long:          -3091438138936063

The plain version does not crash. It prints a number that looks like an answer and is wrong. The sample from this lesson is small enough that the overflow never happens, which is why the sample passes. The __int128 version agrees with the Li Chao tree, which has no cross product, so it is the one to trust.

The bound on the dp values also needs a check. Every segment costs at most |A| * max|B|, and the segments' lengths in A add up to A[n], so |dp| <= A[n] * max|B| <= 2 * 10^9 * 2 * 10^9 = 4 * 10^18. That fits in a 64-bit integer, but only just. The sum dp[j] - A[j] * B[i] can reach 8 * 10^18, which is still below 9.2 * 10^18. A larger limit would need a different type or a modulus.

Timing

Timings on the same machine as the other lessons (12 hardware threads, Linux under WSL2, g++ 15.2.0, -O2). Values a up to 100 and b in [-100, 100] unless stated. Your numbers will differ.

n	method	time
20000	naive O(n^2)	125 ms
20000	binary-search hull	3.5 ms
200000	binary-search hull	31 ms to 40 ms
200000	Li Chao tree	40 ms to 69 ms
200000	pointer hull (b >= 0)	33 ms

The naive time is measured at n = 20000. At n = 200000 the naive loop does about 100 times as many steps, so about 10^10 steps. I did not run that size. The fast methods are close in speed, and the choice between them is about which one is easier to get right. The hull is shorter and faster on this data. The Li Chao tree needs no sorting of the lines and handles any query order without a special case.

Common mistakes

Multiplying two differences in long long. The symptom is a wrong answer with no crash, and it appears only with large values. Use __int128 for the cross product, or check the bound on your inputs first.
Forgetting the A[i] * B[i] term. The symptom is an answer that is too small by that product. It is easy to miss, because it is not part of the line.
Using the pointer hull on unsorted queries. The symptom is a wrong answer on inputs with negative b values. The pointer only moves right, so when a query is to the left of the previous one, the best line can be behind it.
Mishandling equal slopes. With equal slopes, keep the line with the smaller intercept. The code does this at the start of add(). The tie-heavy test covers it.
Removing a line with < instead of <=. Both are correct in value. With <, the hull can hold a line that touches the envelope at one point only, which is harmless but slower. Use <= and say so in a comment.
Building the Li Chao tree over the wrong set of points. The query points are the B values. If you compress the slopes or the A values by mistake, lower_bound returns an index that is not in the tree, and the answer is off.
Starting the Li Chao tree with an empty value that is too small, for example 0. Then no real line ever wins, and the answer is wrong. The code uses LLONG_MAX / 4 with slope 0, which is larger than every real value here and does not overflow when evaluated, because the slope is 0.

Checklist

Expand the transition and find the term that depends on j alone. That is the line. The term that depends on i alone is added outside the minimum.
Write the slope, intercept and query point for each step before the code.
Check the order in which slopes are added. The binary-search hull needs non-increasing slopes for this form.
Use __int128 for the cross product unless you have checked the bound on your inputs.
Use the pointer only when the query points are sorted. The pointer gives wrong answers on inputs with negative b values.
Keep the tie rule the same in the hull and in your reference. Test with many equal slopes.
Stress-test against the O(n^2) loop on random inputs, with and without negative values.

Summary

A DP transition of the form min(dp[j] + b[j] * a[i]) is a line query. The hull keeps the lines that can be the minimum, and a binary search finds the best one for each query. A monotone pointer is faster but needs sorted queries. A Li Chao tree handles any slopes and any query order at O(log n) each. The main risk is overflow in the cross product, which gives wrong answers with no error. Check the value bounds, use a 128-bit product, and compare with the O(n^2) loop.

Practice

Take n = 1, a = 5, b = -2. Compute the answer by hand, then run the program with this input. Hint: one segment, so dp[1] is the cost of that single segment.

Show the answer

The only segment is (0, 1], which costs (A[1] - A[0]) * B[1] = 5 * (-2) = -10. The program prints -10.
Explain in plain words why the monotone pointer fails when some b values are negative, and give a three-item input where it gives a wrong answer. You do not have to run it. Hint: think about which way the pointer can move, and whether the best line for a smaller query can be behind it.

Show the answer

The pointer moves only right. If a later query x is smaller than an earlier one, the best line for x can be to the left of the pointer, so the pointer never reaches it. Input 5 with a = 4 3 1 1 5 and b = 2 1 -5 3 3 shows it: the naive loop prints 5, and the pointer version prints 21. The pointer code was run on 20000 random small inputs, and this is the first one where they differ.
Estimate the largest |dp| for n = 2 * 10^5, a up to 10^3 and |b| up to 10^3, and say whether plain long long is enough for the dp values and for the cross product. Show the arithmetic. Hint: use the bound from this lesson, |dp| <= A[n] * max|B|, and the product of slope and intercept differences.

Show the answer

A[n] <= 2 * 10^5 * 10^3 = 2 * 10^8, and max|B| <= 2 * 10^8, so |dp| <= 4 * 10^16. That fits in long long. The cross product multiplies an intercept difference (up to about 8 * 10^16) by a slope difference (up to about 2 * 10^8), which is about 1.6 * 10^25. That is too large for long long, so the cross product still needs __int128.
The Li Chao tree in this lesson uses the B values, which are known before the DP runs. Describe what changes if the query points come online, that is, each query depends on the answer to an earlier query. Say what the memory cost becomes. Hint: a fixed array of nodes needs the points in advance.

Show the answer

The tree must cover the whole possible range of query points, not a compressed list. Nodes are created when a line is inserted and a child is needed, so each insert creates at most O(log C) nodes, where C is the size of the range. For values up to about 2 * 10^9, that is about 32 levels, so memory is O(n log C) nodes in the worst case. The lesson's version uses one array of 4 times the number of distinct points, which would not fit a range of 4 * 10^9.