Li Chao Tree

A segment tree over the $x$-axis where each node stores one line — the one that is best at that node’s midpoint. Insert and query are both $O(\log C)$, with no requirement that slopes or queries arrive in any order.

The insight

At any node covering $[l,r]$ with midpoint $m$, keep the line that is better at $m$. When inserting a new line:

1. If the new line beats the stored one at $m$, swap them.
2. Two lines cross at most once, so the loser can only win on one side of $m$. Determine which side by comparing at $l$ (or $r$), and recurse into that child only.

One recursion branch per level → $O(\log C)$.

struct Line {
    long long m = 0, c = LLONG_MAX;                  // identity: +infinity
    long long operator()(long long x) const { return c == LLONG_MAX ? LLONG_MAX : m * x + c; }
};
 
struct LiChao {
    int n;
    vector<Line> t;
    LiChao(int n) : n(n), t(4 * n) {}
 
    void insert(int node, int l, int r, Line nw) {
        int m = (l + r) / 2;
        bool atMid  = nw(m) < t[node](m);
        bool atLeft = nw(l) < t[node](l);
        if (atMid) swap(t[node], nw);
        if (l == r) return;
        if (atLeft != atMid) insert(2*node, l, m, nw);
        else                 insert(2*node+1, m+1, r, nw);
    }
    long long query(int node, int l, int r, int x) {
        long long res = t[node](x);
        if (l == r) return res;
        int m = (l + r) / 2;
        return min(res, x <= m ? query(2*node, l, m, x) : query(2*node+1, m+1, r, x));
    }
};

Why it beats the convex hull trick

	CHT (monotone)	CHT (dynamic)	Li Chao
Slopes must be sorted	yes	no	no
Queries must be sorted	yes (pointer) / no (binary search)	no	no
Insert	$O(1)$ am.	$O(\log n)$	$O(\log C)$
Query	$O(1)$ / $O(\log n)$	$O(\log n)$	$O(\log C)$
Overflow risk in the comparison	high	high	none
Code length	short	long and fiddly	~25 lines
Handles non-linear functions	no	no	yes

The overflow point is worth emphasising: CHT’s “is this line unnecessary” test multiplies differences of slopes and intercepts, which overflows long long for realistic inputs and needs __int128. Li Chao only ever evaluates lines and compares the results, so it never overflows beyond the function values themselves.

Beyond lines

The algorithm needs only that any two stored functions cross at most once over the domain. So it works for:

• lines,
• any family of monotone functions that pairwise cross once,
• functions like $f(x)=a\sqrt{x}+b$ or $a/x+b$ with suitable parameters,
• piecewise-defined “cost of using option $i$ at time $x$” functions.

This is a real advantage over the convex hull trick, which is specific to lines.

Dynamic (sparse) Li Chao

When the $x$ range is $10^9$, allocate nodes lazily instead of preallocating $4n$:

struct Node { Line ln; int l = -1, r = -1; };
vector<Node> pool;
// create children on demand inside insert()

$O(q\log C)$ memory. This is the usual version in practice.

Line insertion over a range

A useful extension: “this line is only valid for $x\in [a,b]$”. Descend as in a segment tree update to the $O(\log C)$ canonical nodes covering $[a,b]$, and run the ordinary Li Chao insertion at each. Insert becomes $O({\log }^{2}C)$, query stays $O(\log C)$.

This solves problems where each candidate transition is only available in part of the domain — for instance “the $i$-th offer applies only for quantities between $a_i$ and $b_i$”.

Maximum instead of minimum

Flip every comparison, or negate both $m$ and $c$ on insertion and negate the query result. Negating is less error-prone.

See also: Convex Hull Trick · Segment Tree · Slope Trick