Li Chao Tree
A segment-tree-style structure for maintaining a dynamic lower envelope of lines under point queries.
Li Chao Tree
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Li Chao tree is the line-container I use when a DP or query problem reduces to \[ \min_j (m_j x + b_j) \] or \(\max\) instead, but the pleasant monotonicity assumptions behind the deque version of the convex hull trick are missing. It gives a robust contest implementation for arbitrary line insertion order and arbitrary query order.
Problem-Driven Motivation
A very common contest transition looks like this: \[ dp[i] = cost(i) + \min_{j < i}\bigl(A_j \cdot X_i + B_j\bigr). \]
The naive implementation tries every previous \(j\), so it is \(O(n^2)\). That dies immediately when \(n\) is \(2 \cdot 10^5\).
If both slopes \(A_j\) and query points \(X_i\) are monotone, a deque-based convex hull trick is enough. But many real problems break one or both assumptions:
the \(x\)-coordinates come in arbitrary order,
the states that generate lines are not sorted by slope,
queries and insertions are interleaved online.
That is the point where Li Chao tree becomes the safe fallback.
Recognition Pattern
Strong signals for Li Chao tree are:
a recurrence or query of the form ``minimum / maximum over lines evaluated at one \(x\),''
arbitrary query order, arbitrary line insertion order, or both,
a value domain that can be bounded in advance or compressed offline,
the monotone CHT looks almost right but one monotonicity assumption is false.
If the compared functions are not lines, or if two functions can intersect many times, Li Chao is probably the wrong tool.
Derivation
Suppose every candidate state contributes one line \(y = mx + b\), and every new state asks for the best value at one query point \(x\). The remaining task is:
Maintain the lower envelope of inserted lines and query it at points.
The Li Chao idea is to put a segment-tree structure on the \(x\)-domain. Each node owns an interval \([l,r]\) and stores one currently best candidate line for that interval.
The crucial observation is that two lines intersect at most once. So if we compare two lines on an interval and one of them is better at the midpoint, then the worse line can only still matter on one side of that midpoint.
That leads to the insertion rule:
keep the better line at the midpoint in the current node,
recurse with the other line only into the side where it could still win.
This is why Li Chao stays logarithmic: every insertion follows only one path downward after each comparison.
Worked Problem
Problem.
Given arbitrary integers \(x_0, x_1, \dots, x_{n-1}\), compute \[ dp[0] = 0,\qquad dp[i] = x_i^2 + C + \min_{0 \le j < i}\bigl(dp[j] + x_j^2 - 2x_i x_j\bigr). \]
Why the naive solution fails.
Trying all \(j < i\) for every \(i\) is \(O(n^2)\). For \(n = 2 \cdot 10^5\), that is far too slow.
How the formula becomes lines.
For fixed \(j\), the part depending on \(x_i\) is \[ (-2x_j)\cdot x_i + (dp[j] + x_j^2). \]
So each previous state contributes a line with:
slope \(m_j = -2x_j\),
intercept \(b_j = dp[j] + x_j^2\),
query point \(x = x_i\).
Then \[ dp[i] = x_i^2 + C + \min_j (m_j x_i + b_j). \]
Why Li Chao, not monotone CHT.
The \(x_i\) values may arrive in any order, so front-popping from a deque is illegal. The slopes \(-2x_j\) are also unsorted if the \(x_j\) values are unsorted. That rules out the monotone hull but not Li Chao.
Final algorithm.
bound the queried \(x_i\) values by \([\min x_i, \max x_i]\),
insert the line for state \(0\),
for \(i = 1 \ldots n-1\), query the best line at \(x_i\), compute \(dp[i]\), then insert the line generated by state \(i\).
Implementation Reasoning
The invariant I want from the implementation is:
For every coordinate \(x\), at least one line on the root-to-leaf path for \(x\) is optimal among all inserted lines.
That is why queries simply evaluate every stored line on that path and take the best.
Practical implementation details:
use
__int128for comparisons, because \(mx+b\) can overflow 64-bit during intermediate arithmetic,handle equal slopes carefully: for a minimum hull, keep only the smaller intercept,
if the domain is sparse but all query points are known offline, compress the coordinates and build Li Chao over compressed positions.
The code keeps a dynamic-node tree because it is memory-friendly when the coordinate domain is large but only a small part of it is touched.
Correctness Intuition
Inside one node interval, the kept line is the one that wins at the midpoint. Since two lines intersect at most once, the line that loses at the midpoint can only still become relevant on one side. Recursing only into that side preserves all possible future optima.
Therefore, after every insertion, the optimal line for any queried \(x\) still survives somewhere on the path from the root to the leaf containing \(x\).
Complexity Analysis
If the domain spans \(X\) discrete coordinates:
insert one line: \(O(\log X)\),
query one point: \(O(\log X)\),
memory: \(O(\text{insertions} \cdot \log X)\) in the dynamic-node version.
Common Pitfalls
Forgetting that Li Chao only supports point queries unless you implement the segment-restricted variant.
Choosing a coordinate range that misses some query points.
Using it on functions that are not single-intersection objects.
Flipping the inequalities incorrectly when switching between minimum and maximum.
Assuming 64-bit multiplication is safe during comparisons.
Variants and Failure Modes
If slopes and query points are both monotone, deque CHT is simpler and faster.
If a line is active only on a subsegment of the domain, use the segment-restricted Li Chao variant.
If the domain is continuous and precision matters, use a floating version carefully.
If the compared functions intersect multiple times, Li Chao is no longer justified by the midpoint argument.
Practice Problems
DP with arbitrary-order quadratic transitions.
Dynamic minimum-cost linear functions evaluated at points.
Segment-restricted linear cost updates after offline event expansion.
References
Code
Contest-ready reference implementation for the idea explained above.
#include <bits/stdc++.h>
using namespace std;
struct LiChaoTree {
struct Line {
long long m;
long long b;
long long eval(long long x) const {
return m * x + b;
}
long double eval_ld(long long x) const {
return (long double)m * x + b;
}
};
struct Node {
Line line{0, 0};
bool has_line = false;
Node* left = nullptr;
Node* right = nullptr;
};
static constexpr long long INF = (1LL << 62);
long long lo;
long long hi;
Node* root = nullptr;
LiChaoTree(long long lo, long long hi) : lo(lo), hi(hi) {}
void add_line(long long m, long long b) {
add_line(root, lo, hi, Line{m, b});
}
long long query(long long x) const {
return query_value(root, lo, hi, x);
}
private:
void add_line(Node*& node, long long l, long long r, Line nw) {
if (!node) node = new Node();
if (!node->has_line) {
node->line = nw;
node->has_line = true;
return;
}
if (node->line.m == nw.m) {
if (nw.b < node->line.b) node->line = nw;
return;
}
long long mid = l + (r - l) / 2;
bool left_better = nw.eval_ld(l) < node->line.eval_ld(l);
bool mid_better = nw.eval_ld(mid) < node->line.eval_ld(mid);
if (mid_better) swap(node->line, nw);
if (l == r) return;
if (left_better != mid_better) {
add_line(node->left, l, mid, nw);
} else {
add_line(node->right, mid + 1, r, nw);
}
}
long long query_value(Node* node, long long l, long long r, long long x) const {
if (!node) return INF;
long long answer = node->has_line ? node->line.eval(x) : INF;
if (l == r) return answer;
long long mid = l + (r - l) / 2;
if (x <= mid) return min(answer, query_value(node->left, l, mid, x));
return min(answer, query_value(node->right, mid + 1, r, x));
}
};
// Example application:
// dp[0] = 0
// dp[i] = x[i]^2 + fixed_cost + min_{j < i}(dp[j] + x[j]^2 - 2*x[i]*x[j])
vector<long long> solve_quadratic_dp_arbitrary_x(const vector<long long>& x, long long fixed_cost) {
int n = (int)x.size();
if (n == 0) return {};
long long min_x = *min_element(x.begin(), x.end());
long long max_x = *max_element(x.begin(), x.end());
LiChaoTree lichao(min_x, max_x);
vector<long long> dp(n, 0);
lichao.add_line(-2 * x[0], x[0] * x[0]);
for (int i = 1; i < n; ++i) {
long long best = lichao.query(x[i]);
dp[i] = x[i] * x[i] + fixed_cost + best;
lichao.add_line(-2 * x[i], dp[i] + x[i] * x[i]);
}
return dp;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.