Convex Hull Trick
By @antinloop · Published 2025-10-02
Convex Hull Trick: A Geometric Speedup for Dynamic Programming
Dynamic Programming (DP) is a powerful technique for solving optimization problems. However, a standard DP solution can sometimes be too slow. A common bottleneck occurs when the recurrence relation involves searching for an optimal previous state, leading to an $O(N^2)$ complexity.
The Convex Hull Trick (CHT) is a brilliant optimization technique that speeds up a specific class of DP problems, often reducing their complexity from $O(N^2)$ to $O(N)$ or $O(N \log N)$. It achieves this by cleverly re-framing the DP problem in a geometric context.
-----
The Target DP Recurrence
The Convex Hull Trick applies to DP problems whose recurrence relation looks like this:
$dp[i] = \min_{0 \le j < i} \{ dp[j] + b_j \cdot a_i \}$
Or more generally:
$dp[i] = \min_{0 \le j < i} \{ m_j \cdot x_i + c_j \}$
Here, $m_j$ and $c_j$ are expressions that depend only on the index $j$, and $x_i$ is an expression that depends only on the index $i$. A naive approach would be to iterate through all possible $j$ for each $i$, resulting in an $O(N^2)$ algorithm.
The core insight of CHT is to recognize that the expression inside the minimum, $y = m_j \cdot x_i + c_j$, is simply the equation of a straight line. For a fixed $i$, we are trying to find which line (defined by a previous state $j$) gives the minimum $y$-value at the x-coordinate $x_i$.
As we compute our DP states, we are essentially adding a set of lines to a 2D plane. The query for $dp[i]$ becomes: "At x-coordinate $x_i$, which of our existing lines is the lowest?" The answer will always lie on the lower envelope of these lines, which forms a convex shape. This is where the name "Convex Hull Trick" comes from.
-----
The Simplest Case: Monotonicity for O(N)
The most efficient version of CHT works when two conditions are met:
1. Monotonically Decreasing Slopes: The slopes of the lines we add ($m_j$) must be monotonically decreasing (or increasing, but let's stick to decreasing for this example).
2. Monotonically Increasing Query Points: The x-coordinates we query ($x_i$) must be monotonically increasing.
When these conditions hold, we can maintain the lower envelope of lines in a simple deque (double-ended queue) and achieve an amortized $O(1)$ time for both adding a line and querying the minimum.
The Algorithm
Let's maintain a deque of lines, sorted by their slopes.
1. Adding a Line:
When we add a new line, its slope will be smaller than all slopes already in the deque. We add it to the back. However, this new line might make the last line in our deque "redundant." A line becomes redundant if it's completely covered by its neighbors on the lower envelope.
We can check for this condition by looking at the last three lines in the deque: $L_1, L_2, L_{\text{new}}$. The line $L_2$ becomes redundant if the intersection point of $L_1$ and $L_{\text{new}}$ comes before the intersection point of $L_1$ and $L_2$. We repeatedly pop the last line from the deque as long as this condition is met, and then push the new line.
2. Querying for the Minimum:
Since our query points $x_i$ are increasing, the optimal line on the hull will also move forward. We can simply check the first two lines in the deque. If the second line gives a better (lower) value at $x_i$ than the first line, it means the first line is now useless for all future queries (since $x$ will only get larger). So, we pop it from the front. We repeat this until the first line is better than the second, and that first line is our answer.
C++ Implementation for the O(N) Case
Here's how you can implement this using a deque. We'll represent a line $y = mx + c$ with its slope m and y-intercept c.
#include <iostream>
#include <vector>
#include <deque>
// Using long long to avoid overflow issues
using ll = long long;
struct Line {
ll m, c;
ll eval(ll x) {
return m * x + c;
}
};
// We use long double for intersection calculation to maintain precision
// Returns true if line L2 is made redundant by L1 and L3.
// This is checked by seeing if the intersection of L1 and L3 is to the
// left of the intersection of L1 and L2.
// (c2 - c1) / (m1 - m2) > (c3 - c1) / (m1 - m3)
// (c2 - c1) * (m1 - m3) > (c3 - c1) * (m1 - m2) (rearranged to avoid division)
bool is_redundant(const Line& l1, const Line& l2, const Line& l3) {
// Note: This check works for decreasing slopes. For increasing slopes, the inequality flips.
return (__int128)(l2.c - l1.c) * (l1.m - l3.m) >= (__int128)(l3.c - l1.c) * (l1.m - l2.m);
}
int main() {
// Example usage
std::deque<Line> hull;
// Add a line function
auto add_line = [&](Line new_line) {
// Slopes must be monotonically decreasing
while (hull.size() >= 2 && is_redundant(hull[hull.size()-2], hull.back(), new_line)) {
hull.pop_back();
}
hull.push_back(new_line);
};
// Query function
int query_ptr = 0;
auto query = [&](ll x) {
// Query points must be monotonically increasing
// This pointer optimization is also valid
while (hull.size() >= 2 && hull[0].eval(x) >= hull[1].eval(x)) {
hull.pop_front();
}
return hull[0].eval(x);
};
// --- Dummy calls to show how it's used ---
// In a real DP problem, these would be inside the DP loop
// 1. Add some lines with decreasing slopes
add_line({-1, 10});
add_line({-3, 15});
add_line({-5, 25});
// 2. Query at increasing x points
std::cout << "Query at x=1: " << query(1) << std::endl; // Should be line m=-1 -> 9
std::cout << "Query at x=3: " << query(3) << std::endl; // Should be line m=-3 -> 6
std::cout << "Query at x=5: " << query(5) << std::endl; // Should be line m=-5 -> 0
return 0;
}
-----
Handling Non-Monotonic Queries: The O(N log N) Case
What if the query points $x_i$ are not sorted? We can no longer just pop from the front of the deque. However, if the slopes are still monotonic, the lines on our lower envelope are still sorted by slope. This means we can find the optimal line for a given $x_i$ using binary search.
The add_line function remains the same. The query function changes.
C++ Implementation with Binary Search
#include <iostream>
#include <vector>
#include <algorithm>
using ll = long long;
struct Line {
ll m, c;
ll eval(ll x) {
return m * x + c;
}
};
// ... is_redundant function is the same ...
std::vector<Line> hull; // Use a vector instead of a deque
void add_line(Line new_line) {
// Slopes must be monotonically decreasing
while (hull.size() >= 2 && is_redundant(hull[hull.size()-2], hull.back(), new_line)) {
hull.pop_back();
}
hull.push_back(new_line);
}
ll query(ll x) {
// Binary search for the optimal line
int l = 0, r = hull.size() - 1;
int best_idx = 0;
while (l <= r) {
int mid = l + (r - l) / 2;
if (mid + 1 < hull.size() && hull[mid].eval(x) >= hull[mid + 1].eval(x)) {
l = mid + 1;
} else {
best_idx = mid;
r = mid - 1;
}
}
return hull[best_idx].eval(x);
}
Note: The binary search shown above finds the turning point. Simpler ternary search or std::lower_bound on intersection points can also work.
If neither slopes nor query points are monotonic, you need a more advanced, fully dynamic data structure like a Li Chao Tree, or you can maintain the hull using a std::set, which is significantly more complex to implement correctly.
-----
Full Example: Batch Scheduling Problem
Let's solve a classic problem to see CHT in action.
Problem: You have $N$ tasks to process. For each task $i$, you have its duration $T_i$ and a cost factor $F_i$. You must process them in order. You can group consecutive tasks into batches. When a batch of tasks from $i$ to $j$ is completed, its cost is $(\sum_{k=i}^{j} T_k) \cdot (\sum_{k=i}^{j} F_k)$. What is the minimum total cost to process all $N$ tasks?
Let's define some prefix sums to simplify:
$S_T[i] = \sum_{k=1}^{i} T_k$
$S_F[i] = \sum_{k=1}^{i} F_k$
The cost of a batch from $j+1$ to $i$ is $(S_T[i] - S_T[j]) \cdot (S_F[i] - S_F[j])$.
DP State:
Let $dp[i]$ be the minimum cost to complete the first $i$ tasks.
DP Recurrence:
To compute $dp[i]$, we consider making the last batch include tasks from $j+1$ to $i$. The cost would be the optimal cost for the first $j$ tasks ($dp[j]$) plus the cost of this new batch.
$dp[i] = \min_{0 \le j < i} \{ dp[j] + (S_T[i] - S_T[j]) \cdot S_F[i] \}$ (assuming the problem stated cost as (sum T) * (final F))
Let's use a more standard version where cost is (time_to_finish_batch) (sum F in batch) which is S_T[i] (S_F[i] - S_F[j]).
$dp[i] = \min_{0 \le j < i} \{ dp[j] + S_T[i] \cdot (S_F[i] - S_F[j]) \}$
$dp[i] = \min_{0 \le j < i} \{ dp[j] + S_T[i] \cdot S_F[i] - S_T[i] \cdot S_F[j] \}$
$dp[i] = S_T[i] \cdot S_F[i] + \min_{0 \le j < i} \{ -S_F[j] \cdot S_T[i] + dp[j] \}$
This perfectly matches our CHT form $y = mx+c$:
- Slope $m_j = -S_F[j]$
- Query point $x_i = S_T[i]$
- Y-intercept $c_j = dp[j]$
Checking Conditions:
Assuming $T_i, F_i > 0$:
1. Slopes: $S_F[j]$ is strictly increasing, so $m_j = -S_F[j]$ is monotonically decreasing. ✅
2. Query Points: $S_T[i]$ is strictly increasing, so $x_i$ is monotonically increasing. ✅
This fits the simplest $O(N)$ case\!
C++ Solution for the Example
#include <iostream>
#include <vector>
#include <deque>
using ll = long long;
struct Line {
ll m, c;
ll eval(ll x) { return m * x + c; }
};
bool is_redundant(const Line& l1, const Line& l2, const Line& l3) {
return (__int128)(l2.c - l1.c) * (l1.m - l3.m) >= (__int128)(l3.c - l1.c) * (l1.m - l2.m);
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
std::cin >> n;
std::vector<ll> t(n), f(n);
for (int i = 0; i < n; ++i) std::cin >> t[i];
for (int i = 0; i < n; ++i) std::cin >> f[i];
std::vector<ll> st(n + 1, 0), sf(n + 1, 0);
for (int i = 0; i < n; ++i) {
st[i + 1] = st[i] + t[i];
sf[i + 1] = sf[i] + f[i];
}
std::vector<ll> dp(n + 1, 0);
std::deque<Line> hull;
// Base case: dp[0] = 0. This corresponds to the first line we add.
// Line for j=0: m = -sf[0] = 0, c = dp[0] = 0.
hull.push_back({0, 0});
for (int i = 1; i <= n; ++i) {
// 1. Query for dp[i]
// Query point is x_i = st[i]
while (hull.size() >= 2 && hull[0].eval(st[i]) >= hull[1].eval(st[i])) {
hull.pop_front();
}
ll min_val = hull[0].eval(st[i]);
dp[i] = st[i] * sf[i] + min_val;
// 2. Add the line corresponding to state i for future computations
// Line for j=i: m_i = -sf[i], c_i = dp[i]
Line new_line = {-sf[i], dp[i]};
while (hull.size() >= 2 && is_redundant(hull[hull.size()-2], hull.back(), new_line)) {
hull.pop_back();
}
hull.push_back(new_line);
}
std::cout << dp[n] << std::endl;
return 0;
}