🗂️Data StructureAdvanced

Li Chao Tree

Key Points

  • •
    A Li Chao tree maintains a set of lines y = m x + b and answers minimum (or maximum) value queries at a given x in O(log C) time, where C is the numeric range of x.
  • •
    Unlike the classic Convex Hull Trick, lines can be inserted in any order without requiring monotone slopes or queries.
  • •
    Each node represents an x-interval and stores the line that is best at the interval's midpoint; worse lines are pushed to the left or right child depending on where they might still win.
  • •
    Insertion and query costs depend on the height of the implicit segment tree built over the x-domain, which is approximately log2(R - L) for domain [L, R).
  • •
    The structure can be made memory-efficient by creating nodes lazily, leading to O(N log C) nodes after N insertions.
  • •
    You can handle maximum queries by negating slopes and intercepts (reduce max to min), or by flipping the comparison.
  • •
    A segment variant supports inserting a line active only on [l, r), with O((log C)^2) insertion and O(log C) query.
  • •
    Careful handling of integer overflow, domain bounds, and equal-sloped lines is essential for correctness.

Prerequisites

  • →Binary search and midpoints — Li Chao descent uses midpoint splitting akin to binary search, and safe midpoint computation avoids overflow.
  • →Segment tree basics — The Li Chao tree is an implicit segment tree over the x-domain; understanding interval splitting and recursion helps.
  • →Asymptotic complexity (Big-O) — To reason about O(log C) per operation and O(N log C) node counts.
  • →Integer arithmetic and overflow — Evaluating m*x + b safely requires awareness of 64-bit limits and use of 128-bit intermediates.
  • →Floating-point precision (optional) — For real-valued domains, numerical stability in comparisons matters.
  • →Convex Hull Trick (optional) — Provides context and contrasts: when monotonicity holds, simpler and faster structures may apply.

Detailed Explanation

Tap terms for definitions

01Overview

Imagine you keep adding straight lines on a plane and, for any x you pick, you want to know the smallest y among all those lines at that x. The Li Chao tree is a specialized data structure that solves exactly this problem efficiently, even if you add lines in any order and query in any order. It structures the x-axis into intervals like a segment tree and stores, at each node, the line that is currently best at the node's midpoint. When a new line is inserted, it is compared with the stored line at key points; the worse one is routed to the child interval where it could still win later. Because a difference of two lines is itself a line, the set of x where one line beats another forms a single interval, making this recursive routing correct and efficient. Hook: Think of choosing the cheapest ride-hailing service at any time, where each company offers a price line price(t) = base + rate * t. If many companies compete, the minimum at a particular time t is the best choice. Concept: The Li Chao tree lets you insert any number of such linear cost functions and ask “what is the cheapest at time t?” in logarithmic time. Example: Suppose you have lines y = 2x + 3 and y = -x + 10. At x = 4, the first is 11, the second is 6, so the minimum is 6; the tree returns that answer quickly, regardless of insertion order.

02Intuition & Analogies

Hook: Picture a long road marked with mileposts from L to R. At each milepost x, multiple billboards (lines) advertise a price y for a service that depends linearly on x. You want a fast way to know the cheapest price at any milepost. Concept: Split the road recursively into halves: [L, M) and [M, R), where M is the midpoint. At each split, keep the billboard that is cheapest exactly at M. Because billboards are straight lines, if billboard A is cheaper than B at M, it will be cheaper near M, but B might still win far to the left or right; so we pass B down to the side where it could still be better. Example: Compare line A and line B at the midpoint M. If A(M) ≤ B(M), store A at this node and try to fit B into the child interval where B could beat A (determined by looking at endpoints or midpoint again). If instead B(M) < A(M), swap roles. When you query at some x, you walk down the path determined by x and collect the minimum among the lines you encounter. Because each recursive step halves the interval, both insertion and query take logarithmic time in the range width. This “keep the best-at-mid, push the rest” rule works since the difference of two lines g(x) = (m1 − m2)x + (b1 − b2) changes sign at most once. So if B loses at mid but wins somewhere, it must win entirely on one side of mid, letting us discard the other side. The tree is implicit: children are created only when necessary, saving memory.

03Formal Definition

