βš™οΈAlgorithmAdvanced

Convex Hull Trick - Dynamic (LineContainer)

Key Points

  • β€’
    Dynamic Convex Hull Trick (LineContainer) maintains the lower or upper envelope of lines y = m x + b with O(log n) insertion and O(log n) query for arbitrary insertion order.
  • β€’
    It stores lines ordered by slope and keeps only the lines that can be optimal somewhere, removing dominated lines via intersection checks.
  • β€’
    Queries binary-search the precomputed breakpoints (x-values where one line overtakes the next) to find the best line for a given x.
  • β€’
    For integer problems, use floor-division with care and 128-bit intermediates to avoid overflow and rounding bugs.
  • β€’
    To get minimum values, either implement a min-hull directly or store negated lines in a max-hull and negate query results.
  • β€’
    Floating-point versions are simpler but can suffer from precision issues; prefer exact integer arithmetic when possible.
  • β€’
    Li Chao Tree is an alternative with the same asymptotic complexity but easier to adapt to constrained x-domains and segment updates.
  • β€’
    Common pitfalls include mishandling duplicate slopes, wrong floor-division for negatives, mixing min/max conventions, and assuming monotonic-query optimizations apply during dynamic insertions.

Prerequisites

  • β†’Balanced binary search trees (ordered sets) β€” LineContainer stores lines in slope order and uses lower_bound; understanding BST operations clarifies O(log n).
  • β†’Basic geometry of lines β€” Slope, intercept, and intersections are the backbone of CHT logic.
  • β†’Asymptotic complexity (Big-O) β€” To reason about why insertions and queries are O(log n).
  • β†’Integer arithmetic and floor division β€” Exact integer breakpoints require correct handling of negatives and overflow.
  • β†’Dynamic programming basics β€” Most applications of CHT are DP recurrences of linear form.
  • β†’Floating-point precision β€” Necessary to judge when long double is safe and when integer math is preferable.

Detailed Explanation

Tap terms for definitions

01Overview

The Dynamic Convex Hull Trick (CHT), often implemented as a LineContainer, is a data structure that maintains a set of linear functions y = m x + b and supports fast queries for the minimum or maximum value at a given x. Unlike the simpler deque-based CHT that requires slopes (or query x’s) to be monotonic, the dynamic version allows arbitrary insertion order of lines and arbitrary query order. It achieves this by storing lines sorted by slope and computing, for each kept line, the x-coordinate at which it stops being better than the next line. These x-coordinates (breakpoints) let us binary-search to find the optimal line for any x. Practically, the structure behaves like the geometric lower (for min-queries) or upper (for max-queries) envelope of many lines. When a new line is inserted, the LineContainer checks whether it is dominated everywhere or if it makes some existing lines useless; dominated lines are removed. Queries then evaluate the corresponding optimal line at x. In competitive programming, the dynamic CHT appears in DP optimizations of the form dp[i] = min_j (m_j x_i + c_j), where m_j and c_j depend on earlier states and x_i is known per i. It gives O(log n) per add/query, typically fast enough for n up to 2e5–5e5. An alternative is the Li Chao tree, which handles range-limited x efficiently and is robust with arbitrary insert/query orders, but the LineContainer is often simpler and faster for pure set-of-lines queries.

02Intuition & Analogies

Imagine many straight sticks (lines) laid over a table. For any position x on the table, you want the stick that lies lowest (minimum) or highest (maximum) at that x. If you look from above, the visible outline formed by the lowest sticks is the lower envelope; by the highest sticks, the upper envelope. Any stick that’s never visible is irrelevant because it’s always above (for min) or below (for max) others. The LineContainer keeps only the visible sticks and the exact x-positions where the β€œvisibility” changesβ€”those are the intersections between neighboring visible sticks. If you know where each stick stops being best and the next one starts, then to answer β€œWhat’s best at x?” you simply find the last breakpoint before x and pick the corresponding stick. That’s what binary search over breakpoints does. When adding a new stick, you check where it would show up in the slope order. If the new stick lies above existing visible sticks everywhere (for min), it will never be visible, so you ignore it. If it cuts through the skyline, it will make parts of some sticks invisibleβ€”those parts beyond certain intersections disappear, meaning some lines are entirely dominated and can be removed. For integer inputs, calculating the exact intersection x can be done with careful floor-division instead of floating point. This avoids tiny rounding errors that might choose the wrong stick. For floating-point inputs, using long double is usually good enough, but you must remember that precision can bite near very close intersections.

