Convex Hull Trick answers "given many linear
functions, which one is largest at query x?" in O(1) amortized time —
but only if every line is known and inserted in decreasing-slope order up front, and only for a
non-decreasing stream of queries. A Li Chao Tree (introduced by Li Chao at ZJOI
2012) answers the exact same question with neither restriction: lines can arrive in any order,
queries can arrive in any order, interleaved however you like, each still costing
O(log U) — where U is the size of the fixed coordinate domain the tree
was built over, not the number of lines stored. The mechanism is a segment tree over the x-axis instead of over an
array: every node owns a range of x, and holds at most one line — whichever one is
currently winning at that range's own midpoint.
Four flat-rate courier contracts, each paying y = m·x + b for x
stops on today's route: B (y = x + 7), K
(y = -3x + 11), S (y = -x + 10), and
L (y = 3x + 2). The domain is fixed at x = 0..7 stops.
Press Step or Run to watch all four get inserted in the
scrambled order S, L, B, K — deliberately not sorted by slope — then a run of
stop counts get queried in the scrambled order 5, 0, 6, 2, 7, 1, 4, 3. Nothing
about either order matters to the result; that's the whole point of building the tree this way
instead of Convex Hull Trick's deque.
Insert walks down from the root, and at each node compares the incoming line
against whatever the node already holds — but only at that node's own midpoint. Whichever line
wins at the midpoint stays at that node; the loser gets pushed one level down, into
whichever child it could still possibly win in. On this page's own run: S arrives
first into the empty root. L arrives second — at the root's midpoint (x =
3) L scores 11 against S's 7, so L takes
the root and S gets pushed into the left child, node 2 (range [0,3]),
which is empty, so S settles there directly. B arrives third:
loses to L at the root's midpoint (10 vs 11), so it's pushed toward node 2; there
it loses to S at node 2's own midpoint (x = 1: 8 vs 9), so it's
pushed once more, landing in node 5 (range [2,3]), empty, done. K
follows the identical root → node 2 path and settles into node 4 (range [0,1]). Four
lines, four different nodes, no node ever holding more than one — and which child a loser gets
pushed into is decided by comparing the loser against the node's original occupant at the
range's two endpoints, not by anything about future inserts.
Query just walks one root-to-leaf path for the given x —
⌈log₂ U⌉ + 1 nodes, always, regardless of how many lines are stored — and takes the
maximum of every line found along the way. That's correct because insert's own invariant
guarantees whichever line is truly the best answer for any given x sits somewhere on
that x's own root-to-leaf path: either it's still winning at some ancestor's midpoint
and got kept there, or it lost at every midpoint on the way down and got pushed all the way to the
one leaf where it's never compared against anything else again. Querying x = 2 on
this page's tree visits node 1 (L = 8), node 2 (S = 8), and node
5 (B = 9) — B wins, correctly, despite never once being compared
directly against L at any point during either line's insertion.
class LiChaoTree {
constructor(lo, hi) { // fixed integer domain, inclusive
this.lo = lo;
this.hi = hi;
this.tree = new Map(); // node index -> line; absent means "no line yet"
}
evalAt(line, x) { return line.m * x + line.b; }
insert(line) { this._insert(1, this.lo, this.hi, line); }
_insert(idx, lo, hi, line) {
const cur = this.tree.get(idx);
if (!cur) { this.tree.set(idx, line); return; }
const mid = (lo + hi) >> 1;
const leftNewBetter = this.evalAt(line, lo) > this.evalAt(cur, lo);
const midNewBetter = this.evalAt(line, mid) > this.evalAt(cur, mid);
// the node keeps whichever line wins at its own midpoint
if (midNewBetter) { this.tree.set(idx, line); line = cur; }
if (lo === hi) return; // leaf -- nothing left to push down
// push the midpoint's loser toward whichever half it could still win in
if (leftNewBetter !== midNewBetter) this._insert(2 * idx, lo, mid, line);
else this._insert(2 * idx + 1, mid + 1, hi, line);
}
query(x) { return this._query(1, this.lo, this.hi, x); }
_query(idx, lo, hi, x) {
const cur = this.tree.get(idx);
let best = cur ? this.evalAt(cur, x) : -Infinity;
if (lo === hi) return best;
const mid = (lo + hi) >> 1;
const child = x <= mid
? this._query(2 * idx, lo, mid, x)
: this._query(2 * idx + 1, mid + 1, hi, x);
return Math.max(best, child);
}
}A tempting shortcut — compare and swap at the midpoint, then stop — silently drops
lines that are still the true best answer somewhere. It looks reasonable: if the incoming
line loses at the midpoint, why keep chasing it further down? Two lines make the bug concrete:
P (y = -x + 7) and Q (y = 4x - 8) over
domain x = 0..7. Insert P into the empty root, then
Q: at the root's midpoint (x = 3) both score exactly
4 — a tie, so Q isn't strictly better and a
swap-only implementation discards it right there, never pushing it anywhere. But
Q is the true maximum for every x from 4 to 7 (8, 12, 16,
20, against P's 3, 2, 1, 0) — the correct algorithm above
would have pushed the midpoint's loser into the right child exactly to cover that case, since
leftNewBetter and midNewBetter are equal here (both false) and the loser
still belongs on the right. Checked directly: the broken version answers all four of those queries
wrong, with no error of any kind. A 2,000-trial stress harness against random small line sets
(inserted in shuffled order) generalizes this: the correct algorithm matched an independent
brute-force max on every query across all trials; the swap-only version got at least one query
wrong on 1,079 of 2,000 trials, 2,176 of 16,000 individual
queries overall.
Querying outside the domain the tree was actually built for doesn't error — it just
silently walks the wrong path and can return a real line's value while missing a better one
entirely. Built over x = 0..7, insert A (y = 7x +
4) then B (y = -3x - 6): B ends up stored
only in the tree's right half (it's never the winner anywhere in [0,3], so it's never
pushed there). Query x = -10, well outside the built domain: the walk compares
-10 against each midpoint using the ordinary rule (x ≤ mid goes left),
and every midpoint in [0,7] is larger than -10 — so the walk goes left
every time and never visits the right half at all. The tree reports -66
(A's value, the only line on the all-left path); the true maximum is
24 (B's value at x = -10), missed completely. A
20,000-trial stress harness quantifies how often this bites: querying every real in-domain
x (0 through 7) never once produced a wrong answer, 0 of 160,000 checks, exactly as
the correctness argument above predicts — but querying a random point up to 100 past either edge
of the built domain came back wrong on 6,401 of 20,000 trials
(32.0%). The fix isn't a bounds check inside query() — it's choosing
[lo, hi] up front wide enough to cover every x that will ever actually be
asked for, the same discipline a fixed-size array-backed segment tree already requires.
The reason to reach for this over Convex Hull
Trick's deque is almost always that one of its two ordering assumptions doesn't hold: lines
that arrive interleaved with queries rather than all up front, lines whose slopes aren't known in
sorted order in advance, or queries that jump around instead of moving monotonically — exactly the
"fully online" shape competitive programming problems reach for this structure for, usually
speeding up a dynamic program the same way Convex Hull Trick does, just without its ordering
discipline. The trade is real, not free: this page's array-shaped storage allocates 2U
node slots up front regardless of how many lines ever get inserted, where Convex Hull Trick's deque
only ever holds as many entries as lines that actually survive. The Map-based
reference implementation above sidesteps that for a sparse domain — it only ever creates a node the
first time some insert's recursion actually reaches it, so a huge or unknown-in-advance domain costs
real memory only along the O(log U) paths actually walked, not O(U) flat.
Some competitive-programming implementations push this further still with dynamically-allocated
child pointers and lazy node creation for a domain too large to fix in advance at all (arbitrary
64-bit coordinates, for instance) — a genuinely different memory strategy from either version built
here, not just a bigger array.
Against this site's other structure built from the identical "one node per half of a fixed range" segment-tree shape: reach for a plain Segment Tree when what's stored at each node is a value combined by an associative operator (min, sum, gcd); reach for a Li Chao Tree when what's stored is a whole line (or, in fancier variants, any family of functions that only ever cross a bounded number of times) and the question is which one wins at a point, not what the combined value of a range is.
Insert: O(log U) per line — the walk depth is fixed by the
domain's size U = hi - lo + 1, not by how many lines are already stored, so the 1st
insert and the 100th cost the same. Query: O(log U) per query, for
the same reason — always exactly one root-to-leaf path. Both confirmed directly on this page's own
run: every insert and every query touched exactly 4 nodes, ⌈log₂ 8⌉ + 1, regardless
of position in either sequence. Space: O(U) for the array-backed
form built here (2U node slots exist whether or not a line is ever placed in most of
them); O(k log U) for the Map-based reference implementation above, where
k is the number of lines actually inserted — never worse than the array form, better
whenever U is large and few lines are ever inserted relative to it.
This site's guide, Choosing a Range Query Structure, sets this entry aside from the six it actually compares: it doesn't hold array values at all, it answers which of several inserted lines is largest at a query x, with no array or range-combining operation anywhere in sight.