We maintain a set of affine functions (lines) L = {(x) = x + }. For a fixed domain [L, R) on the x-axis (typically integers or reals within bounded range), the Li Chao tree is an implicit segment tree whose node v corresponds to an interval . Each node stores one line that is pointwise minimal at the midpoint of among all lines that were ever routed to node v. To insert a line , we recursively compare and at key points (e.g., left endpoint and midpoint). If () < (), swap them so that remains the line minimal at . Because − is linear, the set of x where beats is an interval; we recurse only into the child interval where this may occur. A query at x descends the unique path determined by x and returns over all lines stored along that path. Time complexity per insertion or query is O(log C), where − L is the numeric span of the domain, since the recursion depth is bounded by the tree height. If nodes are created lazily, the total number of nodes after N insertions is O(N log C) in the worst case. A segment variant supports adding lines valid only on subranges; it splits the update across O(log C) nodes and performs a local Li Chao insertion at each, yielding O((log C)^2) insertion time.

04When to Use

Use a Li Chao tree when you need to maintain a dynamic set of lines (or line segments) and answer min/max queries at arbitrary x without restrictions on slope order or query order. It excels in online scenarios: you can add a line and immediately query, then add another line, and so on. Typical applications include dynamic programming of the form dp[i] = min_j (m_j x_i + b_j), where x_i is known per i but j arrives in arbitrary order. It is also effective for problems where costs are linear in a parameter, scheduling with linear penalties, or geometry problems requiring envelope queries. Specific use cases:

  • Online Convex Hull Trick without monotonicity (e.g., Codeforces problems with mixed insert/query operations).
  • DP optimizations when x_i are not monotone and slopes m_j are not sorted.
  • Handling maximum queries by negating values, or by switching the comparator.
  • Segment-constrained lines: when a line applies only on [l, r), use the segment Li Chao variant. Avoid it when your domain is unbounded and cannot be safely capped, when you can exploit stronger monotonicity for faster structures (like deque-based CHT with O(1) amortized queries), or when precision issues with floating point dominate; in those cases, alternative methods may be preferable.

⚠️Common Mistakes

  1. Wrong domain bounds: The tree assumes all queries x lie within a fixed [L, R). If a query is outside, results are undefined. Always pick conservative bounds or redesign to clamp/expand carefully.
  2. Integer overflow: Evaluating y = m x + b with 64-bit integers can overflow if |m|, |x|, |b| are large. Use 128-bit intermediates (e.g., __int128 in C++) and choose INF sentinels consistent with your problem constraints.
  3. Midpoint handling: Using mid = (l + r)/2 can overflow if l and r are near 10^{18}. Use mid = l + (r - l)/2, and be consistent with [L, R) vs [L, R] intervals.
  4. Equal slopes: If two lines have the same slope, keep only the one with the better intercept for your objective; failing to handle this can cause infinite recursion or incorrect results.
  5. Max vs min confusion: The standard implementation is for minima. For maxima, either negate slopes and intercepts or invert comparisons. Mixing the two mid-function variants leads to subtle bugs.
  6. Precision with doubles: On real-valued domains, floating-point comparisons at midpoints can be unstable; prefer long double and consider small epsilons for comparisons. If your input is integral and bounded, prefer integer Li Chao.
  7. Segment variant pitfalls: Inserting a line active only on [l, r) requires the segment Li Chao approach; naively inserting globally and trying to invalidate outside the segment will not work.
  8. Memory assumptions: A lazy implicit implementation still creates O(N log C) nodes in worst case. Pre-building a full segment tree over huge C is infeasible; always allocate nodes on demand.

Key Formulas

Line Equation

Explanation: Every line stored in the Li Chao tree has a slope m and intercept b. The query asks for the minimum (or maximum) y at a given x among all such lines.

Line Intersection

Explanation: Two lines x + and x + cross at x*. Because the difference is linear, there is at most one crossing, which underpins the Li Chao routing logic.

Lower Envelope

Explanation: Queries compute the value of the lower envelope at x. The tree maintains enough information to evaluate this minimum in O(log C) time.

Operation Complexity

Explanation: Both inserting a line and querying at x traverse a path of length proportional to the tree height, which is logarithmic in the domain span C = R - L.

Node Count (Lazy)

Explanation: With lazy allocation, each of N inserts can create O(log C) nodes along its path, giving an overall node bound of O(N log C).

Segment Variant Cost

Explanation: A line active on [l, r) updates O(log C) segment-tree nodes, and at each node performs a local O(log C) Li Chao insertion.

Overflow-safe Midpoint

Explanation: To avoid overflow when l and r are large, compute the midpoint this way rather than (l + r)/2. This is important for 64-bit integer domains.

