Convex Hull Trick & Li Chao Segment Trees: Optimizing Linear Cost DP from O(N^2) to O(N log N)

When dynamic programming recurrences involve linear transition costs of the form $dp[i] = \min_{j < i} (dp[j] + m_j \cdot x_i + c_j)$, a naive evaluation requires iterating through all preceding states $j$, producing an $O(N^2)$ overall time complexity. By interpreting each candidate state $j$ as a 2D line $y = m_j x + b_j$ and queries as points on the lower envelope, the Convex Hull Trick (CHT) and Li Chao Segment Trees optimize transition queries from linear scans to logarithmic or amortized constant time.

Geometric Interpretation of Linear Transitions

Consider the canonical dynamic programming recurrence common in batch scheduling, polygon partitioning, and resource partitioning problems:

$$dp[i] = \min_{j < i} \{ dp[j] + C(j, i) \}$$

Suppose the cost function $C(j, i)$ decomposes into a linear interaction term: $C(j, i) = m_j \cdot x_i + c_j + d_i$, where $x_i$ and $d_i$ depend solely on the current state index $i$, while $m_j$ and $c_j$ depend solely on the previous split index $j$. We can isolate the terms dependent strictly on $i$ outside the minimization:

$$dp[i] = d_i + \min_{j < i} \{ m_j \cdot x_i + (dp[j] + c_j) \}$$

If we define a collection of linear functions $f_j(x) = m_j x + b_j$, where the $y$-intercept is $b_j = dp[j] + c_j$, each prior DP state $j$ becomes a line in Cartesian space. The task of finding the optimal $j$ for state $i$ is equivalent to finding $\min_j f_j(x_i)$—evaluating the lower envelope of all lines $f_j$ at coordinate $x = x_i$.

Monotonic Convex Hull Trick: Deque Implementation

When the problem guarantees that slopes $m_j$ are generated in decreasing order ($m_1 \ge m_2 \ge \dots \ge m_k$) and the evaluation coordinates $x_i$ are monotonically non-decreasing ($x_1 \le x_2 \le \dots \le x_N$), we can maintain the lower envelope in a double-ended queue (deque) with amortized $O(1)$ operations.

1. Envelope Line Pruning (Insertion)

Let three lines in the deque be $L_1: y = m_1 x + b_1$, $L_2: y = m_2 x + b_2$, and a prospective new line $L_3: y = m_3 x + b_3$, where $m_1 > m_2 > m_3$. The intersection point $x_{intersect}(L_a, L_b)$ of two lines is given by:

$$x_{intersect}(L_a, L_b) = \frac{b_a - b_b}{m_b - m_a}$$

Line $L_2$ becomes completely irrelevant if its intersection with $L_3$ occurs to the left of (or at) its intersection with $L_1$:

$$x_{intersect}(L_2, L_3) \le x_{intersect}(L_1, L_2)$$

To avoid floating-point inaccuracies and division-by-zero risks, we clear the denominator via integer cross-multiplication:

$$(b_2 - b_3)(m_1 - m_2) \le (b_1 - b_2)(m_2 - m_3)$$

While the last two lines in the deque and the new line satisfy this domination condition, we pop the back of the deque before pushing $L_3$.

2. Query Optimization (Sliding Window)

Because query positions $x_i$ increase monotonically, the optimal segment on the envelope only shifts forward. If the first line $L_1$ at the front of the deque evaluates to a value greater than or equal to the second line $L_2$ at $x_i$ ($L_1(x_i) \ge L_2(x_i)$), line $L_1$ can never be optimal for any future query $x' \ge x_i$. We repeatedly pop the front of the deque until either only one line remains or $L_1(x_i) < L_2(x_i)$.

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

struct Line {
    long long m, b;
    long long eval(long long x) const {
        return m * x + b;
    }
};

class MonotonicCHT {
private:
    deque<Line> hull;

