Pattern Reference
Convex Hull Trick
"DP optimization: line container for max/min queries. Li Chao tree, dynamic CHT."
Loading...
Deep Dive Tutorial
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];
}
}Worked Problems
trending-up
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.