Difference of Lines

Explanation: The sign of g(x) determines which line is better at x. Since g(x) is linear, it changes sign at most once, ensuring correctness of per-node decisions.

Complexity Analysis

Let C = R − L denote the numeric span of the x-domain. The Li Chao tree is an implicit balanced binary partition of [L, R) by midpoints; therefore, its height is O(log C). During insertion of a line, at each visited node we compare the new line with the node’s stored line at O(1) points (typically at the left endpoint and the midpoint). We then keep the better-at-midline at the node and recurse with the worse line into at most one child. Thus, an insertion descends at most the tree height, taking O(log C) time. A query at x follows the unique path determined by the binary search-like descent (x < mid goes left; else right), aggregating the minimum across O(log C) nodes. This yields O(log C) query time. Space usage depends on allocation strategy. If the tree is fully materialized, it would require O(C) nodes (impractical for large domains). In practice, nodes are created lazily: each insertion touches O(log C) new nodes in the worst case, so after N insertions the total number of nodes is O(N log C). Each node stores a constant amount of information (one line and two pointers), so memory is linear in the node count. The segment variant, which activates a line only on [l, r), splits the update across O(log C) segment-tree nodes; at each such node it performs a local Li Chao insertion with cost O(log C), leading to O((log C)^2) time per segment insertion while queries remain O(log C). If floating-point arithmetic is used, time complexity is unchanged, but numerical robustness must be considered.

Code Examples

Li Chao Tree (min queries) with 64-bit integers
1#include <bits/stdc++.h>
2using namespace std;
3
4// Li Chao tree for minimum queries on y = m*x + b over integer x in [X_MIN, X_MAX)
5// Uses lazy (implicit) nodes. Evaluations use __int128 to reduce overflow risk.
6
7struct Line {
8    long long m, b; // y = m*x + b
9    Line(long long _m = 0, long long _b = (long long)9e18) : m(_m), b(_b) {}
10    inline long long eval(long long x) const {
11        __int128 val = (__int128)m * (__int128)x + (__int128)b;
12        if (val > (__int128)LLONG_MAX) return LLONG_MAX;
13        if (val < (__int128)LLONG_MIN) return LLONG_MIN;
14        return (long long)val;
15    }
16};
17
18struct Node {
19    Line ln;         // best-at-mid line for this interval
20    Node* left;      // left child
21    Node* right;     // right child
22    Node() : ln(), left(nullptr), right(nullptr) {}
23};
24
25struct LiChaoMin {
26    long long X_MIN, X_MAX; // domain: [X_MIN, X_MAX)
27    Node* root;
28    LiChaoMin(long long L, long long R) : X_MIN(L), X_MAX(R), root(nullptr) {}
29
30    // Insert line y = m*x + b over the full domain
31    void add_line(long long m, long long b) {
32        Line nw(m, b);
33        add_line(nw, root, X_MIN, X_MAX);
34    }
35
36    // Query minimum y at x
37    long long query(long long x) const {
38        return query(x, root, X_MIN, X_MAX);
39    }
40
41private:
42    static void ensure(Node*& n) {
43        if (!n) n = new Node();
44    }
45
46    static void add_line(Line nw, Node*& n, long long l, long long r) {
47        ensure(n);
48        long long mid = l + ((r - l) >> 1);
49
50        // Handle equal slope early to avoid infinite recursion
51        if (n->ln.m == nw.m) {
52            if (nw.b < n->ln.b) n->ln = nw; // keep better intercept for min
53            return;
54        }
55
56        bool left_better = nw.eval(l) < n->ln.eval(l);
57        bool mid_better  = nw.eval(mid) < n->ln.eval(mid);
58
59        if (mid_better) swap(n->ln, nw); // keep best-at-mid at this node
60
61        if (r - l == 1) return; // leaf interval
62
63        if (left_better != mid_better) {
64            add_line(nw, n->left, l, mid);
65        } else {
66            add_line(nw, n->right, mid, r);
67        }
68    }
69
70    static long long query(long long x, Node* n, long long l, long long r) {
71        if (!n) return (long long)9e18;
72        long long res = n->ln.eval(x);
73        if (r - l == 1) return res;
74        long long mid = l + ((r - l) >> 1);
75        if (x < mid) return min(res, query(x, n->left, l, mid));
76        else         return min(res, query(x, n->right, mid, r));
77    }
78};
79
80int main() {
81    ios::sync_with_stdio(false);
82    cin.tie(nullptr);
83
84    // Domain: x in [-1e6, 1e6)
85    LiChaoMin lichao(-1000000, 1000000);
86
87    // Insert lines
88    lichao.add_line(2, 3);     // y = 2x + 3
89    lichao.add_line(-1, 10);   // y = -x + 10
90    lichao.add_line(0, 5);     // y = 5
91
92    // Sample queries
93    vector<long long> xs = {-2, 0, 4, 10};
94    for (long long x : xs) {
95        long long ans = lichao.query(x);
96        cout << "min at x=" << x << " is " << ans << '\n';
97    }
98
99    return 0;
100}
101