03Formal Definition

Maintain a dynamic set S of linear functions f(x) = m x + b, with m, b in a ring (typically integers). Define the lower envelope E(x) = f(x) (for min-queries; upper envelope for max). The data structure supports: - Insert(f): βˆͺ {f}. - Query(x): return E(x) = f(x). We store lines sorted by slope and maintain, for each line β„“_i, a breakpoint such that β„“_i is optimal on an interval [, ] with , and adjacent lines in slope order cover disjoint intervals. For two lines (x) = x + and (x) = x + with , the intersection x-coordinate is = . Domination: Given lines β„“_a, β„“_b, β„“_c in slope order ( for lower envelope), line β„“_b is dominated if the intersection of (β„“_a, β„“_b) is not less than the intersection of (β„“_b, β„“_c), i.e., ; then β„“_b never attains the minimum. Queries perform a predecessor search for x among breakpoints {} to select the line. Insertions adjust local neighbors, updating breakpoints and removing newly dominated lines. Under these invariants, each operation runs in O( n) using a balanced BST keyed by slope and breakpoints.

04When to Use

Use the dynamic CHT when you must maintain a set of lines under arbitrary insertions and answer min/max queries at arbitrary x. Typical applications are DP optimizations where states contribute linear functions to future states, such as:

  • dp[i] = min_{j < i} (m_j x_i + c_j) where m_j and c_j depend on j and x_i depends on i.
  • Cost optimizations in knuth-like or slope-optimized problems when x is not monotonic.
  • Online settings where lines arrive in any order and queries interleave. Prefer the LineContainer when:
  • You only need whole-line additions (not segment-limited validity).
  • You can store lines in a set sorted by slope.
  • You want fast constant factors and exact integer correctness. Consider Li Chao Tree when:
  • x is constrained to a known domain [L, R].
  • You need to add lines active only on subsegments (segment updates).
  • You want simpler correctness with no slope ordering, at the cost of more memory and fixed coordinate bounds.

⚠️Common Mistakes

  • Mixing min and max conventions: A common pattern is implementing a max-hull and then forgetting to negate m and b for min queries, or vice versa. Provide clear addMin/queryMin wrappers to avoid confusion.
  • Mishandling duplicate slopes: With equal slopes, keep only the line with better intercept (smaller b for min, larger b for max). Failing to prune duplicates can break invariant p_i < p_{i+1}.
  • Incorrect floor-division: For integers and negative values, using a/b truncation instead of floor can shift breakpoints by 1 and lead to wrong answers. Use a correct floordiv handling signs.
  • Floating-point precision: Using double intersections in near-parallel lines can cause wrong ordering. Prefer exact integer logic with __int128 intermediates; use long double only if inputs are floating-point or magnitudes are small.
  • Assuming monotonic-query optimization: The pointer-walk O(1) query optimization only applies when no interleaved insertions happen after you start querying (or when full monotonic preconditions hold). In fully dynamic settings, stick to binary search over breakpoints.
  • Overflow on evaluation: Computing m*x + b in 64-bit may overflow even if the final answer fits conceptually. Cast to __int128 for the multiplication and addition, then clamp or assert within range before returning.
  • Forgetting domain constraints: If your x is outside the intended domain or lines are only valid on ranges, the basic LineContainer won’t enforce those; use a Li Chao tree with segments or add guards.

Key Formulas

Line Equation

Explanation: A linear (affine) function with slope m and intercept b. It maps input x to an output via scaling and shifting.

Intersection Abscissa

Explanation: The x-coordinate where two lines and intersect. It is the breakpoint where the optimal line may switch.

Lower Envelope

Explanation: The minimum value over all lines at x. Dynamic CHT maintains this by keeping only potentially optimal lines and their switch points.

