⚙️AlgorithmAdvanced

Convex Hull Trick (CHT)

Key Points

•
The Convex Hull Trick (CHT) speeds up dynamic programs where each state is a minimum over linear functions, such as dp[i] = mi $n_{j}$ (dp[j] + b[j] × a[i]).
•
You treat each candidate j as a line y = m x + c with m = b[j] and c = dp[j], and then query the minimum value at x = a[i].
•
If slopes are added in monotone order and query x values are monotone, a deque-based CHT gives O(n) total time using a moving pointer.
•
If slopes are monotone but queries arrive in arbitrary order, you can binary search on breakpoints for O(log n) query time.
•
For fully dynamic cases (arbitrary slope insertion and arbitrary query order), a Li Chao tree guarantees O(log C) per operation where C is the x-coordinate range.
•
The key test for removing a line uses intersection ordering or a cross-multiplication check to avoid floating-point precision errors.
•
Handle equal slopes carefully: when minimizing, keep only the line with the smaller intercept; others are dominated.
•
Use 64-bit integers with __int128 in comparisons to avoid overflow, and ensure a[] is sorted if you rely on the monotone pointer optimization.

Prerequisites

→Time complexity and Big-O notation — To understand amortized O(1), O(log n), and O(n) bounds of different CHT variants.
→Basic dynamic programming — To recognize when a recurrence can be rewritten as a minimum over linear functions.
→Lines and slopes (analytic geometry) — To interpret transitions as lines and reason about intersections and envelopes.
→Binary search — To query the hull using breakpoints when x-queries are not monotone.
→Integer overflow and numeric types — To correctly implement cross-multiplication checks and line evaluations without overflow.
→Deque and pointer technique — To implement the O(n) hull with monotone queries efficiently.
→Segment trees (optional) — To better understand the Li Chao tree structure for fully dynamic CHT.

Detailed Explanation

Tap terms for definitions

01Overview

The Convex Hull Trick (CHT) is a classic optimization that accelerates computations of the form min_j (m_j × x + c_j), which often appears inside dynamic programming (DP) transitions. The idea is to model each candidate j as a straight line y = m_j x + c_j and then, for each query x, find the line that yields the minimum y-value. Geometrically, this is the lower envelope of a set of lines. If we maintain just the lines that could be optimal for some x (a lower convex hull in slope order), we can answer each query faster than scanning all lines. In DP problems like dp[i] = min_{j<i} (dp[j] + b[j] × a[i]), we treat b[j] as the slope and dp[j] as the intercept, and query at x = a[i]. Under favorable conditions—monotonic slopes and monotonic x-queries—the data structure becomes extremely simple and runs in O(n). When queries come in arbitrary order (but slopes remain monotonic), we can store intersection breakpoints and perform binary search in O(log n). In fully general settings (arbitrary insert and query orders), a Li Chao segment tree supports O(log C) operations, where C is the coordinate span of x. CHT is widely used in competitive programming for cost optimization, scheduling, divide-and-conquer DP, and other problems where transitions are linear in a parameter.

02Intuition & Analogies

Imagine you are comparing mobile plans. Each plan charges a base fee plus a per-GB cost: total_cost(x) = perGB × x + base. For a fixed data usage x, you would pick the plan with the smallest total cost. If you plot all plans as straight lines on a graph (x on the horizontal axis and total cost on the vertical axis), the best plan is the line lying lowest at your chosen x. If you start at small x and slide right, the best plan occasionally switches to another line at their intersection point—exactly where one plan becomes cheaper than another. This picture is the heart of the Convex Hull Trick: maintain the lower envelope of lines so that for any x, you can quickly find which line is best. Now, translate this to DP: each candidate j that can transition to i contributes a line y = b[j] x + dp[j], and you want the minimum at x = a[i]. If your data usage x always increases (a[i] is sorted), the identity of the best plan changes in a simple, left-to-right way; you can keep a pointer that only moves forward as you query larger x. If your per-GB costs (slopes) also come in sorted order, then when adding a new plan you can discard any plans that will never become the cheapest (they are hidden above the lower envelope). The result is a compact set of potentially optimal plans and very fast lookups, mirroring how you would actually shop: keep only the few non-dominated choices and compare them in the natural order as your needs grow.

03Formal Definition

We are given a set of affine functions (lines) L = {ℓ_k(x) =

m_{k}

x +

c_{k}

}. The lower envelope is the function E(x) =

