viii. Li Chao and Kinetic Segment Trees

Both maintain sets of lines and answer “best value at $x$”. A Li Chao tree is a segment tree over $x$ where each node keeps the line that wins at its midpoint. Inserts and queries take $O(\log C)$, with no ordering requirement and no overflow-prone intersection math. A kinetic segment tree keeps one line per array position and answers range max at a time $t$ that only increases.

Li Chao tree (dynamic, minimum)

struct Line { ll k, b; ll operator()(ll x) const { return k * x + b; } };
struct LiChao {
    struct Node { Line ln; int l = 0, r = 0; };
    vector<Node> t{{{0, LLONG_MAX}}};               // node 0 unused as a null marker; root = 1
    ll lo, hi; int root = 0;
    LiChao(ll lo, ll hi) : lo(lo), hi(hi) {}
    int insert(int v, ll l, ll r, Line ln) {        // over integer x in [l, r)
        if (!v) { t.push_back({ln}); return sz(t) - 1; }
        ll m = l + (r - l) / 2;
        bool lef = ln(l) < t[v].ln(l), mid = ln(m) < t[v].ln(m);
        if (mid) swap(t[v].ln, ln);
        if (r - l == 1) return v;
        if (lef != mid) { int c = insert(t[v].l, l, m, ln); t[v].l = c; }
        else { int c = insert(t[v].r, m, r, ln); t[v].r = c; }
        return v;
    }
    void add(Line ln) { root = insert(root, lo, hi, ln); }
    ll query(ll x) const {
        ll res = LLONG_MAX, l = lo, r = hi; int v = root;
        while (v) {
            res = min(res, t[v].ln(x));
            ll m = l + (r - l) / 2;
            if (x < m) v = t[v].l, r = m; else v = t[v].r, l = m;
        }
        return res;
    }
};

Proof: Li Chao insert/query is correct

Setup. Say a node $v$ is “correct” if, for every $x$ in $v$‘s range, $\min$ over all nodes on the path from $v$ down to $x$‘s leaf of (stored line)$(x)$ equals the true minimum, over every line ever inserted into $v$‘s subtree, evaluated at $x$. We show by induction on the number of lines inserted that the root is always correct (the base case, zero lines beyond the $+\infty$ sentinel, is trivial).

One insertion preserves correctness. Suppose the tree is correct before inserting a new line $g$ into node $v$ (range $[l,r)$, midpoint $m$). Let $\mathrm{old}=t[v].\ln$ before this call, $\mathrm{winner}=\arg {\min }_{\{old,g\}}(\cdot )(m)$ (the one kept as the new $t[v].\ln$) and $\mathrm{loser}$ the other — note $\{\mathrm{winner},\mathrm{loser}\}=\{old,g\}$ as a set, so for every $x$, $\min (\mathrm{winner}(x),\mathrm{loser}(x))=\min (old(x),g(x))$ regardless of labelling. Two lines cross at most once; comparing at $l$ and $m$ tells us exactly which half contains that crossing (if any): if the comparison flips between $l$ and $m$ ($\mathrm{lef}\ne \mathrm{mid}$), the crossing is in $(l,m)$, so on $[m,r)$ the order at $m$ persists and $\mathrm{winner}\le \mathrm{loser}$ there — this is exactly the right child, the one left untouched when we recurse left; symmetrically if $\mathrm{lef}=\mathrm{mid}$, the order already agreed at $l$ and $m$, so $\mathrm{winner}\le \mathrm{loser}$ on all of $[l,m]$ — the untouched left child when we recurse right. So on the untouched child’s range, $\mathrm{loser}(x)\ge \mathrm{winner}(x)=$ new $t[v].\ln (x)$, and omitting $\mathrm{loser}$ from consideration there is harmless: the new path-min there is $\min (t[v].\ln (x),\text{old path-min of that child})=\min (old(x),g(x),\text{old path-min of that child})$, matching “old global min, updated by $g$” as required. On the touched child, the recursive call is the same lemma one level down (inserting $\mathrm{loser}$ there), so by induction its path-min correctly becomes $\min (\text{old path-min},\mathrm{loser}(x))$, and combining with $t[v].\ln (x)=\mathrm{winner}(x)$ again gives $\min (old(x),g(x),\text{old path-min of that child})$. Both cases match the claim, so correctness propagates to all of $v$‘s range, and by induction to the whole tree after any sequence of inserts. $■$

