Convex Hull Trick

Convex Hull Trick answers repeated minima or maxima over linear functions. Its main competitive-programming use is accelerating a DP whose transition can be rearranged into a query over lines. Instead of checking every previous state separately, maintain only the lines that can become best.

This lesson teaches one precise version: minimum queries with slopes inserted in nonincreasing order and query x-coordinates in nondecreasing order. A deque then gives O(1) amortized operations. The runnable example receives all lines before its queries so you can study the structure independently of DP. Later, we explain how to adapt the idea to DP without using future states, and when to choose binary search or a Li Chao tree instead.

Prerequisites: Linear functions y=mx+b, inequalities, Introduction to Dynamic Programming, and deques. Divide and Conquer Optimization for DP is a useful comparison, not a prerequisite. Difficulty: Expert.

Build the idea

1. Read a DP transition as a line query

   A line y=mx+b has slope m (how much y changes when x increases by one) and intercept b (its value at x=0). Consider D[i]=min over j<i of {D[j]+(xᵢ−xⱼ)²}, with D[0]=0. Expanding the square separates the part independent of j: D[i]=xᵢ²+min over j<i of {(−2xⱼ)xᵢ+D[j]+xⱼ²}.

   Each completed state j supplies a line with slope mⱼ=−2xⱼ and intercept bⱼ=D[j]+xⱼ². To compute state i, query those lines at x=xᵢ, then add xᵢ². If the x values never decrease, inserted slopes never increase and query coordinates never decrease. These are exactly the conditions for the minimum deque used here.

2. Define the lower envelope and the order assumptions

   The lower envelope is the smallest y-value among all current lines at each x. Some lines never lie on it and can be discarded. With strictly decreasing slopes, the winner moves toward later, smaller-slope lines as x increases. The deque stores just those potential winners in slope order.

   Equal slopes need special handling first: two parallel lines never change their relative order. Retain only the smaller intercept for minimum queries. This leaves strictly decreasing slopes, making the intersection denominators below positive. Do not reverse just one inequality and assume the same code handles maximum queries or the opposite slope order.

3. Remove a line that cannot become best

   For consecutive candidates A, B, C with m_A>m_B>m_C, their intersection coordinates are x_AB=(b_B−b_A)/(m_A−m_B) and x_BC=(b_C−b_B)/(m_B−m_C). B can have a useful interval only if it starts beating A before C starts beating it. Therefore remove B when x_AB≥x_BC. A tie has no interval of unique optimality, so removing B still preserves all minimum values.

   Avoid floating-point division. Both denominators are positive, so compare (b_B−b_A)(m_B−m_C)≥(b_C−b_B)(m_A−m_B) exactly. For A=3x, B=2x+4, C=x+6, the intersections are 4 and 2: B would start winning too late. Remove B; A and C meet at x=3.

   x	3x	2x+4	x+6	Minimum
   0	0	4	6	0
   3	9	10	9	9
   6	18	16	12	12

   Each new line may make several candidates at the back redundant, so the code uses a while loop. It then appends the new candidate. A line removed this way is unnecessary for every x, independently of query order.

4. Answer queries by advancing the front

   For the next query x, compare the first two lines. While the second is no worse than the first at x, remove the first. If B has a smaller slope than A, then B(x′)−A(x′) can only decrease as x′ increases. Once B beats A, A cannot return as the winner at a later query. The remaining front supplies the minimum.

   This deletion is justified only because future query coordinates do not decrease. Unlike redundancy removal at the back, removing a past winner at the front is not safe for arbitrary x order. Repeated query coordinates are allowed. Ties choose the later line here; tasks requiring a particular winning ID need an explicit tie policy beyond minimum-value correctness.

5. Worked example: three useful lines and three queries

   The program’s sample inserts A=3x, B=2x+2, and C=x+6. Here x_AB=2 and x_BC=4, so B really is needed between those coordinates. This differs from the deliberately redundant B=2x+4 in the preceding example.

   Query x	A=3x	B=2x+2	C=x+6	Answer
   0	0	2	6	0
   3	9	8	9	8
   6	18	14	12	12

   At x=0, keep A at the front and print 0. At x=3, B evaluates to 8≤9, so pop A; C is worse than B and stays behind it. At x=6, C gives 12≤14, so pop B and print 12. The sequence of answers is 0,8,12. No line is added again after it is popped.

6. Put the data structure back inside a DP

   In a DP, each line’s intercept may depend on D[j], so its value is unknown until state j is computed. Insert the line for the base state first. For each new i: query only lines from states j<i, compute D[i], and only then insert state i’s line. Pre-inserting future states would silently solve a different recurrence.

   For x=[0,1,3] and D[0]=0, start with line y=0 from state 0. At x₁=1 the minimum is 0, so D[1]=1²+0=1; insert y=−2x+2. At x₂=3, those two lines give 0 and −4, so D[2]=3²−4=5. The direct recurrence agrees: min(0+3²,1+(3−1)²)=5. The standalone program below takes explicit line coefficients; it does not compute D[i] automatically. See DP with Convex Hull Trick for an existing complete DP application.

   The same hull operations can support causally interleaved insertion and monotone queries under the stated orders. However, the numeric bounds of this line-query program do not automatically bound DP-generated slopes and intercepts: derive those bounds again for the DP you solve.