mi n_{k}

ℓ_k(x). In many DP problems of interest, we must evaluate E(x) at multiple x-values and we progressively add new lines. The Convex Hull Trick maintains a subset H ⊆ L in slope order such that E(x) =

mi n_{ℓ \in H}

ℓ(x) for all x. If slopes are strictly monotone (e.g.,

m_{1} < m_{2}

< …) and we seek the minimum, then H is a convex chain: the x-coordinates of pairwise intersections are strictly increasing, and every line in H is optimal on a contiguous interval. Let the intersection of ℓ_i and ℓ_j be

x_{ij}

= (

c_{j}

−

c_{i}

) / (

m_{i}

−

m_{j}

). If for three consecutive lines in slope order (ℓ_1, ℓ_2, ℓ_3) we find

x_{13} \leq x_{12}

, then ℓ_2 is never optimal and can be removed. This condition can be checked safely with integer cross-multiplication. Querying the minimum at x involves either: (1) advancing a pointer along H while ℓ_{k+1}(x) ≤ ℓ_k(x), which is amortized O(1) if x is nondecreasing; or (2) binary searching the intersection breakpoints to find the segment covering x in O(log

∣ H ∣

). Without monotonicity assumptions, a Li Chao tree maintains the minimum of lines over a fixed domain by recursively replacing the better line over subranges, supporting O(log C) per operation for coordinate span C.

04When to Use

Use CHT when your DP or optimization problem reduces to computing values of the form min_j (m_j × x_i + c_j) many times with lines being added on the fly. Classic cases include: (1) DP with sorted query parameters, e.g., dp[i] = min_{j<i} (dp[j] + b[j] × a[i]) where a[i] is nondecreasing. If b[j] is also monotone in j, the deque + pointer variant runs in O(n). (2) Offline queries with arbitrary order but monotone slopes: maintain the hull and binary search on intersection points in O(log n) per query. (3) Arbitrary insert/query order across a known x-range (e.g., coordinates fit in 64-bit): use a Li Chao tree for O(log C) per operation. Typical competitive programming tasks: optimizing cost functions linear in a parameter (knapsack-like costs with linear penalties), scheduling with linear penalties, DP on lines or partitions where each previous state contributes an affine function, and some divide-and-conquer optimizations after transforming the recurrence into linear forms. If a[i] is not sorted and you cannot reorder queries, prefer Li Chao. If slopes are not monotone (in insertion order) and you cannot sort them, Li Chao also applies. If the function is not linear (e.g., quadratic), consider variants like Convex Hull Trick on quadratics or separate techniques (e.g., Divide & Conquer DP Optimization) depending on structure.

⚠️Common Mistakes

• Ignoring monotonicity requirements: The O(n) deque method assumes slopes are added in monotone order and x-queries are monotone. If either is violated, results can be incorrect or complexity can degrade. Use Li Chao or binary search when needed. • Floating-point intersections: Computing intersection x = (c2 − c1) / (m1 − m2) in double can introduce precision bugs when x is large or near an integer boundary. Prefer integer cross-multiplication (using __int128) for comparisons, or store breakpoints as long double only when acceptable. • Equal slopes: If two lines have the same slope, for minimization keep only the one with the smaller intercept; otherwise, you may keep a dominated line that later breaks your query logic. • Wrong inequality when popping: The condition for removing the middle line depends on the slope order and whether you maintain a lower or upper hull. Reusing code snippets without aligning these assumptions often causes subtle off-by-one or inequality-direction errors. • Overflow in 64-bit: Evaluations like m × x + c or cross products can overflow long long. Use __int128 for intermediate products when values can reach about 1e12 or more. • Not updating the pointer correctly: In the monotone x-query method, advance while the next line is strictly better at the current x; using ≥ vs > changes tie-handling and can affect correctness for equal values. • Mixing min and max: The data structure for minimum differs in inequalities from the one for maximum; flipping signs consistently is safer than editing multiple comparisons.

Key Formulas

CHT-friendly DP

d p [i] = 0 \leq j < i min (d p [j] + b [j] \cdot a [i])

Explanation: This recurrence states each dp[i] is the minimum over previous states of a linear function in a[i]. This is exactly the form that CHT accelerates by turning each j into a line y = m x + c.

Line mapping