    // Cross multiplication: returns true if l2 is dominated by l1 and l3
    bool isDominated(const Line& l1, const Line& l2, const Line& l3) const {
        // Uses __int128_t to prevent overflow during intermediate multiplication
        __int128 lhs = (__int128)(l2.b - l3.b) * (l1.m - l2.m);
        __int128 rhs = (__int128)(l1.b - l2.b) * (l2.m - l3.m);
        return lhs <= rhs;
    }

public:
    void addLine(long long m, long long b) {
        Line newLine = {m, b};
        // If slopes are equal, keep the one with the minimal intercept for lower envelope
        if (!hull.empty() && hull.back().m == m) {
            if (hull.back().b <= b) return;
            hull.pop_back();
        }
        while (hull.size() >= 2 && isDominated(hull[hull.size() - 2], hull.back(), newLine)) {
            hull.pop_back();
        }
        hull.push_back(newLine);
    }

    long long query(long long x) {
        if (hull.empty()) return 0;
        while (hull.size() >= 2 && hull[0].eval(x) >= hull[1].eval(x)) {
            hull.pop_front();
        }
        return hull.front().eval(x);
    }
};

Arbitrary Queries with Monotonic Slopes: Binary Search

When slopes $m_j$ remain monotonic but query coordinates $x_i$ appear in arbitrary, non-monotonic order, the sliding-window front pruning cannot be used because an earlier line discarded today might be required tomorrow. However, because the sequence of intersection points between adjacent lines along the hull is strictly sorted, we can retain all lines in a vector and perform a binary search over the envelope segments in $O(\log N)$ time per query.

For a query $x$, we binary search for the first line $L_k$ whose intersection point with $L_{k+1}$ is strictly greater than $x$. That line $L_k$ minimizes the linear function at $x$.

Dynamic Lines: The Li Chao Segment Tree

The standard Convex Hull Trick breaks down when slopes $m_j$ arrive in arbitrary order. While a dynamic convex hull can be maintained using a balanced binary search tree (such as `std::multiset` in C++ with custom line iterators), implementing and debugging dynamic hulls under contest conditions is notoriously fraught with subtle corner cases, precision pitfalls, and iterator invalidation risks.

The Li Chao Tree offers an exceptionally clean, robust alternative. It is an augmented segment tree built over a coordinate range $[X_{\min}, X_{\max}]$. Each node in the tree covers an interval $[l, r]$ with midpoint $mid = \lfloor (l + r) / 2 \rfloor$ and stores a single line candidate that achieves the minimum value at $mid$.

Li Chao Tree Insertion Mechanics

When a new line $L_{new}$ is inserted into a node currently holding line $L_{old}$ over range $[l, r]$:

1. Compare $L_{new}(mid)$ with $L_{old}(mid)$. If $L_{new}(mid) < L_{old}(mid)$, $L_{new}$ is superior at the midpoint. We swap $L_{new}$ and $L_{old}$ so that the node retains the superior line at $mid$.
2. Now, $L_{old}$ is the displaced line. Because two distinct lines can intersect at most once, $L_{old}$ can only potentially surpass the current node line on either the left half $[l, mid]$ or the right half $[mid + 1, r]$, but never on both.
3. If $L_{old}(l) < L_{curr}(l)$, the intersection occurs in the left subtree; we recursively insert $L_{old}$ into the left child.
4. Otherwise, if $L_{old}(r) < L_{curr}(r)$, the intersection occurs in the right subtree; we recursively insert $L_{old}$ into the right child.
5. If neither condition holds, $L_{old}$ is dominated across the entire interval and is discarded.

Since the interval length is halved at each recursion step, insertion takes at most $O(\log(X_{\max} - X_{\min}))$ operations.

Li Chao Tree Query Mechanics

To query $\min f(x)$ at point $x$, we traverse the tree from the root down to the leaf node corresponding to coordinate $x$. At each visited node along the path, we evaluate the stored line at $x$ and track the global minimum. The query complexity is strictly $O(\log(X_{\max} - X_{\min}))$.

#include <iostream>
#include <algorithm>

using namespace std;

const long long INF = 4e18;

struct LiChaoLine {
    long long m, b;
    long long eval(long long x) const {
        return m * x + b;
    }
};

struct LiChaoNode {
    LiChaoLine line;
    LiChaoNode* left = nullptr;
    LiChaoNode* right = nullptr;
    LiChaoNode(LiChaoLine l) : line(l) {}
};

class DynamicLiChaoTree {
private:
    long long xMin, xMax;
    LiChaoNode* root = nullptr;

