Li Chao Tree

A Li Chao tree is a segment tree over the x-coordinate space. Each node stores the line that dominates at the midpoint of its range, so you can add a line and query the maximum (or minimum) at any $x$ in $O(\log C)$ time—without the monotonicity requirements that make the Convex Hull Trick so demanding.

Difficulty: [Advanced]Prerequisites: Segment Tree, DP—Convex Hull TrickCF Rating Range: 1900–2300+

---

Why Not Just Use CHT?

The classical Convex Hull Trick maintains a sorted envelope of lines and answers queries by binary search or pointer walking. It is blazing fast—$O(1)$ amortized with sorted queries. But it only works when the input is polite:

• Sorted slopes for the deque-based version.
• Sorted query points for the pointer-walking version.
• Online queries in arbitrary order? You need a full-blown dynamic CHT (e.g., std::set of lines), which is fiddly and slow in practice.

Li Chao tree sidesteps all of this. Queries and insertions arrive in any order, and it simply works.

The tradeoff: Li Chao tree requires a fixed coordinate range $[0,C)$, giving $O(\log C)$ per operation instead of $O(\log n)$. For typical contest bounds ($C\le {10}^6$), $\log C\approx 20$—perfectly fine.

How It Works

Picture a segment tree laid over the x-axis range $[0,C)$. Each node covers an interval $[lo,hi)$ and holds one line—the dominant line, meaning the one that achieves the best value at the midpoint $mid=(lo+hi)/2$.

When you insert a new line into a node, the logic has three cases:

  Node covers [lo, hi), midpoint = mid
  "old" = line currently stored, "new" = line being inserted

  1. Ensure new(mid) >= old(mid)  (swap if not)
     Now "new" dominates at the midpoint -> store it here.
  2. If new(lo) >= old(lo):  old can't beat new anywhere in [lo, mid]
     -> recurse into RIGHT child with old  (old might still win on the right)
  3. Else:  old beats new at lo
     -> recurse into LEFT child with old

Each insertion recurses into at most one child—$O(\log C)$.

Querying at point $x$: walk from root to the leaf containing $x$, collecting the line stored at every node visited. Return the best value among them—$O(\log C)$.

Insertion Trace

Coordinate range $[0,8)$, inserting lines $L_1:y=2x+1$, $L_2:y=-x+10$, $L_3:y=x+4$ (maximizing $y$):

  After inserting L1 (y=2x+1):
  [0,8) stores L1

  After inserting L2 (y=-x+10):
  mid=4: L2(4)=6, L1(4)=9  -> L1 stays dominant at mid
         L2(0)=10 > L1(0)=1 -> L2 wins on left
  [0,8) stores L1,  [0,4) stores L2

  After inserting L3 (y=x+4):
  mid=4: L3(4)=8, L1(4)=9  -> L1 stays
         L3(0)=4 < L1(0)=1? No, 4>1 -> L3 wins left
  Recurse into [0,4):
    mid=2: L3(2)=6, L2(2)=8 -> L2 stays
           L3(0)=4 < L2(0)=10 -> L3 goes right
  [0,4) stores L2,  [2,4) stores L3

  Final tree:
       [0,8): L1 (y=2x+1)
      /                   \
  [0,4): L2 (-x+10)    [4,8): empty
   /          \
 [0,2):     [2,4): L3 (x+4)
  empty

Query at $x=1$: visit $[0,8)\to [0,4)\to [0,2)$. Evaluate: $L_1(1)=3$, $L_2(1)=9$, nothing at the leaf. Answer: $9$.

Implementation

#include <bits/stdc++.h>
using namespace std;

struct Line {
    long long m = 0, b = -1e18; // y = m*x + b
    long long eval(long long x) { return m * x + b; }
};

const int MAXC = 1e6 + 1;
Line tree[4 * MAXC];

void addLine(Line nw, int v = 1, int lo = 0, int hi = MAXC) {
    int mid = (lo + hi) / 2;
    bool leftBetter = nw.eval(lo) > tree[v].eval(lo);
    bool midBetter  = nw.eval(mid) > tree[v].eval(mid);
    if (midBetter) swap(tree[v], nw);
    if (hi - lo == 1) return;
    if (leftBetter != midBetter)
        addLine(nw, 2*v, lo, mid);
    else
        addLine(nw, 2*v+1, mid, hi);
}

long long query(int x, int v = 1, int lo = 0, int hi = MAXC) {
    long long res = tree[v].eval(x);
    if (hi - lo == 1) return res;
    int mid = (lo + hi) / 2;
    if (x < mid) return max(res, query(x, 2*v, lo, mid));
    else         return max(res, query(x, 2*v+1, mid, hi));
}

Change > to < and max to min throughout for minimum queries.

Memory note: $4\cdot C$ nodes. For $C={10}^6$ that is 16 M Line structs (~128 MB with long long). If memory is tight, use a dynamic (pointer-based) variant or coordinate-compress the query points.

Li Chao vs. CHT — When to Use Which

Scenario	Best tool
Slopes monotone, queries monotone	Deque CHT—$O(n)$ total
Slopes monotone, queries arbitrary	Li Chao or CHT with binary search
Slopes arbitrary, queries arbitrary	Li Chao tree
Queries online, no ordering guarantees	Li Chao tree
Need $O(\log n)$ not $O(\log C)$	Dynamic CHT (std::set of lines)

Adding Line Segments

Li Chao tree extends naturally to line segments (valid only on $[x_1,x_2]$). Instead of inserting into the root, insert into the $O(\log C)$ nodes that cover $[x_1,x_2]$. Total cost: $O({\log }^{2}C)$ per segment.

Pitfalls

• Fixed coordinate range. The array is allocated for $[0,C)$ at compile time—or you must use dynamic allocation. Check the problem's constraint on $x$ values before coding.
• Integer overflow. $m\cdot x+b$ with $m,x\sim {10}^6$ and $b\sim {10}^{12}$ overflows long long. Use __int128 or restructure the formula.
• Min vs. max confusion. When switching between minimize and maximize variants, every comparison operator flips. Double-check them all.
• Uninitialized default line. The sentinel line must be the worst possible value—$b=-\mathrm{\infty }$ for max queries, $b=+\mathrm{\infty }$ for min. A zero-initialized Line silently poisons every query.

Practice Problems

#	Problem	Difficulty	Notes
1	CF 932F -- Escape Through Leaf	2200	Tree DP + Li Chao tree on subtree merge
2	CF 678F -- Lena and Queries	2500	Offline + Li Chao per centroid
3	CF 1083E -- The Fair Nut and Rectangles	2400	Classic CHT/Li Chao DP
4	CSES -- Line Container	—	Direct "add line, query max"

Further Reading

• cp-algorithms: Li Chao Tree
• DP—Convex Hull Trick—the deque-based alternative
• Competitive Programmer's Handbook §15.5 (Convex Hull Trick overview)