This program builds a Li Chao tree for minimum queries over integer x in a fixed range. It inserts three lines and answers the minimum y for several x. The core idea is storing the line best at the midpoint per node and recursively pushing the other line to the side where it could still win. __int128 is used to mitigate overflow when evaluating m*x + b.

Time: O(log C) per insertion and per query, where C = X_MAX - X_MINSpace: O(N log C) nodes after N insertions (lazy allocation)
Li Chao Tree for maximum queries (double domain) via sign flip
1#include <bits/stdc++.h>
2using namespace std;
3
4// Max-queries implemented by inserting (-m, -b) into a min Li Chao tree
5// and returning -min. Uses long double for better precision on real x.
6
7struct Line {
8    long double m, b;
9    Line(long double _m = 0, long double _b = numeric_limits<long double>::infinity()) : m(_m), b(_b) {}
10    inline long double eval(long double x) const { return m * x + b; }
11};
12
13struct Node {
14    Line ln;
15    Node *left, *right;
16    Node() : ln(), left(nullptr), right(nullptr) {}
17};
18
19struct LiChaoMinLD {
20    long double L, R; // domain [L, R)
21    Node* root;
22    LiChaoMinLD(long double _L, long double _R) : L(_L), R(_R), root(nullptr) {}
23
24    void add_line(long double m, long double b) { add_line(Line(m, b), root, L, R); }
25
26    long double query(long double x) const { return query(x, root, L, R); }
27
28private:
29    static void ensure(Node*& n) { if (!n) n = new Node(); }
30
31    static void add_line(Line nw, Node*& n, long double l, long double r) {
32        ensure(n);
33        long double mid = l + (r - l) / 2.0L;
34        // Equal slopes: keep better intercept
35        if (fabsl(n->ln.m - nw.m) < 1e-18L) { if (nw.b < n->ln.b) n->ln = nw; return; }
36        bool left_better = nw.eval(l) < n->ln.eval(l);
37        bool mid_better  = nw.eval(mid) < n->ln.eval(mid);
38        if (mid_better) swap(n->ln, nw);
39        if (r - l <= 1e-18L) return; // leaf-ish for doubles
40        if (left_better != mid_better) add_line(nw, n->left, l, mid);
41        else                           add_line(nw, n->right, mid, r);
42    }
43
44    static long double query(long double x, Node* n, long double l, long double r) {
45        if (!n) return numeric_limits<long double>::infinity();
46        long double res = n->ln.eval(x);
47        if (r - l <= 1e-18L) return res;
48        long double mid = l + (r - l) / 2.0L;
49        if (x < mid) return min(res, query(x, n->left, l, mid));
50        else         return min(res, query(x, n->right, mid, r));
51    }
52};
53
54int main() {
55    ios::sync_with_stdio(false);
56    cin.tie(nullptr);
57
58    // Max over domain [-1000, 1000)
59    LiChaoMinLD lichao_min(-1000.0L, 1000.0L);
60
61    auto add_max_line = [&](long double m, long double b){
62        // max(m*x + b) == - min( (-m)*x + (-b) )
63        lichao_min.add_line(-m, -b);
64    };
65    auto query_max = [&](long double x){
66        return -lichao_min.query(x);
67    };
68
69    // Insert lines for max envelope
70    add_max_line(1.5L, -2.0L);    // y = 1.5x - 2
71    add_max_line(-0.5L, 5.0L);    // y = -0.5x + 5
72    add_max_line(0.0L, 1.0L);     // y = 1
73
74    for (long double x : { -10.0L, 0.0L, 10.0L }) {
75        cout.setf(std::ios::fixed); cout << setprecision(6);
76        cout << "max at x=" << x << " is " << query_max(x) << '\n';
77    }
78    return 0;
79}
80

