general_li_chao_tree
(Optimization/general_li_chao_tree.hpp)

• View this file on GitHub
• Last update: 2026-11-04 14:46:41+09:00
• Include: #include "Optimization/general_li_chao_tree.hpp"

概要

一般関数 (Pairwise Single Crossing) に対応した Li Chao Tree

Dynamic 版 (座標圧縮しない)

• コンストラクタ: DynamicGeneralLiChaoTree(X xl, X xr, VAL inf = numeric_limits<VAL>::max() / 2)
  • $x$ の範囲が [xl, xr) (この幅を $X$ とする)
• 関数の挿入
  • insert(f): 関数 $f$ を挿入する。計算量 $O(\log X)$
  • insert_segment(l, r, f): 関数 $f$ を区間 $[l, r)$ の範囲内で挿入する。$O(\log^{2} X)$
• 1 点取得
  • query(x): $\min_{i} f_{i}(x)$ を返す。計算量 $O(\log X)$

Static 版 (座標圧縮するか、定義域の範囲が小さい)

制約

• 一般関数 $f_1, f_2, \dots, f_N$ が Pairwise Single Crossing であること

問題例

• Library Checker - Line Add Get Min
• Library Checker - Segment Add Get Min
• COLOCON 2018 Final C - スペースエクスプローラー高橋君
• AtCoder EDPC Z - Frog 3
• Codeforces Round 189 (Div. 1) C. Kalila and Dimna in the Logging Industry
• yukicoder No.705 ゴミ拾い Hard

参考文献

Required by

• monge_shortest_path_by_cht (Optimization/monge_shortest_path_by_cht.hpp)

Verified with

• tests/LibraryChecker_LineAddGetMin_general_li_chao_tree.test.cpp
• tests/LibraryChecker_SegmentAddGetMin_general_li_chao_tree.test.cpp
• tests/yukicoder_705_general_li_chao_tree.test.cpp
• tests/Codeforces_Round_189_Div1_C_general_li_chao_tree.cpp (manual)
• tests/EDPC_Z_general_li_chao_tree.cpp (manual)
• tests/colopl2018-final_C_general_li_chao_tree.cpp (manual)

Code

#pragma once
#include <bits/stdc++.h>
#include <cassert>
using namespace std;


// Dynamic Li Chao Tree for Pairwise Single Crossing Functions
/*
    Func: Pairwise Single Crossing 性を仮定
    注意点：i < j なる領域だけでなく、全領域での Pairwise Single Crossing 性が必要！！！

    x 座標のとりうる値の範囲: [XL, XR)
*/
template<class VAL, class FUNC, class X = long long> struct DynamicGeneralLiChaoTree {
    using Func = function<VAL(X)>;
    struct IndexedFunc {
        Func f;
        int id;
        VAL eval(X x) const { return f(x); };
    };
    struct Node {
        optional<IndexedFunc> func;
        unique_ptr<Node> left, right;
    };
    
    // inner values
    X XL, XR;
    VAL INF = numeric_limits<VAL>::max() / 2;
    int next_id = 0;
    unique_ptr<Node> root;
    
    // constructors
    DynamicGeneralLiChaoTree() {}
    DynamicGeneralLiChaoTree(X xl, X xr, VAL inf = numeric_limits<VAL>::max() / 2) : XL(xl), XR(xr), INF(inf) {
        assert(xl < xr);
    }
    static bool better(const IndexedFunc &a, const IndexedFunc &b, X x) {
        return make_pair(a.eval(x), a.id) < make_pair(b.eval(x), b.id);
    }
    void clear() {
        root.reset();
        next_id = 0;
    }

    // insert(f), in O(log X)
    void insert(unique_ptr<Node> &p, X left, X right, IndexedFunc f) {
        if (!p) p = make_unique<Node>();
        if (!p->func) {
            p->func.emplace(f);
            return;
        }
        X mid = (left + right) / 2;
        bool left_better = better(f, *p->func, left);
        bool right_better = better(f, *p->func, right - 1);

        if (!left_better && !right_better) return;
        if (left_better && right_better) {
            p->func.emplace(f);
            return;
        }
        bool mid_better = better(f, *p->func, mid);
        if (mid_better) {
            IndexedFunc old = std::move(*p->func);
            p->func.emplace(f);
            if (left_better != mid_better) insert(p->left, left, mid, old);
            else insert(p->right, mid, right, old);
        } else {
            if (left_better != mid_better) insert(p->left, left, mid, f);
            else insert(p->right, mid, right, f);
        }
    }
    int insert(Func f) {
        int id = next_id++;
        insert(root, XL, XR, IndexedFunc{std::move(f), id});
        return id;
    }

    // insert_segment(l, r, f), in O(log^2 X)
    void insert_segment(unique_ptr<Node> &p, X left, X right, X l, X r, const IndexedFunc &f) {
        if (r <= left || right <= l) return;
        if (l <= left && right <= r) {
            insert(p, left, right, f);
            return;
        }
        if (!p) p = make_unique<Node>();
        X mid = (left + right) / 2;
        insert_segment(p->left, left, mid, l, r, f);
        insert_segment(p->right, mid, right, l, r, f);
    }
    int insert_segment(X l, X r, Func f) {
        assert(XL <= l && l <= r && r <= XR);
        int id = next_id++;
        if (l != r) insert_segment(root, XL, XR, l, r, IndexedFunc{std::move(f), id});
        return id;
    }

    // query(x), in O(log X)
    pair<VAL, int> query(X x) const {
        assert(XL <= x && x < XR);
        pair<VAL, int> res{INF, -1};
        const Node *p = root.get();
        X left = XL, right = XR;
        while (p) {
            if (p->func) {
                auto cur = make_pair(p->func->eval(x), p->func->id);
                if (res.second == -1 || cur < res) res = cur;
            }
            if (right - left == 1) break;
            X mid = (left + right) / 2;
            if (x < mid) {
                p = p->left.get();
                right = mid;
            } else {
                p = p->right.get();
                left = mid;
            }
        }
        return res;
    }
};

