Convex Hull Trick
A deque-based lower hull for DP recurrences with monotone slopes and monotone queries.
Convex Hull Trick
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Convex hull trick is the DP optimization pattern for recurrences that can be rewritten as \[ dp[i] = cost(i) + \min_j (m_j x_i + b_j) \] or the corresponding maximum version. The crucial step is not the data structure. It is the algebra that turns previous states into lines and current states into query points.
Problem-Driven Motivation
A recurring contest situation is:
\(n \le 2 \cdot 10^5\),
the naive DP is \(O(n^2)\),
after expanding squares or separating variables, every candidate \(j\) contributes something linear in the current variable \(x_i\).
At that point the real problem is no longer ``try every previous \(j\).'' It is ``maintain the lower envelope of many lines.''
Recognition Pattern
The strongest signals are:
a transition with \(\min\) or \(\max\) over previous states,
algebraic expansion produces \(m_j x_i + b_j\),
query points \(x_i\) are monotone, and maybe slopes \(m_j\) are monotone too,
the DP bottleneck is the transition loop over all \(j\).
If the line insertion order or query order is arbitrary, the same derivation may still help, but the correct structure becomes Li Chao tree instead of the deque hull in this note.
Derivation
Suppose the transition is \[ dp[i] = x_i^2 + C + \min_{j < i}\bigl(dp[j] + x_j^2 - 2x_i x_j\bigr). \]
For fixed \(j\), the part depending on \(i\) is \[ (-2x_j)\cdot x_i + (dp[j] + x_j^2). \]
So state \(j\) becomes the line: \[ y = m_j x + b_j,\qquad m_j = -2x_j,\quad b_j = dp[j] + x_j^2. \]
Now the optimization is geometric:
At query \(x_i\), find the line with minimum value.
If lines are added in monotone slope order and query points are monotone, the lower hull can be stored in a deque.
Worked Problem
Problem.
The coordinates \(x_0 < x_1 < \cdots < x_{n-1}\) are sorted. 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 naive fails.
Trying all \(j < i\) for every \(i\) is \(O(n^2)\).
Why monotone CHT fits.
Because the \(x_i\) are sorted:
query points \(x_i\) are increasing,
slopes \(m_j = -2x_j\) are decreasing.
Those two monotonicities are exactly what the deque hull needs.
Deque invariant.
The lines stored in the deque appear in the same order as the intervals of \(x\)-values where they are optimal.
Insertion rule.
When a new line arrives, if the middle line of the last three is never optimal for any \(x\), remove it. That is the ``pop from the back'' step.
Query rule.
When queries come with nondecreasing \(x\), if the second line is already better than the first at the current \(x\), the first line will never become optimal again. That is the ``pop from the front'' step.
Implementation Reasoning
The implementation uses exact integer comparisons with __int128, not floating intersection points. That avoids precision bugs and makes equal-slope handling explicit.
Important invariants:
slopes are inserted in monotone order,
query points are processed in monotone order,
every line removed from the deque is permanently useless under those assumptions.
The code below keeps the generic hull operations and also includes a direct solver for the quadratic DP above.
Correctness Intuition
Each surviving line owns a contiguous interval of query \(x\)-values where it is best. Monotone slope insertion keeps those ownership intervals in order. Once a line loses its entire interval because of a newer line, it can never come back. Likewise, once the front line loses to the next line at the current monotone query point, all later query points are even worse for that front line.
Complexity Analysis
For the monotone deque version:
add line: amortized \(O(1)\),
query: amortized \(O(1)\),
total for \(n\) insertions and \(n\) queries: \(O(n)\),
memory: \(O(n)\).
Common Pitfalls
Using the deque hull when slopes or query points are not monotone.
Deriving the line formula incorrectly even though the data structure is correct.
Forgetting to handle equal slopes.
Flipping inequalities when switching between minimum and maximum.
Using floating intersections when exact integer arithmetic was available.
Variants and Failure Modes
Li Chao tree handles arbitrary insertion/query order.
Offline hulls can work when only one of the monotonicities is missing but queries can be resorted.
If the recurrence does not reduce to linear functions, this trick is not applicable.
Practice Problems
Quadratic DP transitions on sorted coordinates.
Monotone slope/query problems where each previous state is a line.
Problems that can be solved either by monotone CHT or by Li Chao after losing monotonicity.
References
Code
Contest-ready reference implementation for the idea explained above.
#include <bits/stdc++.h>
using namespace std;
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 MonotoneConvexHullTrick {
deque<Line> hull;
// Assumes minimum queries, slopes inserted in monotone order.
static bool is_bad(const Line& a, const Line& b, const Line& c) {
#if defined(__SIZEOF_INT128__)
return (__int128)(b.b - a.b) * (a.m - c.m) >= (__int128)(c.b - a.b) * (a.m - b.m);
#else
long double left = (long double)(b.b - a.b) * (a.m - c.m);
long double right = (long double)(c.b - a.b) * (a.m - b.m);
return left >= right;
#endif
}
void add_line(long long m, long long b) {
Line line{m, b};
while (!hull.empty() && hull.back().m == line.m) {
if (hull.back().b <= line.b) return;
hull.pop_back();
}
while (hull.size() >= 2 && is_bad(hull[hull.size() - 2], hull.back(), line)) {
hull.pop_back();
}
hull.push_back(line);
}
long long query(long long x) {
while (hull.size() >= 2 && hull[0].eval_ld(x) >= hull[1].eval_ld(x)) {
hull.pop_front();
}
return hull.front().eval(x);
}
};
// Example application:
// x must be sorted increasingly.
vector<long long> solve_quadratic_dp_sorted(const vector<long long>& x, long long fixed_cost) {
int n = (int)x.size();
if (n == 0) return {};
vector<long long> dp(n, 0);
MonotoneConvexHullTrick cht;
cht.add_line(-2 * x[0], x[0] * x[0]);
for (int i = 1; i < n; ++i) {
dp[i] = x[i] * x[i] + fixed_cost + cht.query(x[i]);
cht.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.