ℓ_{j} (x) = m_{j} x + c_{j}, m_{j} = b [j], c_{j} = d p [j]

Explanation: Each candidate j contributes a line whose slope is b[j] and intercept is dp[j]. Querying dp[i] reduces to evaluating the minimum line value at x = a[i].

Intersection point

x_{ij} = \frac{c _{j} - c _{i}}{m _{i} - m _{j}}

Explanation: The x-coordinate where lines i and j have equal value. Ordering these intersection points lets us binary search for the optimal line at a given x.

Dominance (pop) test for increasing slopes, lower hull

(c_{3} - c_{1}) (m_{1} - m_{2}) \leq (c_{2} - c_{1}) (m_{1} - m_{3})

Explanation: For three lines with $m_{1} < m_{2} < m_{3}$ , this cross-multiplication condition detects that line 2 is never optimal (its intersection with line 1 is to the right of line 1 vs 3). It avoids division and floating-point errors.

Line evaluation

val (ℓ, x) = m \cdot x + c

Explanation: To answer a query at x, evaluate candidate lines and pick the smallest value for minimization. In monotone-query CHT, you only compare neighboring lines.

Deque CHT complexity

T_{deque} (n) = O (n)

Explanation: With monotone slopes and nondecreasing x, each line is inserted and removed at most once, and the pointer advances at most n times. Thus total time is linear in the number of lines/queries.

Binary search CHT complexity

T_{binary} (n) = O (lo g n) per query

Explanation: When slopes are monotone, we can store intersection breakpoints and find the active line via binary search. Each query takes logarithmic time in the number of lines.

Li Chao complexity

T_{LiChao} = O (lo g C) per op

Explanation: For coordinate range size C (e.g., x in [L, R]), inserting a line or querying a point traverses O(log C) nodes in the implicit segment tree.

Complexity Analysis

In the monotone-slope + monotone-query (deque) Convex Hull Trick, we maintain a lower hull in increasing slope order. Each line is inserted once, and the pop condition (cross-multiplication) ensures any dominated middle line is removed immediately. During queries, a pointer only advances when the next line becomes strictly better at the current x. Because each advance discards the current best for all future larger x, the pointer moves at most O(n) times. Therefore, for n insertions and n queries, the total time is O(n), with O(n) space to store the hull. If queries are not monotone but slopes are, we can store intersection breakpoints (where the optimal line changes) and binary search them for each query in O(log n) time. Insertions still cost amortized O(1), yielding O(n log n) total for n queries and n insertions, with O(n) space. In the fully dynamic case without monotonicity guarantees, a Li Chao tree operates over a fixed x-domain [L, R]. Each insertion or query descends O(log C) nodes, where C ≈ R − L and is typically proportional to the numeric coordinate span. Time is O(log C) per operation and space is O(C) if built explicitly or O(n) if nodes are created lazily during insertions. Practical costs: intersection checks should use 128-bit intermediates to avoid overflow when values approach 1e12–1e18; line evaluation is O(1). For floating-point variants (binary-search CHT with long double breakpoints), numerical error may cause off-by-one in the chosen segment; robust integer comparisons are preferred for exact problems.

Code Examples

