Li Chao Tree

The problem it solves

Suppose you keep adding lines y = m·x + b to a set, and between additions someone hands you an x and asks: of all the lines I've added, which one is lowest here? This is the minimum-at-x query, and it is the beating heart of an entire family of dynamic-programming speedups collectively called the convex hull trick (CHT). A transition like dp[i] = min over j of (dp[j] + cost(j, i)) often factors into "evaluate a bunch of lines at a point," and turning an O(n²) DP into O(n log n) hinges on answering those queries fast.

The classic CHT keeps the lower envelope of the lines as an explicit stack and binary-searches it — but it only works cleanly when slopes are added in sorted order and queries are monotone. Break either assumption and the bookkeeping turns into a minefield of pops, special cases, and floating-point intersection tests. The Li Chao tree, introduced by competitive programmer Li Chao and popularized through Codeforces around 2017, throws the hull away entirely. It stores the lines implicitly in a segment tree over the query domain and never sorts, never pops, and never computes an intersection. That is the whole pitch: same queries, none of the fragility.

How it works: keep the midpoint winner, push the loser down

Build a segment tree over the discrete range of possible query coordinates, say [0, C). Each node owns an x-interval [l, r) and stores at most one line — the line that, as far as this node knows, is the best candidate over its interval. Initially every node is empty.

To insert a new line f at a node holding line g, look at the midpoint mid = (l + r) / 2 and compare which line is lower at mid. The crucial fact is that two distinct non-parallel lines cross exactly once, so over the interval one line wins the left part and the other wins the right part. Therefore:

• Keep the midpoint winner in this node. It is guaranteed to be best on at least one full half of the interval, so storing it for the whole node is safe.
• The loser can only overtake on one half — the half where it was already better at an endpoint relative to the midpoint. Recurse into exactly that one child with the loser as the new line to insert.

You touch one node per level and stop at the leaves, so an insertion is O(height) = O(log C). A query at point x is even simpler: walk from the root down to the leaf containing x, evaluating the stored line at each node along the path, and return the minimum value seen. Because every line that could be best at x was, by the insert invariant, parked somewhere on that root-to-leaf path, this O(log C) walk is exact.

Notice what is absent: no slope sorting, no intersection coordinates, no envelope to repair. The "convex hull" lives nowhere — it is reconstructed lazily, one node at a time, by midpoint comparisons.

When to reach for it

• DP optimizations where lines and queries are unordered. If slopes arrive sorted and queries are monotone, the monotone-CHT stack is faster; the Li Chao tree shines precisely when neither holds.
• You value correctness over a constant factor. The insert/query logic is a dozen lines and has no edge cases around vertical lines, equal slopes, or floating-point ties.
• Queries land on a known, bounded coordinate set. A Li Chao tree wants a fixed domain [0, C) or a known sorted list of query x-values to index against. Unbounded real-valued queries need coordinate compression first.
• Online insert/query interleaving. Unlike offline-only tricks, you can freely mix inserts and queries.

Reach for something else when: slopes are monotone and queries are monotone (use the O(1)-amortized stack CHT), you need deletions in true online fashion (use the balanced-BST "LineContainer" or a divide-and-conquer-on-time Li Chao), or the cost function is not expressible as lines at all (then you are out of CHT territory entirely).

Li Chao tree vs the alternatives

	Li Chao tree	Monotone CHT (stack)	LineContainer (BST)	Kinetic Segment Tree
Insert line	O(log C)	O(1) amortized	O(log n)	O(log n) amortized
Query min at x	O(log C)	O(1) amortized / O(log n)	O(log n)	O(log n)
Slopes must be sorted	No	Yes	No	No
Queries must be monotone	No	Yes (else add binary search)	No	No
Supports deletion	No (persistent/offline only)	No	No (only via rebuild)	No
Float / overflow risk	Low (just evaluate at integers)	Higher (intersection coords)	Higher (division in cmp)	Moderate
Lines of code	~15	~25 (with binary search)	~40	~60

The headline trade is constant factor versus simplicity. The monotone stack is the fastest by a clear margin when its preconditions hold. The Li Chao tree throws away those preconditions for a log factor and a far shorter, harder-to-break implementation — which is why it is the default teaching tool for CHT today.