7. Choose a different query structure when needed

   Situation	Suitable approach
   Slopes ordered, x queries ordered	Deque with permanent front pops
   Slopes ordered, x queries arbitrary	Keep the hull; binary-search the best adjacent pair
   Slopes arbitrary but all lines known first	Sort by slope, deduplicate, build hull; then query
   Online arbitrary slopes and x queries	Li Chao tree on a known or compressed x-domain

   Binary-search queries cost O(log n) each and must not destroy candidates needed by later x values. A Li Chao Segment Tree does not need monotone slopes or queries; its complexity depends on the coordinate domain and implementation. Sorting future DP lines is usually invalid when their coefficients depend on unfinished states. This technique concerns envelopes of linear functions, not constructing a polygon’s geometric convex hull.

8. Read the program and check integer bounds

   Line stores slope and intercept; value(x) evaluates a candidate. isRedundant compares the two intersection positions by cross products. hull is a deque of current candidates. lineCount and queryCount describe input size, while x is the next nondecreasing query coordinate. Every independent command is written on its own line.

   Require 1≤n≤200000, 0≤q≤200000, |m|,|x|≤10⁶, and |b|≤10⁹. An evaluation has magnitude at most 10¹²+10⁹. Each cross product has magnitude at most (2×10⁹)(2×10⁶)=4×10¹⁵. Both fit signed long long, and using that type for the fields makes multiplication wide before it occurs. int is sufficient for counts. With wider coefficients, even a small final answer does not guarantee safe cross products; use a proven wider exact method instead of switching silently to floating point.

   The program assumes the supplied orders and bounds are valid. It always has at least one retained line because n≥1; q=0 simply prints nothing. Negative slopes, negative intercepts, negative x values, equal slopes, and repeated x values are all permitted within those conditions.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<deque>
using namespace std;
struct Line{
    long long slope,intercept;
    long long value(long long x)const{
        return slope*x+intercept;
    }
};
bool isRedundant(Line first,Line middle,Line last){
    // Compare intersection(first,middle) >= intersection(middle,last).
    // Both denominators are positive because slopes are strictly decreasing here.
    long long left=(middle.intercept-first.intercept)*(middle.slope-last.slope);
    long long right=(last.intercept-middle.intercept)*(first.slope-middle.slope);
    return left>=right;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int lineCount,queryCount;
    if(!(cin>>lineCount>>queryCount)){
        return 0;
    }
    deque<Line>hull;
    for(int index=0;index<lineCount;index++){
        Line line;
        cin>>line.slope>>line.intercept; // Slopes must be nonincreasing.
        if(!hull.empty()&&hull.back().slope==line.slope){
            if(hull.back().intercept<=line.intercept){
                continue; // The new parallel line can never improve a minimum.
            }
            hull.pop_back();
        }
        while(hull.size()>=2&&isRedundant(hull[hull.size()-2],hull.back(),line)){
            hull.pop_back();
        }
        hull.push_back(line);
    }
    for(int index=0;index<queryCount;index++){
        long long x;
        cin>>x; // Query coordinates must be nondecreasing.
        while(hull.size()>=2&&hull[1].value(x)<=hull[0].value(x)){
            hull.pop_front(); // A smaller-slope winner also wins at every later x.
        }
        cout<<hull.front().value(x)<<'\n';
    }
}

Complexity analysis

For n input lines and q queries, total time is O(n+q), with O(1) amortized insertion and query work under the documented order assumptions. Every line is appended once. A line can be removed from the back at most once while building the hull, and a surviving line can be removed from the front at most once across all queries. The q final evaluations add O(q). Individual operations may pop many lines; their total work is linear.

The deque contains at most n lines, so auxiliary space is O(n). No sorting is performed in this program. Sorting unordered offline lines would add O(n log n); retaining a complete hull and binary-searching arbitrary query coordinates would instead add O(q log n) query time. The exact long long arithmetic bound is part of the input contract, not a promise for unrestricted coefficients.

Example input and output

Read n q with 1≤n≤200000 and 0≤q≤200000. Read n lines m b in nonincreasing slope order, then q integer x values in nondecreasing order. Require |m|,|x|≤10⁶ and |b|≤10⁹. Print min(mx+b) over all input lines for each query. This is a minimum-value line-query program, not a DP solver or an arbitrary-order hull.

Input

3 3
3 0
2 2
1 6
0
3
6

Output

0
8
12

All three lines are useful because their consecutive intersections are at x=2 and x=4. Queries at 0,3,6 return 0,8,12, respectively. The worked table above shows all line values, and the deque trace explains exactly when each former front is removed.

Practical applications

Use CHT when transition algebra produces minⱼ(mⱼx+bⱼ) or an equivalent maximum query. Quadratic-distance and scheduling DPs often have this shape, but recognizing lines is only the first step: check whether the insertion and query orders support this deque.

Practice and related lessons: DP with Convex Hull Trick connects the hull to an actual DP; Li Chao Segment Tree handles arbitrary online slope order; Divide and Conquer Optimization for DP is an alternative when the recurrence has proven monotone split positions rather than the line-query orders needed here.

Check your understanding

Why is removing the front line permanently safe?

Put it into practice

Practice: cross-check the program against scanning every input line for each query. Include the useful-line sample, the redundant set {3x,2x+4,x+6}, parallel lines, repeated x values, and negative coordinates. Then derive the line coefficients for the D[i]=min over j<i of {D[j]+(xᵢ−xⱼ)²} recurrence before implementing its causal insertion loop.

Show a hint

For value-only tests, the oracle is min(m*x+b for every original line). Sort slopes decreasingly and queries increasingly when generating valid inputs. Do not apply the destructive query routine to an out-of-order test and call that an implementation bug.

Further reading

• Convex Hull Trick — further reading ↗