guest@cp-base:~/home/dp$
templates/convex-hull-trick.cpp
compilable
$cat templates/convex-hull-trick

Convex Hull Trick (Li Chao Tree)

Dynamic line container with O(log C) insert and min query using Li Chao segment tree.

[Dynamic Programming]|
Jul 9, 2026
|explanatory_notes.md|
#convex-hull-trick#cht#li-chao#line-container#optimization
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Line {
    ll m, c;
    Line(ll m = 0, ll c = LLONG_MAX) : m(m), c(c) {}
    ll eval(ll x) { return m * x + c; }
};

struct LiChao {
    struct Node {
        Line line;
        Node *L, *R;
        Node(Line l = Line()) : line(l), L(nullptr), R(nullptr) {}
    };

    Node* root;
    ll lo, hi;

    LiChao(ll lo, ll hi) : lo(lo), hi(hi), root(new Node()) {}

    void addLine(Line nw) { addLine(root, lo, hi, nw); }

    ll query(ll x) { return query(root, lo, hi, x); }

private:
    void addLine(Node* nd, ll l, ll r, Line nw) {
        ll mid = l + (r - l) / 2;
        bool lBetter = nw.eval(l) < nd->line.eval(l);
        bool mBetter = nw.eval(mid) < nd->line.eval(mid);
        if (mBetter) swap(nd->line, nw);
        if (l == r) return;
        if (lBetter != mBetter) {
            if (!nd->L) nd->L = new Node();
            addLine(nd->L, l, mid, nw);
        } else {
            if (!nd->R) nd->R = new Node();
            addLine(nd->R, mid + 1, r, nw);
        }
    }

    ll query(Node* nd, ll l, ll r, ll x) {
        if (!nd) return LLONG_MAX;
        ll res = nd->line.eval(x);
        if (l == r) return res;
        ll mid = l + (r - l) / 2;
        if (x <= mid) return min(res, query(nd->L, l, mid, x));
        return min(res, query(nd->R, mid + 1, r, x));
    }
};
51 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

Convex Hull Trick — Li Chao Tree

Dynamically maintains a set of lines y=mx+cy = mx + c and answers minimum queries at any xx in a bounded range [L,R][L, R].

How It Works

  • Each segment tree node over [l,r][l, r] stores the line that is best at the midpoint

  • Insert: compare new line vs stored line at mid. If new is better, swap. Push the worse line into whichever child it might still win in

  • Query: evaluate stored line at xx, recurse into child containing xx, return minimum along the path

    • Advantages over Classic CHT

  • Arbitrary insertion order (no sorted slopes needed)

  • Interleaved queries and insertions

  • Dynamic node allocation — memory proportional to actual usage

    • When to Use

  • DP optimization where transitions are linear functions

  • Lines inserted online with arbitrary slopes

  • For max queries: negate slopes and intercepts

    • Notes

  • Classic deque-based CHT is O(1)O(1) amortized when slopes AND queries are monotonic

  • Li Chao is more general but O(log⁡C)O(\log C) per operation

    • Complexity

  • Insert / Query — O(log⁡C)O(\log C) where C=R−LC = R - L

  • Space — O(nlog⁡C)O(n \log C)