xiv. Convex Hull Trick

For transitions $d{p}_i={\min }_{j<i}(m_j{x}_i+c_j)+g(i)$, each earlier state is a line and the query is the lower envelope at $x_i$. Recognise it by expanding the cost: whatever multiplies a function of $j$ by a function of $i$ is slope × query point. Example: $d{p}_i={\min }_{j}d{p}_j+(a_i-a_j{)}^2$ gives slope $-2a_j$, intercept $d{p}_j+a_j^2$, point $a_i$, plus $a_i^2$.

Slopes inserted	Queries	Structure	Cost
monotone	monotone	deque, pop from the front	$O(n)$
monotone	arbitrary	deque/stack + binary search	$O(n\log n)$
arbitrary	arbitrary	Li Chao tree (Li Chao) or LineContainer	$O(n\log C)$ / $O(n\log n)$
arbitrary, offline	arbitrary	CDQ on index + monotone hull inside	$O(n{\log }^{2}n)$
lines with a validity range of $i$	arbitrary	Li Chao with segment insertion, or segment tree over time	$O(n{\log }^{2}n)$
lines with deletions, offline	arbitrary	segment tree over time + Li Chao with rollback	$O(n{\log }^{2}n)$
on a tree (lines from ancestors)	arbitrary	persistent Li Chao, or monotone hull with rollback during DFS	$O(n\log n)$

Monotone hull (min, slopes decreasing, queries increasing)

struct MonoCHT {
    deque<pair<ll, ll>> h;                                  // (slope, intercept), slopes strictly decreasing
    static bool bad(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c) {   // b never strictly below min(a, c)
        return (__int128)(c.second - a.second) * (a.first - b.first) <= (__int128)(b.second - a.second) * (a.first - c.first);
    }
    void add(ll m, ll c) {
        if (sz(h) && h.back().first == m) { if (h.back().second <= c) return; h.pop_back(); }
        while (sz(h) >= 2 && bad(h[sz(h) - 2], h.back(), {m, c})) h.pop_back();
        h.push_back({m, c});
    }
    ll at(int i, ll x) const { return h[i].first * x + h[i].second; }
    ll query(ll x) { while (sz(h) >= 2 && at(0, x) >= at(1, x)) h.pop_front(); return at(0, x); }
    ll queryAny(ll x) const {                               // arbitrary x: binary search on the envelope
        int lo = 0, hi = sz(h) - 1;
        while (lo < hi) { int mid = (lo + hi) / 2; if (at(mid, x) >= at(mid + 1, x)) lo = mid + 1; else hi = mid; }
        return at(lo, x);
    }
};

For max, negate slopes and intercepts (or flip the comparisons). If slopes arrive increasing, mirror $x\to -x$.

Proof: the removal test and the pointer

For the minimum, as $x$ increases the optimal line’s slope decreases, so the envelope lists lines by decreasing slope. Take $m_a>m_b>m_c$ and let $x_{ab}$, $x_{ac}$ be the intersection abscissas. $b$ is below $a$ only for $x>x_{ab}$ and below $c$ only for $x<x_{bc}$. If $x_{ac}\le x_{ab}$: for $x\ge x_{ab}$ we have $x\ge x_{ac}$, so $c\le a$ there, and at $x_{ab}$, $b=a\ge c$; since $c$ decreases faster than $b$ afterwards, $c\le b$ on all of $x\ge x_{ab}$. So $b$ is never strictly below both, and removing it is safe. Clearing denominators ($m_a-m_b>0$, $m_a-m_c>0$) gives the integer test. The surviving lines have increasing breakpoints, so each line is optimal on an interval, and for nondecreasing queries a line popped from the front is never optimal again: amortised $O(1)$. __int128 is needed because the products reach $10^{18}\cdot 10^9$.

Fully dynamic: line container

A multiset of lines sorted by slope, each storing the $x$ where it stops being optimal; inserting removes dominated neighbours. Query by binary searching the breakpoints. (Max version; for min insert $(-k,-m)$ and negate.)

struct Line { mutable ll k, m, p; bool operator<(const Line& o) const { return k < o.k; } bool operator<(ll x) const { return p < x; } };
struct LineContainer : multiset<Line, less<>> {
    static const ll INF = LLONG_MAX;
    static ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
    bool isect(iterator x, iterator y) {                    // set x->p; true if y is now useless
        if (y == end()) return x->p = INF, false;
        if (x->k == y->k) x->p = x->m > y->m ? INF : -INF;
        else x->p = fdiv(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(ll k, ll m) {
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
    }
    ll query(ll x) const { auto l = *lower_bound(x); return l.k * x + l.m; }
};

Proof sketch: breakpoints of the upper envelope

Lines are kept sorted by slope; for the maximum, the envelope uses them in increasing slope order as $x$ grows, and line $\ell$ is optimal on $(p_{\text{prev}},p_{\ell }]$, where $p_{\ell }=\lfloor$ intersection with the next line $\rfloor$ (integer queries). A line is useless iff its interval is empty, i.e. $p_{\text{prev}}\ge p_{\ell }$. After inserting a line, only its neighbours’ breakpoints change: the loop removes following lines that it dominates, then checks whether the new line itself is useless, then removes preceding lines that became useless. Each line is inserted and erased at most once, so the total is $O(n\log n)$. Floor division keeps the comparison exact for integer queries.

Variations

• Two-parameter costs $d{p}_i={\min }_{j}d{p}_j+b_j{a}_i+c_i$ with an extra constraint $j\in [l_i,r_i)$: segment tree of hulls (each node a static hull of its lines), $O(n{\log }^{2}n)$.
• Divide and conquer (CDQ) on the index when slopes or queries aren’t monotone but you want deque speed: solve the left half, build a hull of its lines sorted by slope, answer the right half’s queries sorted by $x$, recurse.
• “Add a line, query a point” with per-element growth (values grow linearly with time): kinetic segment tree (KST).
• Functions that cross at most once (not just lines): Li Chao works unchanged.
• When the transition is ${\min }_{j}d{p}_j+w(j,i)$ with $w$ Monge but not linear, use the monotone-queue / divide-and-conquer machinery instead (Monotone Optimizations).