What the numbers actually say

• Query coordinate range C, not number of lines n, sets the depth. With a coordinate range of one billion (10⁹), the tree height is ⌈log₂ 10⁹⌉ = 30. Every insert and query touches at most 30 nodes — independent of how many lines you have inserted.
• Recursive (array) version uses O(C) memory. For C = 10⁶ that is roughly 2·10⁶ stored lines' worth of slots — a few tens of megabytes. For C = 10⁹ you must switch to the dynamic / sparse node-allocated version, which costs O(n log C) nodes for n inserts: 10⁵ lines × 30 ≈ 3 million nodes.
• Overflow is the real-world failure mode, not time. Evaluating m·x + b with |m|, |b|, |x| up to 10⁹ produces values up to ~10¹⁸ — right at the edge of signed 64-bit. Initialize empty nodes with a sentinel large enough but not so large it overflows on the next add.
• Constant factor vs monotone CHT: typically 2–4×. On a 10⁶-line, 10⁶-query benchmark, a clean monotone stack runs in tens of milliseconds; a Li Chao tree of the same workload runs in the low hundreds. Both are trivially fast; the difference matters only at the largest contest limits.

JavaScript implementation

This is the recursive version over a fixed integer domain [0, size), answering minimum-at-x. Lines are [m, b]; an empty slot is a line that is "infinitely high everywhere."

// Minimum-at-x Li Chao tree over integer coordinates [0, size).
// tree[node] holds a line [m, b], or null if empty.
class LiChaoTree {
  constructor(size) {
    this.size = size;
    this.tree = new Array(4 * size).fill(null); // segment-tree array
  }

  static f([m, b], x) { return m * x + b; }      // value of a line at x

  // Insert line [m,b] into the node covering [l, r].
  insert(line, node = 1, l = 0, r = this.size - 1) {
    let cur = this.tree[node];
    if (cur === null) { this.tree[node] = line; return; }
    const mid = (l + r) >> 1;
    // Does the NEW line win at the left end? at the midpoint?
    const leftBetter = LiChaoTree.f(line, l)   < LiChaoTree.f(cur, l);
    const midBetter  = LiChaoTree.f(line, mid) < LiChaoTree.f(cur, mid);
    // Keep the midpoint winner here; push the loser into the half it can still win.
    if (midBetter) { this.tree[node] = line; line = cur; } // swap: store new, demote old
    if (l === r) return;                                   // leaf: nowhere to push
    if (leftBetter !== midBetter) this.insert(line, 2 * node,     l,       mid);
    else                          this.insert(line, 2 * node + 1, mid + 1, r);
  }

  // Minimum value of any inserted line at coordinate x.
  query(x, node = 1, l = 0, r = this.size - 1) {
    const cur = this.tree[node];
    const here = cur === null ? Infinity : LiChaoTree.f(cur, x);
    if (l === r) return here;
    const mid = (l + r) >> 1;
    return x <= mid
      ? Math.min(here, this.query(x, 2 * node,     l,       mid))
      : Math.min(here, this.query(x, 2 * node + 1, mid + 1, r));
  }
}

// --- usage ---
const t = new LiChaoTree(1_000_000);
t.insert([2, 5]);    // y = 2x + 5
t.insert([-1, 800]); // y = -x + 800
t.insert([0, 100]);  // y = 100
console.log(t.query(0));   // 5   (line 2x+5)
console.log(t.query(500)); // 100 (line y=100 is lowest here)
console.log(t.query(900)); // -100 (line -x+800 wins)

The swap trick on the line if (midBetter) { ... line = cur; } is what keeps the code branch-free of "which line do I recurse with": after deciding the node's keeper, line always refers to the demoted loser, and the leftBetter !== midBetter XOR picks the single half where that loser can still take over.

Python implementation

Same algorithm. For huge coordinate ranges, prefer the dynamic form that allocates child nodes lazily — shown here so you can index against a real-world [lo, hi] with no 4·C array.

INF = float('inf')

class _Node:
    __slots__ = ('line', 'left', 'right')
    def __init__(self):
        self.line = None          # (m, b) or None
        self.left = self.right = None