Monotone deque CHT for DP: O(n) with increasing slopes and increasing queries

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // CHT for minimizing y = m*x + c
5 // Assumptions:
6 //  - Lines are added with nondecreasing slope m
7 //  - Query x are nondecreasing
8 // We use a vector hull and a pointer that only moves forward.
9 
10 struct Line {
11     long long m; // slope
12     long long c; // intercept
13     // Evaluate this line at x, using 128-bit for safety
14     long long eval(long long x) const {
15         __int128 val = (__int128)m * x + c;
16         return (long long)val;
17     }
18 };
19 
20 // Check if l2 is useless when between l1 and l3 for LOWER hull, with m1 < m2 < m3
21 static bool isBad(const Line &l1, const Line &l2, const Line &l3) {
22     // Intersection(l1,l2) >= Intersection(l2,l3)  <=>  pop l2
23     // Compare (c2 - c1)/(m1 - m2) >= (c3 - c2)/(m2 - m3)
24     // A robust equivalent without division is:
25     // (c3 - c1) * (m1 - m2) <= (c2 - c1) * (m1 - m3)
26     __int128 left  = (__int128)(l3.c - l1.c) * (l1.m - l2.m);
27     __int128 right = (__int128)(l2.c - l1.c) * (l1.m - l3.m);
28     return left <= right; // if true, l2 is never optimal
29 }
30 
31 struct CHTDeque {
32     vector<Line> hull; // increasing slopes for lower hull
33     size_t ptr = 0;    // pointer to best line for current/next x
34 
35     void add_line(long long m, long long c) {
36         Line ln{m, c};
37         // Handle equal slope: keep only smaller intercept for minimization
38         if (!hull.empty() && hull.back().m == m) {
39             if (c >= hull.back().c) return; // new line is worse
40             hull.pop_back();
41             if (ptr) ptr = min(ptr, hull.size());
42         }
43         while (hull.size() >= 2 && isBad(hull[hull.size()-2], hull.back(), ln)) {
44             // If we pop something before ptr, move ptr back to keep it valid
45             if (ptr == hull.size() - 1) ptr--;
46             hull.pop_back();
47         }
48         hull.push_back(ln);
49         if (ptr >= hull.size()) ptr = hull.size() - 1;
50     }
51 
52     long long query(long long x) {
53         // Move pointer while the next line gives a smaller value at x
54         while (ptr + 1 < hull.size() && hull[ptr+1].eval(x) <= hull[ptr].eval(x)) {
55             ++ptr;
56         }
57         return hull[ptr].eval(x);
58     }
59 };
60 
61 int main() {
62     ios::sync_with_stdio(false);
63     cin.tie(nullptr);
64 
65     // Example DP: dp[i] = min_{j < i} (dp[j] + b[j] * a[i])
66     // Conditions (for O(n) CHT): a[i] nondecreasing, b[j] nondecreasing in j.
67     int n = 6;
68     vector<long long> a = {0, 2, 3, 5, 8, 13}; // 1..n-1 used for simplicity; a is nondecreasing
69     vector<long long> b = {1, 1, 2, 3, 5, 8};  // slopes nondecreasing
70     vector<long long> dp(n, 0);
71 
72     // Base case: dp[0] = 0, add line from j=0: y = b[0]*x + dp[0]
73     CHTDeque cht;
74     cht.add_line(b[0], dp[0]);
75 
76     for (int i = 1; i < n; ++i) {
77         long long x = a[i];
78         // Query min over j < i at x = a[i]
79         long long best = cht.query(x);
80         dp[i] = best; // This example has no extra constant; in problems add constant terms if present
81         // Insert line for j = i: y = b[i]*x + dp[i]
82         cht.add_line(b[i], dp[i]);
83     }
84 
85     // Output dp values
86     for (int i = 0; i < n; ++i) {
87         cout << "dp[" << i << "] = " << dp[i] << '\n';
88     }
89     return 0;
90 }
91

Maintains a lower hull with increasing slopes and answers queries for nondecreasing x using a forward-only pointer. The isBad() test removes the middle line when its intersection ordering is violated, ensuring only potentially optimal lines remain. For the DP form dp[i] = min_j (dp[j] + b[j] × a[i]), we map lines as (m = b[j], c = dp[j]) and query at x = a[i].

Time: O(n) total for n insertions and n queries (amortized O(1) per operation) under monotone slopes and monotone x.Space: O(n) for the hull.

