Dynamic Li Chao Tree (data_structure/dynamic_li_chao_tree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-05-02 07:09:43+09:00
• Include: #include "data_structure/dynamic_li_chao_tree.hpp"

Li Chao Tree は、区間内の直線群に対する最小値（または最大値）クエリを高速に処理するためのデータ構造です。ここでは、動的にノードを作成するバージョンを提供します。

テンプレートパラメータ:

• T: 直線の係数および座標の型。
• Left: 管理する区間の左端 (inclusive)。
• Right: 管理する区間の右端 (exclusive)。
• e: 最小値（または最大値）の単位元を返す関数。T e() の形式である必要があります。最小値を求める場合は十分に大きな値を、最大値を求める場合は十分に小さな値を返します。

使い方

コンストラクタ

DynamicLiChaoTree()

説明

空の Dynamic Li Chao Tree を構築します。

計算量

$O(1)$

add (直線追加)

void add(T a, T b)

説明

管理する区間 [Left, Right) 全体に直線 $y = ax + b$ を追加します。

• a: 直線の傾き。
• b: 直線の切片。

計算量

$O(\log (Right - Left))$

void add(T a, T b, T L, T R)

説明

区間 [L, R) に直線 $y = ax + b$ を追加します。

• a: 直線の傾き。
• b: 直線の切片。
• L: 直線を追加する区間の左端 (inclusive)。
• R: 直線を追加する区間の右端 (exclusive)。

制約

$Left \le L < R \le Right$

計算量

$O(\log^2 (Right - Left))$

operator() (クエリ)

T operator()(T x)

説明

座標 x における、追加された全ての直線の最小値（または最大値）を返します。

• x: クエリ座標。
• 戻り値: 座標 x における最小値（または最大値）。

制約

$Left \le x < Right$

計算量

$O(\log (Right - Left))$

Required by

• test/segment_add_get_min.test.cpp

Verified with

• test/line_add_get_min.test.cpp

Code

#pragma once
#include <memory>
#include <stack>

template <typename T, T Left, T Right, auto e>
struct DynamicLiChaoTree {
    struct node;
    using nptr = std::unique_ptr<node>;
    struct node {
        T a, b;
        nptr left{nullptr}, right{nullptr};
        node(T _a, T _b) : a(_a), b(_b) {}
        T get(T x) {
            return x * a + b;
        }
    };
    nptr root{nullptr};
    DynamicLiChaoTree() {}

    void add(T a, T b, nptr* ptr = nullptr, T l = Left, T r = Right) {
        if (!ptr) {
            ptr = &root;
        }
        while (*ptr) {
            nptr& cur = *ptr;
            T mid = (l + r) >> 1;
            T L = a * l + b;
            T M = a * mid + b;
            T R = a * (r - 1) + b;
            T cL = cur->get(l);
            T cM = cur->get(mid);
            T cR = cur->get(r - 1);
            if (cL <= L && cR <= R) {
                return;
            }
            if (L <= cL && R <= cR) {
                std::swap(cur->a, a);
                std::swap(cur->b, b);
                return;
            }
            if (L <= cL) {
                if (M <= cM) {
                    std::swap(cur->a, a);
                    std::swap(cur->b, b);
                    ptr = &cur->right;
                    l = mid;
                } else {
                    ptr = &cur->left;
                    r = mid;
                }
            } else {
                if (M <= cM) {
                    std::swap(cur->a, a);
                    std::swap(cur->b, b);
                    ptr = &cur->left;
                    r = mid;
                } else {
                    ptr = &cur->right;
                    l = mid;
                }
            }
            if (r <= l + 1) return;
        }
        if (*ptr) {
            if (a * l + b <= (*ptr)->get(l)) {
                std::swap((*ptr)->a, a);
                std::swap((*ptr)->b, b);
            }
        } else {
            *ptr = std::make_unique<node>(a, b);
        }
    }

    void add(T a, T b, T L, T R) {
        std::stack<std::tuple<nptr*, T, T>> st;
        st.emplace(&root, Left, Right);
        while (!st.empty()) {
            auto [ptr, l, r] = st.top();
            st.pop();
            if (r <= L || R <= l) continue;
            if (L <= l && r <= R) {
                add(a, b, ptr, l, r);
                continue;
            }
            if (!*ptr) {
                *ptr = std::make_unique<node>(T{0}, e());
            }
            T mid = (l + r) >> 1;
            st.emplace(&((*ptr)->left), l, mid);
            st.emplace(&((*ptr)->right), mid, r);
        }
    }

    T operator()(T x) {
        T res{e()};
        nptr* ptr = &root;
        T l{Left}, r{Right};
        while (*ptr) {
            nptr& cur = *ptr;
            res = std::min(res, cur->get(x));
            T mid = (l + r) >> 1;
            if (x < mid) {
                ptr = &cur->left;
                r = mid;
            } else {
                ptr = &cur->right;
                l = mid;
            }
        }
        return res;
    }
};

#line 2 "data_structure/dynamic_li_chao_tree.hpp"
#include <memory>
#include <stack>

template <typename T, T Left, T Right, auto e>
struct DynamicLiChaoTree {
    struct node;
    using nptr = std::unique_ptr<node>;
    struct node {
        T a, b;
        nptr left{nullptr}, right{nullptr};
        node(T _a, T _b) : a(_a), b(_b) {}
        T get(T x) {
            return x * a + b;
        }
    };
    nptr root{nullptr};
    DynamicLiChaoTree() {}

    void add(T a, T b, nptr* ptr = nullptr, T l = Left, T r = Right) {
        if (!ptr) {
            ptr = &root;
        }
        while (*ptr) {
            nptr& cur = *ptr;
            T mid = (l + r) >> 1;
            T L = a * l + b;
            T M = a * mid + b;
            T R = a * (r - 1) + b;
            T cL = cur->get(l);
            T cM = cur->get(mid);
            T cR = cur->get(r - 1);
            if (cL <= L && cR <= R) {
                return;
            }
            if (L <= cL && R <= cR) {
                std::swap(cur->a, a);
                std::swap(cur->b, b);
                return;
            }
            if (L <= cL) {
                if (M <= cM) {
                    std::swap(cur->a, a);
                    std::swap(cur->b, b);
                    ptr = &cur->right;
                    l = mid;
                } else {
                    ptr = &cur->left;
                    r = mid;
                }
            } else {
                if (M <= cM) {
                    std::swap(cur->a, a);
                    std::swap(cur->b, b);
                    ptr = &cur->left;
                    r = mid;
                } else {
                    ptr = &cur->right;
                    l = mid;
                }
            }
            if (r <= l + 1) return;
        }
        if (*ptr) {
            if (a * l + b <= (*ptr)->get(l)) {
                std::swap((*ptr)->a, a);
                std::swap((*ptr)->b, b);
            }
        } else {
            *ptr = std::make_unique<node>(a, b);
        }
    }

    void add(T a, T b, T L, T R) {
        std::stack<std::tuple<nptr*, T, T>> st;
        st.emplace(&root, Left, Right);
        while (!st.empty()) {
            auto [ptr, l, r] = st.top();
            st.pop();
            if (r <= L || R <= l) continue;
            if (L <= l && r <= R) {
                add(a, b, ptr, l, r);
                continue;
            }
            if (!*ptr) {
                *ptr = std::make_unique<node>(T{0}, e());
            }
            T mid = (l + r) >> 1;
            st.emplace(&((*ptr)->left), l, mid);
            st.emplace(&((*ptr)->right), mid, r);
        }
    }

    T operator()(T x) {
        T res{e()};
        nptr* ptr = &root;
        T l{Left}, r{Right};
        while (*ptr) {
            nptr& cur = *ptr;
            res = std::min(res, cur->get(x));
            T mid = (l + r) >> 1;
            if (x < mid) {
                ptr = &cur->left;
                r = mid;
            } else {
                ptr = &cur->right;
                l = mid;
            }
        }
        return res;
    }
};

Back to top page