#line 2 "Optimization/general_li_chao_tree.hpp"
#include <bits/stdc++.h>
#line 4 "Optimization/general_li_chao_tree.hpp"
using namespace std;


// Dynamic Li Chao Tree for Pairwise Single Crossing Functions
/*
    Func: Pairwise Single Crossing 性を仮定
    注意点：i < j なる領域だけでなく、全領域での Pairwise Single Crossing 性が必要！！！

    x 座標のとりうる値の範囲: [XL, XR)
*/
template<class VAL, class FUNC, class X = long long> struct DynamicGeneralLiChaoTree {
    using Func = function<VAL(X)>;
    struct IndexedFunc {
        Func f;
        int id;
        VAL eval(X x) const { return f(x); };
    };
    struct Node {
        optional<IndexedFunc> func;
        unique_ptr<Node> left, right;
    };
    
    // inner values
    X XL, XR;
    VAL INF = numeric_limits<VAL>::max() / 2;
    int next_id = 0;
    unique_ptr<Node> root;
    
    // constructors
    DynamicGeneralLiChaoTree() {}
    DynamicGeneralLiChaoTree(X xl, X xr, VAL inf = numeric_limits<VAL>::max() / 2) : XL(xl), XR(xr), INF(inf) {
        assert(xl < xr);
    }
    static bool better(const IndexedFunc &a, const IndexedFunc &b, X x) {
        return make_pair(a.eval(x), a.id) < make_pair(b.eval(x), b.id);
    }
    void clear() {
        root.reset();
        next_id = 0;
    }

    // insert(f), in O(log X)
    void insert(unique_ptr<Node> &p, X left, X right, IndexedFunc f) {
        if (!p) p = make_unique<Node>();
        if (!p->func) {
            p->func.emplace(f);
            return;
        }
        X mid = (left + right) / 2;
        bool left_better = better(f, *p->func, left);
        bool right_better = better(f, *p->func, right - 1);

        if (!left_better && !right_better) return;
        if (left_better && right_better) {
            p->func.emplace(f);
            return;
        }
        bool mid_better = better(f, *p->func, mid);
        if (mid_better) {
            IndexedFunc old = std::move(*p->func);
            p->func.emplace(f);
            if (left_better != mid_better) insert(p->left, left, mid, old);
            else insert(p->right, mid, right, old);
        } else {
            if (left_better != mid_better) insert(p->left, left, mid, f);
            else insert(p->right, mid, right, f);
        }
    }
    int insert(Func f) {
        int id = next_id++;
        insert(root, XL, XR, IndexedFunc{std::move(f), id});
        return id;
    }

    // insert_segment(l, r, f), in O(log^2 X)
    void insert_segment(unique_ptr<Node> &p, X left, X right, X l, X r, const IndexedFunc &f) {
        if (r <= left || right <= l) return;
        if (l <= left && right <= r) {
            insert(p, left, right, f);
            return;
        }
        if (!p) p = make_unique<Node>();
        X mid = (left + right) / 2;
        insert_segment(p->left, left, mid, l, r, f);
        insert_segment(p->right, mid, right, l, r, f);
    }
    int insert_segment(X l, X r, Func f) {
        assert(XL <= l && l <= r && r <= XR);
        int id = next_id++;
        if (l != r) insert_segment(root, XL, XR, l, r, IndexedFunc{std::move(f), id});
        return id;
    }

    // query(x), in O(log X)
    pair<VAL, int> query(X x) const {
        assert(XL <= x && x < XR);
        pair<VAL, int> res{INF, -1};
        const Node *p = root.get();
        X left = XL, right = XR;
        while (p) {
            if (p->func) {
                auto cur = make_pair(p->func->eval(x), p->func->id);
                if (res.second == -1 || cur < res) res = cur;
            }
            if (right - left == 1) break;
            X mid = (left + right) / 2;
            if (x < mid) {
                p = p->left.get();
                right = mid;
            } else {
                p = p->right.get();
                left = mid;
            }
        }
        return res;
    }
};

Back to top page