Binary search CHT with breakpoints (monotone slopes, arbitrary query order)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // CHT for minimizing y = m*x + c with slopes inserted in increasing order.
5 // Stores intersection breakpoints (as long double) and answers queries via binary search.
6 // Note: using long double can introduce precision issues for adversarial inputs;
7 // prefer integer cross-checks if exactness is required.
8 
9 struct Line {
10     long long m, c;
11     long long eval(long long x) const {
12         __int128 val = (__int128)m * x + c;
13         return (long long)val;
14     }
15 };
16 
17 struct CHTBinary {
18     vector<Line> st;         // lines in increasing slope
19     vector<long double> brk; // breakpoint x where this line becomes better than previous
20 
21     // Compute intersection x where l2 starts beating l1: solve l1(x) = l2(x), take x as long double
22     static long double intersectLD(const Line &l1, const Line &l2) {
23         // (m1 - m2) * x = c2 - c1  =>  x = (c2 - c1) / (m1 - m2)
24         return (long double)(l2.c - l1.c) / (long double)(l1.m - l2.m);
25     }
26 
27     void add_line(long long m, long long c) {
28         Line ln{m, c};
29         // Handle equal slopes: keep only smaller c for minimization
30         if (!st.empty() && st.back().m == m) {
31             if (c >= st.back().c) return;
32             st.pop_back();
33             if (!brk.empty()) brk.pop_back();
34         }
35         // While the last line is never optimal (breakpoint not increasing), pop it
36         while (!st.empty()) {
37             if (st.size() == 1) {
38                 long double x = intersectLD(st.back(), ln);
39                 st.push_back(ln);
40                 brk.push_back(x);
41                 return;
42             } else {
43                 // Check if new breakpoint with ln is <= last breakpoint => last line is useless
44                 long double x = intersectLD(st.back(), ln);
45                 if (x <= brk.back()) {
46                     st.pop_back();
47                     brk.pop_back();
48                 } else {
49                     st.push_back(ln);
50                     brk.push_back(x);
51                     return;
52                 }
53             }
54         }
55         // If empty, just push with -inf breakpoint
56         st.push_back(ln);
57         brk.push_back(-numeric_limits<long double>::infinity());
58     }
59 
60     long long query(long long x) const {
61         // Find the rightmost breakpoint <= x
62         int idx = upper_bound(brk.begin(), brk.end(), (long double)x) - brk.begin() - 1;
63         idx = max(idx, 0);
64         return st[idx].eval(x);
65     }
66 };
67 
68 int main() {
69     ios::sync_with_stdio(false);
70     cin.tie(nullptr);
71 
72     // Example: build hull of lines and answer queries in arbitrary order.
73     CHTBinary cht;
74     vector<pair<long long,long long>> lines = {
75         {1, 5},  // y = 1*x + 5
76         {2, 1},  // y = 2*x + 1
77         {3, -2}, // y = 3*x - 2
78     };
79     // Ensure slopes are added in increasing order
80     sort(lines.begin(), lines.end());
81     for (auto [m,c] : lines) cht.add_line(m,c);
82 
83     vector<long long> queries = { -10, 0, 1, 3, 10 };
84     for (long long x : queries) {
85         cout << "min at x=" << x << " -> " << cht.query(x) << '\n';
86     }
87     return 0;
88 }
89

Maintains lines in increasing slope order and stores the x-coordinate where each new line becomes better than the previous one. Queries binary search these breakpoints to pick the correct line. This supports arbitrary query order but still requires monotone slope insertion.

Time: Insertion amortized O(1); each query O(log n). Building n lines and answering q queries is O(n + q log n).Space: O(n) for lines and breakpoints.

