Convex Hull Trick (Li Chao Tree)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Line {
    ll m, c;
    Line(ll m = 0, ll c = LLONG_MAX) : m(m), c(c) {}
    ll eval(ll x) { return m * x + c; }
};

struct LiChao {
    struct Node {
        Line line;
        Node *L, *R;
        Node(Line l = Line()) : line(l), L(nullptr), R(nullptr) {}
    };

    Node* root;
    ll lo, hi;

    LiChao(ll lo, ll hi) : lo(lo), hi(hi), root(new Node()) {}

    void addLine(Line nw) { addLine(root, lo, hi, nw); }

    ll query(ll x) { return query(root, lo, hi, x); }

private:
    void addLine(Node* nd, ll l, ll r, Line nw) {
        ll mid = l + (r - l) / 2;
        bool lBetter = nw.eval(l) < nd->line.eval(l);
        bool mBetter = nw.eval(mid) < nd->line.eval(mid);
        if (mBetter) swap(nd->line, nw);
        if (l == r) return;
        if (lBetter != mBetter) {
            if (!nd->L) nd->L = new Node();
            addLine(nd->L, l, mid, nw);
        } else {
            if (!nd->R) nd->R = new Node();
            addLine(nd->R, mid + 1, r, nw);
        }
    }

    ll query(Node* nd, ll l, ll r, ll x) {
        if (!nd) return LLONG_MAX;
        ll res = nd->line.eval(x);
        if (l == r) return res;
        ll mid = l + (r - l) / 2;
        if (x <= mid) return min(res, query(nd->L, l, mid, x));
        return min(res, query(nd->R, mid + 1, r, x));
    }
};