This example shows how to support maximum queries by inserting negated lines into a min Li Chao tree and negating query results. It uses long double to reduce floating-point error on real-valued domains.

Time: O(log C) per insertion and query (C = R - L)Space: O(N log C) nodes in the worst case
Segment Li Chao Tree: lines active only on [l, r)
1#include <bits/stdc++.h>
2using namespace std;
3
4// Segment Li Chao: insert a line only active on [ql, qr) (integer domain)
5// Each update visits O(log C) nodes; at a fully-covered node, we perform a local Li Chao insertion.
6
7struct Line {
8    long long m, b;
9    Line(long long _m = 0, long long _b = (long long)9e18) : m(_m), b(_b) {}
10    inline long long eval(long long x) const {
11        __int128 v = (__int128)m * x + b;
12        if (v > (__int128)LLONG_MAX) return LLONG_MAX;
13        if (v < (__int128)LLONG_MIN) return LLONG_MIN;
14        return (long long)v;
15    }
16};
17
18struct Node {
19    Line ln; // best-at-mid for this interval
20    Node *left, *right;
21    Node() : ln(), left(nullptr), right(nullptr) {}
22};
23
24struct SegLiChaoMin {
25    long long L, R; // [L, R)
26    Node* root;
27    SegLiChaoMin(long long _L, long long _R) : L(_L), R(_R), root(nullptr) {}
28
29    // Add line over [ql, qr)
30    void add_segment_line(long long m, long long b, long long ql, long long qr) {
31        ql = max(ql, L); qr = min(qr, R);
32        if (ql >= qr) return;
33        add_segment_line(Line(m, b), root, L, R, ql, qr);
34    }
35
36    long long query(long long x) const { return query(x, root, L, R); }
37
38private:
39    static void ensure(Node*& n) { if (!n) n = new Node(); }
40
41    static void add_line_here(Line nw, Node*& n, long long l, long long r) {
42        ensure(n);
43        long long mid = l + ((r - l) >> 1);
44
45        if (n->ln.m == nw.m) { if (nw.b < n->ln.b) n->ln = nw; return; }
46
47        bool left_better = nw.eval(l) < n->ln.eval(l);
48        bool mid_better  = nw.eval(mid) < n->ln.eval(mid);
49        if (mid_better) swap(n->ln, nw);
50        if (r - l == 1) return;
51        if (left_better != mid_better) add_line_here(nw, n->left, l, mid);
52        else                           add_line_here(nw, n->right, mid, r);
53    }
54
55    static void add_segment_line(Line nw, Node*& n, long long l, long long r, long long ql, long long qr) {
56        if (qr <= l || r <= ql) return; // no overlap
57        ensure(n);
58        if (ql <= l && r <= qr) {
59            add_line_here(nw, n, l, r); // local insertion
60            return;
61        }
62        long long mid = l + ((r - l) >> 1);
63        add_segment_line(nw, n->left, l, mid, ql, qr);
64        add_segment_line(nw, n->right, mid, r, ql, qr);
65    }
66
67    static long long query(long long x, Node* n, long long l, long long r) {
68        if (!n) return (long long)9e18;
69        long long res = n->ln.eval(x);
70        if (r - l == 1) return res;
71        long long mid = l + ((r - l) >> 1);
72        if (x < mid) return min(res, query(x, n->left, l, mid));
73        else         return min(res, query(x, n->right, mid, r));
74    }
75};
76
77int main() {
78    ios::sync_with_stdio(false); cin.tie(nullptr);
79
80    // Domain: [0, 20)
81    SegLiChaoMin lichao(0, 20);
82
83    // Insert y = x over [0, 10)
84    lichao.add_segment_line(1, 0, 0, 10);
85    // Insert y = 20 - x over [10, 20)
86    lichao.add_segment_line(-1, 20, 10, 20);
87    // Insert constant y = 7 over [5, 15)
88    lichao.add_segment_line(0, 7, 5, 15);
89
90    for (int x = 0; x < 20; ++x) {
91        cout << "min at x=" << x << " is " << lichao.query(x) << '\n';
92    }
93    return 0;
94}
95

This program implements the segment Li Chao tree, allowing lines to be active only over subranges. It demonstrates inserting three lines with different active intervals and querying the minimum at each integer x. Each segment insertion touches O(log C) nodes and performs a local Li Chao insertion within those nodes.

Time: O((log C)^2) per segment insertion; O(log C) per querySpace: O(N log C) nodes after N segment insertions (lazy allocation)