Li Chao Tree: fully dynamic CHT for arbitrary slopes and query order

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Li Chao tree for minimizing y = m*x + c over x in [L, R].
5 // Works with arbitrary insertion order and arbitrary queries.
6 
7 struct Line {
8     long long m, c; // y = m*x + c
9     long long eval(long long x) const {
10         __int128 val = (__int128)m * x + c; // avoid overflow
11         return (long long)val;
12     }
13 };
14 
15 struct Node {
16     Line ln;
17     Node *l = nullptr, *r = nullptr;
18     Node(Line _ln) : ln(_ln) {}
19 };
20 
21 struct LiChao {
22     long long L, R; // domain inclusive
23     Node* root;
24     static constexpr long long INF = (1LL<<62);
25 
26     LiChao(long long L_, long long R_) : L(L_), R(R_), root(nullptr) {}
27 
28     void add_line(Line nw) { add_line(root, L, R, nw); }
29     void add_line(Node* &cur, long long l, long long r, Line nw) {
30         if (!cur) { cur = new Node(nw); return; }
31         long long mid = l + (r - l) / 2;
32         bool lef = nw.eval(l) < cur->ln.eval(l);
33         bool mdd = nw.eval(mid) < cur->ln.eval(mid);
34         bool rig = nw.eval(r) < cur->ln.eval(r);
35         if (mdd) swap(nw, cur->ln);
36         if (l == r) return;
37         if (lef != mdd) add_line(cur->l, l, mid, nw);
38         else if (rig != mdd) add_line(cur->r, mid+1, r, nw);
39         // If neither side differs, nw is worse everywhere; drop it.
40     }
41 
42     void add_segment(Line nw, long long ql, long long qr) {
43         add_segment(root, L, R, nw, ql, qr);
44     }
45     void add_segment(Node* &cur, long long l, long long r, Line nw, long long ql, long long qr) {
46         if (qr < l || r < ql) return;
47         if (ql <= l && r <= qr) { add_line(cur, l, r, nw); return; }
48         if (!cur) cur = new Node(Line{0, INF});
49         long long mid = l + (r - l) / 2;
50         add_segment(cur->l, l, mid, nw, ql, qr);
51         add_segment(cur->r, mid+1, r, nw, ql, qr);
52     }
53 
54     long long query(long long x) const { return query(root, L, R, x); }
55     long long query(Node* cur, long long l, long long r, long long x) const {
56         if (!cur) return (long long)((1ULL<<63)-1); // approx +inf
57         long long res = cur->ln.eval(x);
58         if (l == r) return res;
59         long long mid = l + (r - l) / 2;
60         if (x <= mid) return min(res, query(cur->l, l, mid, x));
61         else          return min(res, query(cur->r, mid+1, r, x));
62     }
63 };
64 
65 int main() {
66     ios::sync_with_stdio(false);
67     cin.tie(nullptr);
68 
69     // Domain for x (adjust to your problem constraints)
70     long long L = -1000000000000LL, R = 1000000000000LL; // [-1e12, 1e12]
71     LiChao cht(L, R);
72 
73     // Insert some lines in arbitrary order
74     cht.add_line(Line{3, 7});   // y = 3x + 7
75     cht.add_line(Line{-2, 10}); // y = -2x + 10
76     cht.add_line(Line{1, -5});  // y = x - 5
77 
78     // Query arbitrary x
79     vector<long long> xs = {-7, 0, 4, 1000000000000LL};
80     for (long long x : xs) {
81         cout << "min at x=" << x << " -> " << cht.query(x) << '\n';
82     }
83 
84     // Optional: add a line active only on a segment [l, r]
85     cht.add_segment(Line{0, 3}, -5, 5); // y = 3 on [-5,5]
86     cout << "after segment add, x=2 -> " << cht.query(2) << '\n';
87 
88     return 0;
89 }
90

Implements a Li Chao tree that supports adding lines in any order and querying any x within a fixed domain. It also shows how to add a line over a segment, which is useful when a transition applies only to a subrange of x. This approach avoids slope and query monotonicity constraints.