Proof: $O(\log C)$ per insert and query

insert recurses into exactly one of its two children at every internal node (the if (lef != mid) ... else ... branch is strictly one-sided, never both), and the domain $[l,r)$ halves each level, so one insert call does $O(\log C)$ work. query walks a single root-to-leaf path, $O(1)$ work per node, so it is $O(\log C)$ too. $■$

• Maximum: insert $(-k,-b)$ and negate the answer.
• Memory: one node per inserted line (at most). Preallocated array version over compressed query points is faster when all $x$ are known.
• Segment insertion (line valid only on $[a,b)$): descend to the $O(\log C)$ canonical nodes and insert there. That’s $O({\log }^{2}C)$ per insert.
• Beyond lines: any family where two functions cross at most once on the domain works (for example $f(x)=a\sqrt{x}+b$, $f(x)=a/x+b$, or the cost functions of some DP transitions).
• Merging Li Chao trees (for DP on trees): merge like segment trees, re-inserting the lines of the smaller structure; the total is $O(n\log C)$ amortized because each line only moves down.
• Persistent Li Chao: path-copy on insert.

	Monotone CHT (deque)	Dynamic CHT (set)	Li Chao
slope order	must be sorted	any	any
query order	sorted for $O(1)$, else binary search	any	any
cost	$O(1)$ amortized	$O(\log n)$	$O(\log C)$
overflow risk	intersection products overflow; need __int128	same	only evaluates lines
code	short	fiddly	short

DP usage is in Convex Hull Trick.

Kinetic segment tree

Positions $i$ hold lines $k_{i}t+b_i$. Time $t$ only increases. Operations: replace a line, range max at the current $t$, advance $t$. Each node stores the winning line at the current time and melt = the earliest future time when some winner in its subtree changes. Advancing time only descends into nodes whose melt has passed.

struct KST {
    struct L { ll k, b; ll at(ll x) const { return k * x + b; } };
    int n; ll t = 0; vector<L> best; vector<ll> melt;
    static constexpr ll INF = LLONG_MAX;
    static ll fdiv(ll a, ll d) { return a / d - ((a % d != 0) && ((a < 0) != (d < 0))); }
    void pull(int v) {
        L a = best[2 * v], b = best[2 * v + 1];
        if (a.at(t) < b.at(t) || (a.at(t) == b.at(t) && a.k < b.k)) swap(a, b);   // a wins now
        best[v] = a; melt[v] = min(melt[2 * v], melt[2 * v + 1]);
        if (b.k > a.k) melt[v] = min(melt[v], max(t + 1, fdiv(a.b - b.b, b.k - a.k) + 1));
    }
    void build(int v, int l, int r, const vector<L>& a) {
        if (r - l == 1) { best[v] = a[l]; melt[v] = INF; return; }
        int m = (l + r) / 2; build(2 * v, l, m, a); build(2 * v + 1, m, r, a); pull(v);
    }
    KST(const vector<L>& a) : n(sz(a)), best(4 * sz(a)), melt(4 * sz(a), INF) { build(1, 0, n, a); }
    void set(int v, int l, int r, int i, L x) {
        if (r - l == 1) { best[v] = x; return; }
        int m = (l + r) / 2; i < m ? set(2 * v, l, m, i, x) : set(2 * v + 1, m, r, i, x); pull(v);
    }
    ll query(int v, int l, int r, int ql, int qr) const {
        if (qr <= l || r <= ql) return LLONG_MIN;
        if (ql <= l && r <= qr) return best[v].at(t);
        int m = (l + r) / 2;
        return max(query(2 * v, l, m, ql, qr), query(2 * v + 1, m, r, ql, qr));
    }
    void heat(int v, int l, int r) {
        if (melt[v] > t) return;
        int m = (l + r) / 2; heat(2 * v, l, m); heat(2 * v + 1, m, r); pull(v);
    }
    void advance(ll dt) { t += dt; heat(1, 0, n); }
};