Upper Envelope

Explanation: The maximum value over all lines at x. A max-hull can be converted to a min-hull by negating slopes and intercepts.

Floored Division

Explanation: Integer division rounded down toward negative infinity. Needed when computing integer breakpoints exactly for negative values.

Integer Breakpoint

Explanation: For integer queries, we store the last x where line a is at least as good as line b using floored division. This supports correct lowe semantics.

CHT DP Recurrence

Explanation: A common DP where each previous state contributes a line; querying at gives the optimal transition cost for i.

Time per Operation

Explanation: Both insertion and query take logarithmic time due to balanced BST operations and predecessor search over breakpoints.

Line Insertions Count

Explanation: Each insertion removes only a constant expected number of neighboring lines, keeping the overall maintenance efficient across n operations.

Complexity Analysis

The dynamic Convex Hull Trick (LineContainer) supports two primary operations: inserting a line and querying at a point x. Lines are kept in a balanced ordered set keyed by slope, and every kept line stores a breakpoint p marking the last x where it dominates its next neighbor. Insertion involves placing the new line in slope order (O(log n)) and then fixing local structure: computing intersections with its neighbors and removing any lines that become dominated. Each remove is a set erase (O(log n)), but a crucial amortization argument shows that across all insertions, each line is deleted at most once. Hence, the total number of deletions over n insertions is O(n), yielding O(log n) amortized time per insertion. Queries perform a binary search (lowe) over p to find the active line at x, which is O(log n). Evaluation of x + b is O(1). Therefore, both operations run in O(log n), with small constants in practice. Space complexity is O(k), where k is the number of non-dominated lines currently stored. In the worst case (all lines can be part of the envelope), so overall memory is O(n). Implementation details that affect constants: (1) Using exact integer floor-division and __int128 intermediates prevents recomputation or misordering due to precision issues. (2) Proper duplicate-slope handling (keeping only the better intercept) avoids unnecessary set entries and preserves monotone breakpoints (p strictly increasing). (3) If all lines are known in advance and queries are monotone, specialized deque-based CHT can reduce queries to O(1) amortized, but this does not generally apply when insertions interleave arbitrarily with queries. Overall, dynamic CHT reliably achieves O(log n) per operation for 2e5–5e5 scale instances common in contests.

Code Examples

