Li Chao Tree (Convex Hull Trick)
(structure/LiChaoTree.cpp)

• View this file on GitHub
• Last update: 2021-09-12 23:44:25+09:00

概要

Convex Hull Trick の Li Chao Treeで実装したバージョン

• add(a,b,l) : 登録した $x$ 座標の $[a,b)$ に線分 $l$ を追加
• query(a) : 登録した $x$ 座標の $a$ 番目を含む線分の $y$ 座標の最小値 (線分が存在しない場合はinf)

計算量

• add(a,b,l) : $O(log^2\ N)$
• query(a) : $O(log\ N)$

Depends on

• template/template.cpp

Verified with

• test/LiChaoTree.test.cpp

Code

#pragma once
#include "../template/template.cpp"

template <class T>
struct LiChaoTree {
    struct L {
        T a, b;
        L(T a, T b) : a(a), b(b) {}
        bool operator==(L l) { return a == l.a && b == l.b; };
    };
    T f(L line, T x) {
        return line.a * x + line.b;
    }
    ll size = 1;
    L ini = {0, inf};
    vector<L> dat;
    vector<T> X;
    void add(ll a, ll b, L li, ll k = 0, ll l = 0, ll r = -1) {
        if (r == -1) r = size;
        if (r <= a || b <= l) return;
        ll m = (l + r) / 2;
        if (!(a <= l && r <= b)) {
            add(a, b, li, 2 * k + 1, l, m);
            add(a, b, li, 2 * k + 2, m, r);
            return;
        }
        if (dat[k] == ini) {
            dat[k] = li;
            return;
        }
        ll lx = X[l], mx = X[m], rx = X[r - 1];
        bool left = f(li, lx) < f(dat[k], lx);
        bool mid = f(li, mx) < f(dat[k], mx);
        bool right = f(li, rx) < f(dat[k], rx);

        if (left && right) {
            dat[k] = li;
            return;
        }
        if (!left && !right) return;
        if (mid) swap(li, dat[k]);
        if (left != mid) {
            add(a, b, li, 2 * k + 1, l, m);
        } else {
            add(a, b, li, 2 * k + 2, m, r);
        }
    }
    T query(ll a, ll k = 0, ll l = 0, ll r = -1) {
        if (r == -1) r = size;
        if (r - l == 1) return f(dat[k], X[a]);
        if (a < (l + r) / 2)
            return min(query(a, k * 2 + 1, l, (l + r) / 2), f(dat[k], X[a]));
        else
            return min(query(a, k * 2 + 2, (l + r) / 2, r), f(dat[k], X[a]));
    }
    LiChaoTree(vector<T> v) : X(v) {
        ll N = len(v);
        while (size < N) size *= 2;
        dat.resize(size * 2 - 1, ini);
        X.resize(size * 2 - 1, 1e9);
    }
};
/*
@brief Li Chao Tree (Convex Hull Trick)
@docs docs/LiChaoTree.md
*/

#line 2 "template/template.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
#define REP(i, n) for (int i = 1; i < n; i++)
#define rev(i, n) for (int i = n - 1; i >= 0; i--)
#define REV(i, n) for (int i = n - 1; i > 0; i--)
#define all(v) v.begin(), v.end()
#define PL pair<ll, ll>
#define PI pair<int, int>
#define pi acos(-1)
#define len(s) (int)s.size()
#define compress(v) \
    sort(all(v));   \
    v.erase(unique(all(v)), v.end());
#define comid(v, x) lower_bound(all(v), x) - v.begin()

template<class T>
using prique=priority_queue<T,vector<T>,greater<>>;

template <class T, class U>
inline bool chmin(T &a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T, class U>
inline bool chmax(T &a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
constexpr ll inf = 3e18;
#line 3 "structure/LiChaoTree.cpp"

template <class T>
struct LiChaoTree {
    struct L {
        T a, b;
        L(T a, T b) : a(a), b(b) {}
        bool operator==(L l) { return a == l.a && b == l.b; };
    };
    T f(L line, T x) {
        return line.a * x + line.b;
    }
    ll size = 1;
    L ini = {0, inf};
    vector<L> dat;
    vector<T> X;
    void add(ll a, ll b, L li, ll k = 0, ll l = 0, ll r = -1) {
        if (r == -1) r = size;
        if (r <= a || b <= l) return;
        ll m = (l + r) / 2;
        if (!(a <= l && r <= b)) {
            add(a, b, li, 2 * k + 1, l, m);
            add(a, b, li, 2 * k + 2, m, r);
            return;
        }
        if (dat[k] == ini) {
            dat[k] = li;
            return;
        }
        ll lx = X[l], mx = X[m], rx = X[r - 1];
        bool left = f(li, lx) < f(dat[k], lx);
        bool mid = f(li, mx) < f(dat[k], mx);
        bool right = f(li, rx) < f(dat[k], rx);

        if (left && right) {
            dat[k] = li;
            return;
        }
        if (!left && !right) return;
        if (mid) swap(li, dat[k]);
        if (left != mid) {
            add(a, b, li, 2 * k + 1, l, m);
        } else {
            add(a, b, li, 2 * k + 2, m, r);
        }
    }
    T query(ll a, ll k = 0, ll l = 0, ll r = -1) {
        if (r == -1) r = size;
        if (r - l == 1) return f(dat[k], X[a]);
        if (a < (l + r) / 2)
            return min(query(a, k * 2 + 1, l, (l + r) / 2), f(dat[k], X[a]));
        else
            return min(query(a, k * 2 + 2, (l + r) / 2, r), f(dat[k], X[a]));
    }
    LiChaoTree(vector<T> v) : X(v) {
        ll N = len(v);
        while (size < N) size *= 2;
        dat.resize(size * 2 - 1, ini);
        X.resize(size * 2 - 1, 1e9);
    }
};
/*
@brief Li Chao Tree (Convex Hull Trick)
@docs docs/LiChaoTree.md
*/

Back to top page