Li Chao Tree
(data-structure/cht/li_chao_tree.hpp)

• View this file on GitHub
• Last update: 2024-01-08 01:32:22+09:00
• Include: #include "data-structure/cht/li_chao_tree.hpp"

Description

Li Chao tree は，直線及び線分の集合をセグメント木で管理し，与えられた $x$ 座標での最小値を取得するデータ構造である．

Operations

• LiChaoTree(vector<T> xs)
  • クエリに用いる $x$ 座標を受け取り，Li Chao tree を構築する
  • 時間計算量: $O(n)$
• void add_line(T a, T b)
  • 直線 $y = ax + b$ を追加する
  • 時間計算量: $O(\log n)$
• void add_segment(T a, T b, T xl, T xr)
  • 線分 $y = ax + b \quad (x \in [x_l, x_r))$ を追加する
  • 時間計算量: $O(\log^2 n)$
• T get(T x)
  • $x$ での最小値を取得する
  • 時間計算量: $O(\log n)$

Reference

• Li Chao Treeのメモ

Verified with

• test/yosupo/line_add_get_min.lct.test.cpp
• test/yosupo/segment_add_get_min.test.cpp

Code

#pragma once
#include <algorithm>
#include <bit>
#include <limits>
#include <utility>
#include <vector>

template <typename T>
class LiChaoTree {
   public:
    LiChaoTree() = default;
    explicit LiChaoTree(const std::vector<T>& vs) : xs(vs) {
        std::ranges::sort(xs);
        xs.erase(std::ranges::unique(xs).begin(), xs.end());
        size = std::bit_ceil(xs.size());
        node.resize(2 * size, {0, INF});
        while ((int)xs.size() <= size) xs.push_back(xs.back() + 1);
    }

    void add_line(T a, T b) { update({a, b}, 1, 0, size); }

    void add_segment(T a, T b, T xl, T xr) {
        int l = std::ranges::lower_bound(xs, xl) - xs.begin();
        int r = std::ranges::lower_bound(xs, xr) - xs.begin();

        Line line(a, b);
        int len = 1;
        int l0 = l, r0 = r;
        for (l += size, r += size; l < r; l >>= 1, r >>= 1, len <<= 1) {
            if (l & 1) {
                update(line, l++, l0, l0 + len);
                ++l;
                l0 += len;
            }
            if (r & 1) {
                --r;
                r0 -= len;
                update(line, r, r0, r0 + len);
            }
        }
    }

    T get(T x) const {
        int k = std::ranges::lower_bound(xs, x) - xs.begin();
        k += size;
        T res = node[k](x);
        while (k >>= 1) res = std::min(res, node[k](x));
        return res;
    }

   private:
    struct Line {
        T a, b;
        Line(T a, T b) : a(a), b(b) {}
        T operator()(T x) const { return a * x + b; }
    };

    static constexpr T INF = std::numeric_limits<T>::max();

    int size;
    std::vector<T> xs;
    std::vector<Line> node;

    void update(Line line, int k, int l, int r) {
        while (true) {
            int m = std::midpoint(l, r);
            bool left = line(xs[l]) < node[k](xs[l]);
            bool mid = line(xs[m]) < node[k](xs[m]);
            bool right = line(xs[r]) < node[k](xs[r]);

            if (!left && !right) break;
            if (left && right) {
                node[k] = line;
                break;
            }
            if (mid) std::swap(node[k], line);
            if (r - l == 1) break;
            if (left != mid) {
                k = 2 * k;
                r = m;
            } else {
                k = 2 * k + 1;
                l = m;
            }
        }
    }
};

#line 2 "data-structure/cht/li_chao_tree.hpp"
#include <algorithm>
#include <bit>
#include <limits>
#include <utility>
#include <vector>

template <typename T>
class LiChaoTree {
   public:
    LiChaoTree() = default;
    explicit LiChaoTree(const std::vector<T>& vs) : xs(vs) {
        std::ranges::sort(xs);
        xs.erase(std::ranges::unique(xs).begin(), xs.end());
        size = std::bit_ceil(xs.size());
        node.resize(2 * size, {0, INF});
        while ((int)xs.size() <= size) xs.push_back(xs.back() + 1);
    }

    void add_line(T a, T b) { update({a, b}, 1, 0, size); }

    void add_segment(T a, T b, T xl, T xr) {
        int l = std::ranges::lower_bound(xs, xl) - xs.begin();
        int r = std::ranges::lower_bound(xs, xr) - xs.begin();

        Line line(a, b);
        int len = 1;
        int l0 = l, r0 = r;
        for (l += size, r += size; l < r; l >>= 1, r >>= 1, len <<= 1) {
            if (l & 1) {
                update(line, l++, l0, l0 + len);
                ++l;
                l0 += len;
            }
            if (r & 1) {
                --r;
                r0 -= len;
                update(line, r, r0, r0 + len);
            }
        }
    }

    T get(T x) const {
        int k = std::ranges::lower_bound(xs, x) - xs.begin();
        k += size;
        T res = node[k](x);
        while (k >>= 1) res = std::min(res, node[k](x));
        return res;
    }

   private:
    struct Line {
        T a, b;
        Line(T a, T b) : a(a), b(b) {}
        T operator()(T x) const { return a * x + b; }
    };

    static constexpr T INF = std::numeric_limits<T>::max();

    int size;
    std::vector<T> xs;
    std::vector<Line> node;

    void update(Line line, int k, int l, int r) {
        while (true) {
            int m = std::midpoint(l, r);
            bool left = line(xs[l]) < node[k](xs[l]);
            bool mid = line(xs[m]) < node[k](xs[m]);
            bool right = line(xs[r]) < node[k](xs[r]);

            if (!left && !right) break;
            if (left && right) {
                node[k] = line;
                break;
            }
            if (mid) std::swap(node[k], line);
            if (r - l == 1) break;
            if (left != mid) {
                k = 2 * k;
                r = m;
            } else {
                k = 2 * k + 1;
                l = m;
            }
        }
    }
};

Back to top page