    void addLine(LiChaoNode*& node, long long l, long long r, LiChaoLine newLine) {
        if (!node) {
            node = new LiChaoNode(newLine);
            return;
        }
        long long mid = l + (r - l) / 2;
        bool newBeatsMid = newLine.eval(mid) < node->line.eval(mid);
        if (newBeatsMid) {
            swap(node->line, newLine);
        }
        if (l == r) return;
        if (newLine.eval(l) < node->line.eval(l)) {
            addLine(node->left, l, mid, newLine);
        } else if (newLine.eval(r) < node->line.eval(r)) {
            addLine(node->right, mid + 1, r, newLine);
        }
    }

    long long query(LiChaoNode* node, long long l, long long r, long long x) const {
        if (!node) return INF;
        long long res = node->line.eval(x);
        if (l == r) return res;
        long long mid = l + (r - l) / 2;
        if (x <= mid) {
            return min(res, query(node->left, l, mid, x));
        } else {
            return min(res, query(node->right, mid + 1, r, x));
        }
    }

public:
    DynamicLiChaoTree(long long minX, long long maxX) : xMin(minX), xMax(maxX) {}

    void addLine(long long m, long long b) {
        addLine(root, xMin, xMax, {m, b});
    }

    long long query(long long x) const {
        return query(root, xMin, xMax, x);
    }
};

Comparative Evaluation Matrix

The table below summarizes the trade-offs between dynamic programming optimization data structures for linear cost transitions:

Edge Cases and Numerical Safeguards

When implementing these optimizations in competitive programming or high-performance systems, several subtle failure modes must be guarded against:

• Integer Overflow on Evaluations: Evaluating $m \cdot x + b$ when $|m|, |x| \approx 10^9$ yields values exceeding $10^{18}$, causing standard 64-bit signed integer overflow. Always promote multiplication to `__int128_t` or cast explicitly before computing line values.
• Parallel and Duplicate Lines: When multiple candidate states produce identical slopes ($m_i = m_j$), the line with the greater $y$-intercept is strictly inferior for a lower envelope. Always discard dominated parallel lines immediately upon insertion to prevent zero division in intersection checks.
• Sparse Coordinate Spaces: When query coordinates span $[-10^9, 10^9]$, building a static array-based segment tree requires prohibitive memory. Use dynamic node allocation (pointer-based or index-allocated vectors) to instantiate only $O(\log C)$ nodes per inserted line.

Frequently Asked Questions

Below are detailed solutions to frequent technical questions encountered when optimizing linear cost dynamic programming transitions:

What is the core prerequisite for applying the Convex Hull Trick to a dynamic programming recurrence?

The recurrence must be expressible as $dp[i] = \min_{j < i} (dp[j] + m_j \cdot x_i + c_j)$ or the corresponding maximum. The cost component must decompose into a product of a state-dependent slope $m_j$ and a query coordinate $x_i$, plus an intercept term independent of $x_i$. If the transition contains higher-order cross terms like $x_i^2 \cdot j$ or non-linear functions, standard CHT cannot be applied directly without auxiliary transformations.

When should an engineer choose a Li Chao Segment Tree over a dynamic Convex Hull Trick with std::multiset?

A Li Chao Tree is preferable when line insertions arrive in arbitrary (non-monotonic) order and query coordinates are within a bounded integer domain. It eliminates geometric line-intersection math, handles parallel lines without edge-case branching, and avoids complex iterator manipulation in balanced binary search trees.

How does integer cross-multiplication prevent precision errors when checking convex hull line dominance?

Rather than calculating floating-point intersection points $x = (b_2 - b_1) / (m_1 - m_2)$ and comparing doubles, cross-multiplication verifies $(b_1 - b_2) \cdot (m_2 - m_3) \ge (b_2 - b_3) \cdot (m_1 - m_2)$ using 128-bit integers, eliminating rounding inaccuracies on large coordinate ranges.

Can a Li Chao Tree support line segments rather than infinite lines?

Yes. An extended Li Chao Tree can insert a line segment restricted to $[l, r]$ by first decomposing $[l, r]$ into $O(\log C)$ canonical segment tree nodes, and then running the standard Li Chao insertion subroutine on each node in $O(\log C)$ time, resulting in $O(\log^2 C)$ overall insertion complexity.