Dynamic LineContainer (max-hull core) with min-hull wrappers using exact integer breakpoints
1#include <bits/stdc++.h>
2using namespace std;
3
4// Dynamic Convex Hull Trick (KACTL-style): maintains UPPER envelope (max). 
5// Use addMax/queryMax for maxima. For minima, use addMin/queryMin wrappers
6// that negate (m, b) and the answer.
7//
8// - Stores lines sorted by slope.
9// - Each line keeps 'p' = last x where this line is better than the next.
10// - Query uses lower_bound on x to find the active line.
11// - Uses floored division for exact integer breakpoints, safe with negatives.
12// - Evaluates y = m*x + b with 128-bit intermediates to avoid overflow.
13
14struct Line {
15    long long m, b;               // y = m*x + b
16    mutable long long p;          // last x where this line is better than next
17    bool operator<(const Line& o) const { return m < o.m; }
18    bool operator<(long long x) const { return p < x; } // for lower_bound with x
19};
20
21struct LineContainer : multiset<Line, less<>> {
22    static const long long INF = (1LL<<62); // sufficiently large sentinel
23
24    // Floored division a/b for signed integers. Correct for negatives.
25    static long long floordiv(long long a, long long b) {
26        assert(b != 0);
27        // floor(a/b)
28        long long q = a / b;
29        long long r = a % b;
30        if ((r != 0) && ((r > 0) != (b > 0))) --q;
31        return q;
32    }
33
34    // Update x->p given x and y (y comes after x in slope order). If y removed, return true.
35    bool isect(iterator x, iterator y) {
36        if (y == end()) { x->p = INF; return false; }
37        if (x->m == y->m) {
38            // For MAX hull: keep the larger intercept.
39            x->p = (x->b > y->b) ? INF : -INF;
40        } else {
41            // Compute last x where x is better than y (integer floor)
42            // Solve m_x*x + b_x >= m_y*x + b_y  => x >= (b_y - b_x)/(m_x - m_y)
43            x->p = floordiv(y->b - x->b, x->m - y->m);
44        }
45        return x->p >= y->p; // if true, y is useless and should be erased
46    }
47
48    // Insert line for MAX queries
49    void addMax(long long m, long long b) {
50        auto z = insert({m, b, 0});
51        auto y = z, x = y;
52        // Remove next lines that become useless
53        while (isect(y, ++z)) z = erase(z);
54        if (y != begin() && isect(--x, y)) {
55            // Current y is useless; re-link x with next
56            isect(x, y = erase(y));
57        }
58        // Fix potential previous neighbors becoming useless
59        while (y != begin()) {
60            auto x2 = x;
61            --x2;
62            if (x->p < y->p) break;
63            isect(x2, erase(x));
64            x = x2;
65        }
66    }
67
68    // Query maximum at x
69    long long queryMax(long long x) const {
70        assert(!empty());
71        auto it = lower_bound(x); // finds first line with p >= x
72        // Evaluate with 128-bit intermediate to avoid overflow
73        __int128 val = (__int128)it->m * x + it->b;
74        if (val > (__int128)LLONG_MAX) throw overflow_error("value overflows long long");
75        if (val < (__int128)LLONG_MIN) throw overflow_error("value underflows long long");
76        return (long long)val;
77    }
78
79    // Convenience wrappers for MIN queries via sign flip
80    void addMin(long long m, long long b) { addMax(-m, -b); }
81    long long queryMin(long long x) const { return -queryMax(x); }
82};
83
84int main() {
85    ios::sync_with_stdio(false);
86    cin.tie(nullptr);
87
88    LineContainer cht;
89
90    // Build a MIN hull of lines: y = 2x + 3, y = -x + 10, y = 0x + 5
91    cht.addMin(2, 3);
92    cht.addMin(-1, 10);
93    cht.addMin(0, 5);
94
95    vector<long long> xs = {-10, -1, 0, 1, 4, 10};
96    for (long long x : xs) {
97        long long ans = cht.queryMin(x);
98        cout << "min at x=" << x << " is " << ans << '\n';
99    }
100
101    // Demonstrate MAX hull directly
102    LineContainer chtMax;
103    chtMax.addMax(1, 0);  // y = x
104    chtMax.addMax(-1, 0); // y = -x
105    cout << "max at x=5 is " << chtMax.queryMax(5) << " (expects 5)\n";
106
107    return 0;
108}
109

This is a robust dynamic CHT using a multiset ordered by slope. Each stored line keeps a breakpoint p (the last x where it is at least as good as the next line). Insertion is O(log n) and removes any lines made useless. Queries lower_bound on p to select the active line and then evaluate y. The core structure maintains a MAX envelope. To support MIN queries easily, we add wrappers that negate inputs/outputs. Exact integer floor-division and __int128 intermediates prevent rounding and overflow issues.

