Convex Hull Trick (CHT) & Li Chao Segment Tree: Optimizing dp[i] = min_j (m_j x_i + b_j)

1. Formal Invariant — Lower Envelope & Li Chao Midpoint Dominance

2. Li Chao Segment Tree Single-Branch Recursion

3. Choosing the Right Envelope Data Structure

Depending on monotonicity of inserted slopes $m_j$ and query coordinates $x_i$, four regimes arise:

1. Slopes $m_j$ monotonic + Queries $x_i$ monotonic: Use a std::deque with a moving front pointer and back-hull pruning in $O(1)$ amortized per step ($O(N)$ total).
2. Slopes $m_j$ monotonic + Queries $x_i$ arbitrary: Maintain the hull in a std::vector and binary search the optimal line at $x_i$ in $O(\log N)$ per query.
3. Slopes $m_j$ arbitrary + Queries $x_i$ arbitrary (Integer/Bounded Domain): Use a Li Chao Segment Tree (or dynamic implicit Li Chao Tree) in $O(N \log(\text{range}))$ time—completely free of division or floating-point intersection bugs!
4. Slopes $m_j$ arbitrary + Floating-Point Domain: Use KACTL's LineContainer (std::multiset ordered by slope maintaining right-intersection endpoints) in $O(N \log N)$ time.

4. Hardware & Cache Behavior

5. Complexity Matrix

6. Production-Grade C++20 Implementation (Dynamic Implicit Li Chao Tree)

#include <vector>
#include <cstdint>
#include <limits>
#include <algorithm>

class DynamicLiChaoTree {
public:
    static constexpr int64_t INF = std::numeric_limits<int64_t>::max() / 4;

    struct Line {
        int64_t m = 0;
        int64_t b = INF;
        int64_t eval(int64_t x) const { return m * x + b; }
    };

private:
    struct Node {
        Line line;
        int left = -1;
        int right = -1;
    };

    int64_t x_min_, x_max_;
    std::vector<Node> pool_;

    int new_node() {
        pool_.push_back(Node{});
        return static_cast<int>(pool_.size()) - 1;
    }

    void add_line(int u, int64_t l, int64_t r, Line nw) {
        int64_t mid = l + (r - l) / 2;
        bool left_better = nw.eval(l) < pool_[u].line.eval(l);
        bool mid_better  = nw.eval(mid) < pool_[u].line.eval(mid);

        if (mid_better) {
            std::swap(pool_[u].line, nw);
        }
        if (l == r) return;

        if (left_better != mid_better) {
            if (pool_[u].left == -1) {
                int c = new_node();
                pool_[u].left = c;
            }
            add_line(pool_[u].left, l, mid, nw);
        } else {
            if (pool_[u].right == -1) {
                int c = new_node();
                pool_[u].right = c;
            }
            add_line(pool_[u].right, mid + 1, r, nw);
        }
    }

    int64_t query(int u, int64_t l, int64_t r, int64_t x) const {
        if (u == -1) return INF;
        int64_t res = pool_[u].line.eval(x);
        if (l == r) return res;
        int64_t mid = l + (r - l) / 2;
        if (x <= mid) {
            return std::min(res, query(pool_[u].left, l, mid, x));
        } else {
            return std::min(res, query(pool_[u].right, mid + 1, r, x));
        }
    }

public:
    DynamicLiChaoTree(int64_t x_min, int64_t x_max, int reserve_nodes = 200000)
        : x_min_(x_min), x_max_(x_max) {
        pool_.reserve(reserve_nodes);
        new_node(); // root is index 0
    }

    void insert(int64_t m, int64_t b) {
        add_line(0, x_min_, x_max_, Line{m, b});
    }

    int64_t query(int64_t x) const {
        return query(0, x_min_, x_max_, x);
    }
};