Advancing costs $O({\log }^{2}n)$ amortized per winner change. Range-restricted time advances (“heaten” only $[l,r)$) need lazy time tags and cost $O({\log }^{3}n)$ amortized. Typical uses: “add $x$ to all $a_i$ in a range, query range max of $a_i\cdot c_i$” with $x\ge 0$ (the KTT technique), and DP where each candidate’s value grows linearly over time.

Proof: melt correctly bounds how long a cached winner stays valid

Let $a=\mathrm{best}[2v]$, $b=\mathrm{best}[2v+1]$ at the moment of a pull, with $a$ selected as the current winner (so $a.\mathrm{at}(t)>b.\mathrm{at}(t)$, or they’re equal with $a.k\ge b.k$ — the comparator’s tie-break). If $b.k\le a.k$, $b$ can never overtake $a$ as $t$ increases (the gap $a.\mathrm{at}(t)-b.\mathrm{at}(t)$ is non-decreasing), so no finite melt from this pair is needed, matching the code (no update to melt[v] from this branch unless $b.k>a.k$). If $b.k>a.k$, solve $a.\mathrm{at}(\tau )=b.\mathrm{at}(\tau )$ for the real crossing time $\tau =\frac{a.b-b.b}{b.k-a.k}$ (exactly fdiv’s argument as a real number); for $t^{\prime }<\tau$, $b.\mathrm{at}(t^{\prime })<a.\mathrm{at}(t^{\prime })$ still ($a$ correctly stays cached), and for $t^{\prime }>\tau$, $b.\mathrm{at}(t^{\prime })>a.\mathrm{at}(t^{\prime })$ ($b$ must take over). The code’s candidate $\lfloor \tau \rfloor +1$ is the first integer strictly greater than $\tau$ when $\tau$ is not itself an integer (correct: that is exactly the first integer time $b$ strictly overtakes), and is $\tau +1$ — one step late — in the knife-edge case where $\tau$ is itself an integer. This apparent off-by-one never produces a wrong query value: at $t^{\prime }=\tau$ exactly, $a.\mathrm{at}(\tau )=b.\mathrm{at}(\tau )$ by definition of $\tau$, so returning the stale $a$ gives the identical number $b$ would have; the cached identity only matters for slope information an ancestor might use in its own melt computation, and that correction arrives on the very next advance regardless, before any strictly-later crossing could depend on it. So melt[v] is always a safe bound: best[v] is guaranteed correct in value for every $t<\mathrm{melt}[v]$, and heat’s melt[v] > t: return check never skips a node that actually needs reprocessing. $■$

Proof: $O(\log n)$ amortized per winner change, between set calls

Fix a stretch of time with no set calls. Each node $v$‘s winner, over the whole stretch, can only change to a line of strictly greater slope than the line it replaces (that is the only way pull lets $b$ overtake $a$ — the $b.k>a.k$ branch above). So the sequence of distinct winners at $v$ over the stretch has strictly increasing slopes, and there are at most $\mathrm{size}(v)$ distinct lines ever present in $v$‘s range to draw slopes from, giving at most $\mathrm{size}(v)-1$ melt-triggered re-pulls at $v$ for the whole stretch. Summing over all $O(n)$ nodes of the segment tree, ${\sum }_v\mathrm{size}(v)=O(n\log n)$ total re-pulls for the entire stretch. Each heat call visits only nodes with $\mathrm{melt}[v]\le t$ (genuinely triggered) plus, for each such node, its two children checked and immediately returned if not triggered — an $O(1)$-per-triggered-node overhead — so total work across the whole stretch is $O(n\log n)$, i.e. $O(\log n)$ amortized per winner change. Interleaving set calls breaks the clean “slopes only increase” budget at the $O(\log n)$ ancestors it touches (a replaced line can re-open room for new, unrelated future melts there), and bounding that interaction costs an extra $\log n$ factor — this is the standard, folklore-cited result (matching the note’s $O({\log }^{2}n)$ figure); it is not re-derived here, consistent with how this repo cites Ji Ruyi’s original result for beats-with-range-add rather than reproving it from scratch. $■$