Time: O(log C) per insertion and per query, where C is the size of the x-domain (typically proportional to R − L).Space: O(n) nodes created lazily for n insertions (or O(C) if built explicitly).

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// CHT for minimizing y = m*x + c
5	// Assumptions:
6	// - Lines are added with nondecreasing slope m
7	// - Query x are nondecreasing
8	// We use a vector hull and a pointer that only moves forward.
9
10	struct Line {
11	long long m; // slope
12	long long c; // intercept
13	// Evaluate this line at x, using 128-bit for safety
14	long long eval(long long x) const {
15	__int128 val = (__int128)m * x + c;
16	return (long long)val;
17	}
18	};
19
20	// Check if l2 is useless when between l1 and l3 for LOWER hull, with m1 < m2 < m3
21	static bool isBad(const Line &l1, const Line &l2, const Line &l3) {
22	// Intersection(l1,l2) >= Intersection(l2,l3) <=> pop l2
23	// Compare (c2 - c1)/(m1 - m2) >= (c3 - c2)/(m2 - m3)
24	// A robust equivalent without division is:
25	// (c3 - c1) * (m1 - m2) <= (c2 - c1) * (m1 - m3)
26	__int128 left = (__int128)(l3.c - l1.c) * (l1.m - l2.m);
27	__int128 right = (__int128)(l2.c - l1.c) * (l1.m - l3.m);
28	return left <= right; // if true, l2 is never optimal
29	}
30
31	struct CHTDeque {
32	vector<Line> hull; // increasing slopes for lower hull
33	size_t ptr = 0; // pointer to best line for current/next x
34
35	void add_line(long long m, long long c) {
36	Line ln{m, c};
37	// Handle equal slope: keep only smaller intercept for minimization
38	if (!hull.empty() && hull.back().m == m) {
39	if (c >= hull.back().c) return; // new line is worse
40	hull.pop_back();
41	if (ptr) ptr = min(ptr, hull.size());
42	}
43	while (hull.size() >= 2 && isBad(hull[hull.size()-2], hull.back(), ln)) {
44	// If we pop something before ptr, move ptr back to keep it valid
45	if (ptr == hull.size() - 1) ptr--;
46	hull.pop_back();
47	}
48	hull.push_back(ln);
49	if (ptr >= hull.size()) ptr = hull.size() - 1;
50	}
51
52	long long query(long long x) {
53	// Move pointer while the next line gives a smaller value at x
54	while (ptr + 1 < hull.size() && hull[ptr+1].eval(x) <= hull[ptr].eval(x)) {
55	++ptr;
56	}
57	return hull[ptr].eval(x);
58	}
59	};
60
61	int main() {
62	ios::sync_with_stdio(false);
63	cin.tie(nullptr);
64
65	// Example DP: dp[i] = min_{j < i} (dp[j] + b[j] * a[i])
66	// Conditions (for O(n) CHT): a[i] nondecreasing, b[j] nondecreasing in j.
67	int n = 6;
68	vector<long long> a = {0, 2, 3, 5, 8, 13}; // 1..n-1 used for simplicity; a is nondecreasing
69	vector<long long> b = {1, 1, 2, 3, 5, 8}; // slopes nondecreasing
70	vector<long long> dp(n, 0);
71
72	// Base case: dp[0] = 0, add line from j=0: y = b[0]*x + dp[0]
73	CHTDeque cht;
74	cht.add_line(b[0], dp[0]);
75
76	for (int i = 1; i < n; ++i) {
77	long long x = a[i];
78	// Query min over j < i at x = a[i]
79	long long best = cht.query(x);
80	dp[i] = best; // This example has no extra constant; in problems add constant terms if present
81	// Insert line for j = i: y = b[i]*x + dp[i]
82	cht.add_line(b[i], dp[i]);
83	}
84
85	// Output dp values
86	for (int i = 0; i < n; ++i) {
87	cout << "dp[" << i << "] = " << dp[i] << '\n';
88	}
89	return 0;
90	}
91

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// CHT for minimizing y = m*x + c with slopes inserted in increasing order.
5	// Stores intersection breakpoints (as long double) and answers queries via binary search.
6	// Note: using long double can introduce precision issues for adversarial inputs;
7	// prefer integer cross-checks if exactness is required.
8
9	struct Line {
10	long long m, c;
11	long long eval(long long x) const {
12	__int128 val = (__int128)m * x + c;
13	return (long long)val;
14	}
15	};
16
17	struct CHTBinary {
18	vector<Line> st; // lines in increasing slope
19	vector<long double> brk; // breakpoint x where this line becomes better than previous
20
21	// Compute intersection x where l2 starts beating l1: solve l1(x) = l2(x), take x as long double
22	static long double intersectLD(const Line &l1, const Line &l2) {
23	// (m1 - m2) * x = c2 - c1 => x = (c2 - c1) / (m1 - m2)
24	return (long double)(l2.c - l1.c) / (long double)(l1.m - l2.m);
25	}
26
27	void add_line(long long m, long long c) {
28	Line ln{m, c};
29	// Handle equal slopes: keep only smaller c for minimization
30	if (!st.empty() && st.back().m == m) {
31	if (c >= st.back().c) return;
32	st.pop_back();
33	if (!brk.empty()) brk.pop_back();
34	}
35	// While the last line is never optimal (breakpoint not increasing), pop it
36	while (!st.empty()) {
37	if (st.size() == 1) {
38	long double x = intersectLD(st.back(), ln);
39	st.push_back(ln);
40	brk.push_back(x);
41	return;
42	} else {
43	// Check if new breakpoint with ln is <= last breakpoint => last line is useless
44	long double x = intersectLD(st.back(), ln);
45	if (x <= brk.back()) {
46	st.pop_back();
47	brk.pop_back();
48	} else {
49	st.push_back(ln);
50	brk.push_back(x);
51	return;
52	}
53	}
54	}
55	// If empty, just push with -inf breakpoint
56	st.push_back(ln);
57	brk.push_back(-numeric_limits<long double>::infinity());
58	}
59
60	long long query(long long x) const {
61	// Find the rightmost breakpoint <= x
62	int idx = upper_bound(brk.begin(), brk.end(), (long double)x) - brk.begin() - 1;
63	idx = max(idx, 0);
64	return st[idx].eval(x);
65	}
66	};
67
68	int main() {
69	ios::sync_with_stdio(false);
70	cin.tie(nullptr);
71
72	// Example: build hull of lines and answer queries in arbitrary order.
73	CHTBinary cht;
74	vector<pair<long long,long long>> lines = {
75	{1, 5}, // y = 1*x + 5
76	{2, 1}, // y = 2*x + 1
77	{3, -2}, // y = 3*x - 2
78	};
79	// Ensure slopes are added in increasing order
80	sort(lines.begin(), lines.end());
81	for (auto [m,c] : lines) cht.add_line(m,c);
82
83	vector<long long> queries = { -10, 0, 1, 3, 10 };
84	for (long long x : queries) {
85	cout << "min at x=" << x << " -> " << cht.query(x) << '\n';
86	}
87	return 0;
88	}
89

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Li Chao tree for minimizing y = m*x + c over x in [L, R].
5	// Works with arbitrary insertion order and arbitrary queries.
6
7	struct Line {
8	long long m, c; // y = m*x + c
9	long long eval(long long x) const {
10	__int128 val = (__int128)m * x + c; // avoid overflow
11	return (long long)val;
12	}
13	};
14
15	struct Node {
16	Line ln;
17	Node l = nullptr, r = nullptr;
18	Node(Line _ln) : ln(_ln) {}
19	};
20
21	struct LiChao {
22	long long L, R; // domain inclusive
23	Node* root;
24	static constexpr long long INF = (1LL<<62);
25
26	LiChao(long long L_, long long R_) : L(L_), R(R_), root(nullptr) {}
27
28	void add_line(Line nw) { add_line(root, L, R, nw); }
29	void add_line(Node* &cur, long long l, long long r, Line nw) {
30	if (!cur) { cur = new Node(nw); return; }
31	long long mid = l + (r - l) / 2;
32	bool lef = nw.eval(l) < cur->ln.eval(l);
33	bool mdd = nw.eval(mid) < cur->ln.eval(mid);
34	bool rig = nw.eval(r) < cur->ln.eval(r);
35	if (mdd) swap(nw, cur->ln);
36	if (l == r) return;
37	if (lef != mdd) add_line(cur->l, l, mid, nw);
38	else if (rig != mdd) add_line(cur->r, mid+1, r, nw);
39	// If neither side differs, nw is worse everywhere; drop it.
40	}
41
42	void add_segment(Line nw, long long ql, long long qr) {
43	add_segment(root, L, R, nw, ql, qr);
44	}
45	void add_segment(Node* &cur, long long l, long long r, Line nw, long long ql, long long qr) {
46	if (qr < l \|\| r < ql) return;
47	if (ql <= l && r <= qr) { add_line(cur, l, r, nw); return; }
48	if (!cur) cur = new Node(Line{0, INF});
49	long long mid = l + (r - l) / 2;
50	add_segment(cur->l, l, mid, nw, ql, qr);
51	add_segment(cur->r, mid+1, r, nw, ql, qr);
52	}
53
54	long long query(long long x) const { return query(root, L, R, x); }
55	long long query(Node* cur, long long l, long long r, long long x) const {
56	if (!cur) return (long long)((1ULL<<63)-1); // approx +inf
57	long long res = cur->ln.eval(x);
58	if (l == r) return res;
59	long long mid = l + (r - l) / 2;
60	if (x <= mid) return min(res, query(cur->l, l, mid, x));
61	else return min(res, query(cur->r, mid+1, r, x));
62	}
63	};
64
65	int main() {
66	ios::sync_with_stdio(false);
67	cin.tie(nullptr);
68
69	// Domain for x (adjust to your problem constraints)
70	long long L = -1000000000000LL, R = 1000000000000LL; // [-1e12, 1e12]
71	LiChao cht(L, R);
72
73	// Insert some lines in arbitrary order
74	cht.add_line(Line{3, 7}); // y = 3x + 7
75	cht.add_line(Line{-2, 10}); // y = -2x + 10
76	cht.add_line(Line{1, -5}); // y = x - 5
77
78	// Query arbitrary x
79	vector<long long> xs = {-7, 0, 4, 1000000000000LL};
80	for (long long x : xs) {
81	cout << "min at x=" << x << " -> " << cht.query(x) << '\n';
82	}
83
84	// Optional: add a line active only on a segment [l, r]
85	cht.add_segment(Line{0, 3}, -5, 5); // y = 3 on [-5,5]
86	cout << "after segment add, x=2 -> " << cht.query(2) << '\n';
87
88	return 0;
89	}
90