Pattern Guide
Convex Hull Trick
"Optimize DP with min/max of linear functions. Maintains a convex hull of lines."
The Convex Hull Trick (CHT) optimizes DP transitions of the form dp[i] = min(dp[j] + b[j]*x[i]) from O(n²) to O(n log n) or O(n) amortized. It works by maintaining a "hull" of linear functions y = mx+b so the optimal line at each query can be found quickly. Essential for "Slope Optimization DP." The Li Chao tree variant handles arbitrary query orders in O(log C) per operation.
16 min readdp problems →
Problems you can solve with this pattern
4 problems · click any to start solving
Li Chao Tree — handles arbitrary query order, O(log C) per op
// Li Chao Tree: handles arbitrary insertions and queries
// Each node stores the "dominant" line for its range's midpoint
class LiChaoTree {
constructor(lo, hi) {
this.lo = lo; this.hi = hi;
this.line = null; this.left = null; this.right = null;
}
// Insert line y = mx + b (minimize)
insert(m, b, lo = this.lo, hi = this.hi, node = this) {
if (!node) return;
const mid = (lo + hi) >> 1;
const newBetter = !node.line || m * mid + b < node.line[0] * mid + node.line[1];
if (newBetter) [m, b, node.line] = [node.line ? node.line[0] : m, node.line ? node.line[1] : b, [m, b]];
if (lo === hi) return;
const leftBetter = !node.line || m * lo + b < node.line[0] * lo + node.line[1];
if (leftBetter) {
if (!node.left) node.left = new LiChaoTree(lo, mid);
this.insert(m, b, lo, mid, node.left);
} else {
if (!node.right) node.right = new LiChaoTree(mid + 1, hi);
this.insert(m, b, mid + 1, hi, node.right);
}
}
query(x, lo = this.lo, hi = this.hi, node = this) {
if (!node) return Infinity;
const mid = (lo + hi) >> 1;
let best = node.line ? node.line[0] * x + node.line[1] : Infinity;
if (x <= mid) best = Math.min(best, this.query(x, lo, mid, node.left));
else best = Math.min(best, this.query(x, mid + 1, hi, node.right));
return best;
}
}
// Monotone CHT (O(n) when queries and slopes are both monotone)
class MonotoneCHT {
constructor() { this.lines = []; } // [slope, intercept]
bad(l1, l2, l3) {
// l2 is never optimal if intersection(l1,l3) is left of intersection(l1,l2)
return (l3[1]-l1[1])*(l1[0]-l2[0]) <= (l2[1]-l1[1])*(l1[0]-l3[0]);
}
addLine(m, b) {
const l = [m, b];
while (this.lines.length >= 2 && this.bad(this.lines.at(-2), this.lines.at(-1), l))
this.lines.pop();
this.lines.push(l);
}
queryMin(x) { // assumes x is non-decreasing
while (this.lines.length >= 2 &&
this.lines[0][0]*x+this.lines[0][1] >= this.lines[1][0]*x+this.lines[1][1])
this.lines.shift();
return this.lines[0][0]*x+this.lines[0][1];
}
}CHT applies when a DP transition looks like: dp[i] = min over j < i of { f(j) + g(j) * h(i) }. Rewrite as a family of linear functions: line j has slope g(j) and intercept f(j), query at x = h(i). We want the minimum (or maximum) y-value among all lines at each query point. The trick: maintain only the "lower convex hull" of lines — lines not on the hull are never optimal.
Li Chao Tree — handles arbitrary query order, O(log C) per op
// Li Chao Tree: handles arbitrary insertions and queries
// Each node stores the "dominant" line for its range's midpoint
class LiChaoTree {
constructor(lo, hi) {
this.lo = lo; this.hi = hi;
this.line = null; this.left = null; this.right = null;
}
// Insert line y = mx + b (minimize)
insert(m, b, lo = this.lo, hi = this.hi, node = this) {
if (!node) return;
const mid = (lo + hi) >> 1;
const newBetter = !node.line || m * mid + b < node.line[0] * mid + node.line[1];
if (newBetter) [m, b, node.line] = [node.line ? node.line[0] : m, node.line ? node.line[1] : b, [m, b]];
if (lo === hi) return;
const leftBetter = !node.line || m * lo + b < node.line[0] * lo + node.line[1];
if (leftBetter) {
if (!node.left) node.left = new LiChaoTree(lo, mid);
this.insert(m, b, lo, mid, node.left);
} else {
if (!node.right) node.right = new LiChaoTree(mid + 1, hi);
this.insert(m, b, mid + 1, hi, node.right);
}
}
query(x, lo = this.lo, hi = this.hi, node = this) {
if (!node) return Infinity;
const mid = (lo + hi) >> 1;
let best = node.line ? node.line[0] * x + node.line[1] : Infinity;
if (x <= mid) best = Math.min(best, this.query(x, lo, mid, node.left));
else best = Math.min(best, this.query(x, mid + 1, hi, node.right));
return best;
}
}
// Monotone CHT (O(n) when queries and slopes are both monotone)
class MonotoneCHT {
constructor() { this.lines = []; } // [slope, intercept]
bad(l1, l2, l3) {
// l2 is never optimal if intersection(l1,l3) is left of intersection(l1,l2)
return (l3[1]-l1[1])*(l1[0]-l2[0]) <= (l2[1]-l1[1])*(l1[0]-l3[0]);
}
addLine(m, b) {
const l = [m, b];
while (this.lines.length >= 2 && this.bad(this.lines.at(-2), this.lines.at(-1), l))
this.lines.pop();
this.lines.push(l);
}
queryMin(x) { // assumes x is non-decreasing
while (this.lines.length >= 2 &&
this.lines[0][0]*x+this.lines[0][1] >= this.lines[1][0]*x+this.lines[1][1])
this.lines.shift();
return this.lines[0][0]*x+this.lines[0][1];
}
}CHT applicability test: Can your DP be written as dp[i] = min/max over j of (f(j) + slope(j) * query(i))?
- If yes and slopes are monotone + queries are monotone: O(n) monotone CHT
- If yes but arbitrary order: Li Chao tree O(n log C)
Li Chao vs CHT: CHT requires careful maintenance of hull; Li Chao tree is simpler to code and handles arbitrary insert/query order at cost of O(log C) per operation.
Related: SMAWK algorithm for totally monotone matrices; Kinetic Heaps for moving queries. For competitive programming, Li Chao tree is the go-to for "slope trick" style DP optimizations when the slope pattern isn't guaranteed monotone.
- If yes and slopes are monotone + queries are monotone: O(n) monotone CHT
- If yes but arbitrary order: Li Chao tree O(n log C)
Li Chao vs CHT: CHT requires careful maintenance of hull; Li Chao tree is simpler to code and handles arbitrary insert/query order at cost of O(log C) per operation.
Related: SMAWK algorithm for totally monotone matrices; Kinetic Heaps for moving queries. For competitive programming, Li Chao tree is the go-to for "slope trick" style DP optimizations when the slope pattern isn't guaranteed monotone.