ds/li_chao_tree.hpp

• View this file on GitHub
• Last update: 2021-06-07 23:09:50-04:00
• Include: #include "ds/li_chao_tree.hpp"

Verified with

• tests/ds/li_chao_tree.test.cpp

Code

template <typename T> struct Line {
    T m, b;
    Line(T m0, T b0) : m(m0), b(b0) {}
    T eval(T x) { return x * m + b; }
};
template <typename T, ll MINX = (ll)-1e6, ll MAXX = (ll)1e6> struct LiChaoTree { // Just *-1 if you want to do max lol
    using line = Line<T>;
    struct Node {
        Node *l = nullptr, *r = nullptr;
        line val{0, LLINF};
        Node(Node *l0, Node *r0, line v0) : l(l0), r(r0), val(v0) {}
    };
    Node *rt = nullptr;
    void _insert(line ln, Node *&n, ll l, ll r) {
        if (l > r) return;
        if (!n) {
            n = new Node(nullptr, nullptr, ln);
            return;
        }
        ll mid = (l + r) / 2;
        bool lDom = ln.eval(l) < n->val.eval(l), mDom = ln.eval(mid) < n->val.eval(mid);
        if (mDom) swap(ln, n->val);
        if (l == r) return; // base case
        if (lDom != mDom) _insert(ln, n->l, l, mid);
        else _insert(ln, n->r, mid + 1, r);
    }
    ll _query(ll x, Node *n, ll l, ll r) {
        if (!n) return LLINF;
        ll res = n->val.eval(x), mid = (l + r) / 2;
        if (l != r) {
            if (x < mid) res = min(res, _query(x, n->l, l, mid));
            else res = min(res, _query(x, n->r, mid + 1, r));
        }
        return res;
    }
    void insert(line ln) { _insert(ln, rt, MINX, MAXX); }
    ll query(ll x) { return _query(x, rt, MINX, MAXX); }
};

#line 1 "ds/li_chao_tree.hpp"
template <typename T> struct Line {
    T m, b;
    Line(T m0, T b0) : m(m0), b(b0) {}
    T eval(T x) { return x * m + b; }
};
template <typename T, ll MINX = (ll)-1e6, ll MAXX = (ll)1e6> struct LiChaoTree { // Just *-1 if you want to do max lol
    using line = Line<T>;
    struct Node {
        Node *l = nullptr, *r = nullptr;
        line val{0, LLINF};
        Node(Node *l0, Node *r0, line v0) : l(l0), r(r0), val(v0) {}
    };
    Node *rt = nullptr;
    void _insert(line ln, Node *&n, ll l, ll r) {
        if (l > r) return;
        if (!n) {
            n = new Node(nullptr, nullptr, ln);
            return;
        }
        ll mid = (l + r) / 2;
        bool lDom = ln.eval(l) < n->val.eval(l), mDom = ln.eval(mid) < n->val.eval(mid);
        if (mDom) swap(ln, n->val);
        if (l == r) return; // base case
        if (lDom != mDom) _insert(ln, n->l, l, mid);
        else _insert(ln, n->r, mid + 1, r);
    }
    ll _query(ll x, Node *n, ll l, ll r) {
        if (!n) return LLINF;
        ll res = n->val.eval(x), mid = (l + r) / 2;
        if (l != r) {
            if (x < mid) res = min(res, _query(x, n->l, l, mid));
            else res = min(res, _query(x, n->r, mid + 1, r));
        }
        return res;
    }
    void insert(line ln) { _insert(ln, rt, MINX, MAXX); }
    ll query(ll x) { return _query(x, rt, MINX, MAXX); }
};

Back to top page