Time: O(log n) per add and O(log n) per querySpace: O(n) for n non-dominated lines
Dynamic LineContainer with long double intersections for real-valued x (min-hull)
1#include <bits/stdc++.h>
2using namespace std;
3
4// Floating-point variant (long double) for MIN envelope.
5// Simpler to read; suitable when inputs are real-valued or magnitudes are moderate.
6// Warning: susceptible to precision error near nearly-parallel lines.
7
8struct Line {
9    long double m, b;               // y = m*x + b
10    mutable long double p;          // x-coordinate where this line stops being better than next
11    bool operator<(const Line& o) const { return m < o.m; } // slope order
12    bool operator<(long double x) const { return p < x; }   // for lower_bound(x)
13};
14
15struct LineContainerLD : multiset<Line, less<>> {
16    static constexpr long double INF = 1.0L/0.0L; // +inf
17
18    // Compute intersection x where line x becomes worse than y for MIN hull.
19    // For MIN, x is better before p, and worse after p.
20    static long double intersectX(const Line& x, const Line& y) {
21        // Assume x.m != y.m; otherwise handled separately
22        return (y.b - x.b) / (x.m - y.m);
23    }
24
25    bool isect(iterator x, iterator y) {
26        if (y == end()) { x->p = INF; return false; }
27        if (fabsl(x->m - y->m) < 1e-18L) {
28            // Equal slopes: keep smaller intercept (better for MIN)
29            x->p = (x->b <= y->b) ? INF : -INF;
30        } else {
31            x->p = intersectX(*x, *y);
32        }
33        return x->p >= y->p; // if true, y is useless
34    }
35
36    void add(long double m, long double b) {
37        auto z = insert({m, b, 0});
38        auto y = z, x = y;
39        while (isect(y, ++z)) z = erase(z);
40        if (y != begin() && isect(--x, y)) {
41            isect(x, y = erase(y));
42        }
43        while (y != begin()) {
44            auto x2 = x; --x2;
45            if (x->p < y->p) break;
46            isect(x2, erase(x));
47            x = x2;
48        }
49    }
50
51    long double query(long double x) const {
52        assert(!empty());
53        auto it = lower_bound(x);
54        return it->m * x + it->b;
55    }
56};
57
58int main() {
59    ios::sync_with_stdio(false);
60    cin.tie(nullptr);
61
62    LineContainerLD cht;
63    // Build MIN hull for floating-point slopes/intercepts
64    cht.add(0.5L, 2.0L);      // y = 0.5x + 2
65    cht.add(-1.25L, 5.0L);    // y = -1.25x + 5
66    cht.add(2.0L, -10.0L);    // y = 2x - 10
67
68    vector<long double> xs = {-5.0L, 0.0L, 2.5L, 10.0L};
69    cout.setf(std::ios::fixed); cout << setprecision(6);
70    for (auto x : xs) {
71        cout << "min at x=" << x << " is " << cht.query(x) << '\n';
72    }
73    return 0;
74}
75

This variant maintains a MIN envelope with long doubles, computing intersections via exact real division. It is straightforward and good for real-valued inputs, but can suffer from numerical issues if lines are nearly parallel or very large. For integer-heavy problems, prefer the exact-integer variant.

Time: O(log n) per add and querySpace: O(n)
DP optimization using dynamic CHT: dp[i] = min_j (a[j] * x[i] + dp[j])
1#include <bits/stdc++.h>
2using namespace std;
3
4// Reuse the integer-precise LineContainer from example 1 (max-hull with min wrappers)
5struct Line {
6    long long m, b; mutable long long p; 
7    bool operator<(const Line& o) const { return m < o.m; }
8    bool operator<(long long x) const { return p < x; }
9};
10
11struct LineContainer : multiset<Line, less<>> {
12    static const long long INF = (1LL<<62);
13    static long long floordiv(long long a, long long b) {
14        long long q = a / b, r = a % b; if ((r != 0) && ((r > 0) != (b > 0))) --q; return q;
15    }
16    bool isect(iterator x, iterator y) {
17        if (y == end()) { x->p = INF; return false; }
18        if (x->m == y->m) x->p = (x->b > y->b) ? INF : -INF; 
19        else x->p = floordiv(y->b - x->b, x->m - y->m);
20        return x->p >= y->p;
21    }
22    void addMax(long long m, long long b) {
23        auto z = insert({m, b, 0}); auto y = z, x = y;
24        while (isect(y, ++z)) z = erase(z);
25        if (y != begin() && isect(--x, y)) isect(x, y = erase(y));
26        while (y != begin()) { auto x2 = x; --x2; if (x->p < y->p) break; isect(x2, erase(x)); x = x2; }
27    }
28    void addMin(long long m, long long b) { addMax(-m, -b); }
29    long long queryMax(long long x) const { auto it = lower_bound(x); __int128 v = (__int128)it->m * x + it->b; return (long long)v; }
30    long long queryMin(long long x) const { return -queryMax(x); }
31};
32
33int main() {
34    ios::sync_with_stdio(false);
35    cin.tie(nullptr);
36
37    int n; 
38    cin >> n;
39    vector<long long> a(n), x(n), dp(n);
40    for (int i = 0; i < n; ++i) cin >> a[i]; // slopes contributed by state i
41    for (int i = 0; i < n; ++i) cin >> x[i]; // query points
42
43    // Example recurrence: dp[i] = min_{j < i} (a[j] * x[i] + dp[j])
44    LineContainer cht; 
45    // Initialize with j = 0 contributing to future states
46    dp[0] = 0; // or given base cost
47    cht.addMin(a[0], dp[0]);
48
49    for (int i = 1; i < n; ++i) {
50        // Query best transition at x[i]
51        long long best = cht.queryMin(x[i]);
52        dp[i] = best;
53        // Now state i contributes a new line for future i'
54        cht.addMin(a[i], dp[i]);
55    }
56
57    // Output dp[n-1] and optionally all dp
58    cout << dp[n-1] << '\n';
59    return 0;
60}
61