def fval(line, x):
    return INF if line is None else line[0] * x + line[1]

class LiChaoTree:
    def __init__(self, lo, hi):   # closed integer range [lo, hi]
        self.lo, self.hi = lo, hi
        self.root = _Node()

    def insert(self, m, b):
        self._insert(self.root, self.lo, self.hi, (m, b))

    def _insert(self, node, l, r, line):
        cur = node.line
        if cur is None:
            node.line = line
            return
        mid = (l + r) // 2
        left_better = fval(line, l)   < fval(cur, l)
        mid_better  = fval(line, mid) < fval(cur, mid)
        if mid_better:
            node.line, line = line, cur     # keep midpoint winner, demote loser
        if l == r:
            return
        if left_better != mid_better:
            if node.left is None: node.left = _Node()
            self._insert(node.left, l, mid, line)
        else:
            if node.right is None: node.right = _Node()
            self._insert(node.right, mid + 1, r, line)

    def query(self, x):
        return self._query(self.root, self.lo, self.hi, x)

    def _query(self, node, l, r, x):
        if node is None:
            return INF
        best = fval(node.line, x)
        if l == r:
            return best
        mid = (l + r) // 2
        if x <= mid:
            return min(best, self._query(node.left,  l, mid, x))
        return min(best, self._query(node.right, mid + 1, r, x))

# Maximum-at-x? Insert (-m, -b), query x, negate the result.
t = LiChaoTree(0, 10**9)
for m, b in [(2, 5), (-1, 800), (0, 100)]:
    t.insert(m, b)
print(t.query(0), t.query(500), t.query(900))  # 5 100 -100

Variants worth knowing

Dynamic (sparse) Li Chao tree. Shown above: allocate nodes on demand so the domain can be the full [−10⁹, 10⁹] without a giant array. Costs O(n log C) nodes total.

Li Chao tree of segments (Kinetic / "lines on intervals"). Insert a line that is only valid on a sub-range [l, r]. Descend to the O(log C) canonical segment-tree nodes covering [l, r] first, then run the normal midpoint-insert inside each — O(log² C) per insertion. This is how you add "edges only alive during certain x" and is the backbone of several offline geometry problems.

Persistent Li Chao tree. Copy the O(log C) nodes touched on each insert instead of mutating them, exactly as in a persistent segment tree. You then query any past version, which simulates deletion by reverting — useful for DP on trees where you "undo" a line when leaving a subtree.

Mergeable / small-to-large Li Chao. For DP on trees (e.g. tree-distance optimizations), maintain one tree per subtree and merge children by reinserting the smaller tree's lines into the larger — O(n log² C) overall via the small-to-large argument.

LineContainer (the BST alternative). Not a Li Chao tree at all, but the other modern CHT: a std::multiset of lines ordered by slope, kept on the lower envelope with on-the-fly intersection comparisons. Faster constant, supports arbitrary slopes and queries, but trickier and harder to make exact with integers.

Common bugs and edge cases

• Recursing with the wrong line after the swap. After you decide the node's keeper, you must recurse with the loser. Forgetting to swap (or swapping conditionally and then using the wrong variable) silently drops lines and produces too-large answers.
• The XOR child-selection. The correct rule is "recurse left iff leftBetter != midBetter." A common slip is comparing the new line's win at the right endpoint instead, or comparing the original (pre-swap) lines — re-derive it from "where can the demoted line still win."
• Integer overflow in m·x + b. With |m|, |x| ≈ 10⁹ the product is 10¹⁸. Use 64-bit (or 128-bit for safety) and pick a sentinel for empty nodes that won't overflow when a real line is later compared against it.
• Querying outside the built domain. The tree only knows [lo, hi]. Coordinate-compress to the set of query x-values, or build over the exact closed range you will query; an out-of-range x walks off into undefined nodes.
• Mid computed as (l + r) / 2 in a language without integer division. In JS use (l + r) >> 1 (and watch the sign for negative ranges — shift rounds toward −∞, which is actually what you want, but be deliberate).
• Assuming it deletes. A plain Li Chao tree cannot remove a line; it is smeared across many nodes. If you need deletion, you need the persistent or offline-segment-on-time variant, not a "remove" method.