This program shows how to integrate the LineContainer into a typical DP: each previous state j contributes a line y = a[j] x + dp[j]. For each i, we query the hull at x[i] to get dp[i], then insert the new line from state i. This works even when slopes a[j] and query points x[i] are in arbitrary order.

Time: O(n log n) total for n statesSpace: O(n)
Li Chao Tree (min-hull) as an alternative on a fixed x-domain
1#include <bits/stdc++.h>
2using namespace std;
3
4// Minimal Li Chao tree for MIN queries on integer domain [L, R].
5// Supports add-line and query in O(log (R-L+1)). Useful when x is bounded
6// and you want simpler correctness regardless of slope/order.
7
8struct Line { long long m, b; long long eval(long long x) const { return m * x + b; } };
9
10struct Node {
11    Line ln; bool has; Node *l, *r;
12    Node(): ln({0, (long long)4e18}), has(false), l(nullptr), r(nullptr) {}
13};
14
15struct LiChao {
16    long long L, R; Node* root;
17    LiChao(long long L, long long R): L(L), R(R), root(new Node()) {}
18
19    void add_line(Line nw) { add_line(root, L, R, nw); }
20    long long query(long long x) const { return query(root, L, R, x); }
21
22private:
23    void add_line(Node* cur, long long l, long long r, Line nw) {
24        long long mid = l + (r - l) / 2;
25        if (!cur->has) { cur->ln = nw; cur->has = true; return; }
26        bool lef = nw.eval(l) < cur->ln.eval(l);
27        bool midb = nw.eval(mid) < cur->ln.eval(mid);
28        if (midb) swap(nw, cur->ln);
29        if (l == r) return;
30        if (lef != midb) {
31            if (!cur->l) cur->l = new Node();
32            add_line(cur->l, l, mid, nw);
33        } else {
34            if (!cur->r) cur->r = new Node();
35            add_line(cur->r, mid+1, r, nw);
36        }
37    }
38
39    long long query(Node* cur, long long l, long long r, long long x) const {
40        if (!cur || !cur->has) return (long long)4e18;
41        long long res = cur->ln.eval(x);
42        if (l == r) return res;
43        long long mid = l + (r - l) / 2;
44        if (x <= mid) return min(res, query(cur->l, l, mid, x));
45        else return min(res, query(cur->r, mid+1, r, x));
46    }
47};
48
49int main() {
50    ios::sync_with_stdio(false);
51    cin.tie(nullptr);
52
53    long long L = -1000000, R = 1000000;
54    LiChao lichao(L, R);
55    // Add lines for MIN queries
56    lichao.add_line({2, 3});     // y = 2x + 3
57    lichao.add_line({-1, 10});   // y = -x + 10
58
59    cout << lichao.query(-5) << '\n';
60    cout << lichao.query(0) << '\n';
61    cout << lichao.query(6) << '\n';
62    return 0;
63}
64

The Li Chao tree is shown for comparison. It provides the same O(log range) complexity regardless of insertion order and without maintaining slope ordering. It handles fixed domains naturally and can be extended to segment-limited lines. Use it when domain bounds are known and exact integer arithmetic is desired without floor-division subtleties.

Time: O(log (R-L+1)) per add and querySpace: O(number of created nodes), up to O(log (R-L+1)) per line in the worst case