Li Chao Tree
(convex/li_chao_tree.hpp)

View this file on GitHub
Last update: 2026-07-07 18:38:36+09:00
Include: #include "convex/li_chao_tree.hpp"

Overview

LiChaoTree<T, Objective> maintains linear functions over a fixed integral coordinate domain. Unlike the monotone-slope convex hull trick, lines may be inserted in any order.

It supports both lines over the complete domain and lines restricted to a half-open coordinate segment.

Construction

LiChaoTree(T left, T right);

The coordinate domain is [left, right). It is fixed at construction, but nodes are allocated only where insertion visits, so a large integer domain is practical.

The aliases MinLiChaoTree<T> and MaxLiChaoTree<T> select minimum and maximum queries. T must be a signed integral type.

Evaluation uses the widened type described by LinearFunction<T> in convex/convex_hull_trick.hpp.

Methods

Let $U$ be the number of integer coordinates in the domain.

Method	Description	Complexity
`add_line(slope, intercept)`	Adds a line over the complete domain.	$O(\log U)$
`add_segment(l, r, slope, intercept)`	Adds a line only over `[l, r)`.	$O(\log^2 U)$
`query(x)`	Returns the optimum at `x`, or `nullopt` if no line covers it.	$O(\log U)$
`get(x)`	Returns the optimum and requires some line to cover `x`.	$O(\log U)$
`left_bound()`, `right_bound()`	Return domain endpoints.	$O(1)$
`node_count()`	Returns allocated node count.	$O(1)$
`reserve(capacity)`	Reserves node storage.	$O(N)$
`clear()`	Removes every line while retaining the domain.	$O(N)$

Example

#include "convex/li_chao_tree.hpp"

#include <iostream>

int main() {
    m1une::convex::MinLiChaoTree<long long> tree(-1000, 1001);
    tree.add_line(2, 3);
    tree.add_line(-1, 8);
    tree.add_segment(-10, 11, 0, -5);

    long long answer = static_cast<long long>(tree.get(4));
    std::cout << answer << "\n";
}

Depends on

Convex Hull Trick (convex/convex_hull_trick.hpp)

Required by

Convex All (convex/all.hpp)

Verified with

Code

#ifndef M1UNE_CONVEX_LI_CHAO_TREE_HPP
#define M1UNE_CONVEX_LI_CHAO_TREE_HPP 1

#include <cassert>
#include <concepts>
#include <cstddef>
#include <limits>
#include <numeric>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>

#include "convex_hull_trick.hpp"

namespace m1une {
namespace convex {

// Dynamic Li Chao tree over an integral half-open coordinate domain.
template <std::signed_integral T, LineOptimization Objective = LineOptimization::Minimize>
struct LiChaoTree {
    using Line = LinearFunction<T>;
    using value_type = typename Line::value_type;

   private:
    struct Node {
        Line line;
        bool has_line;
        int left;
        int right;

        Node() : has_line(false), left(-1), right(-1) {}

        explicit Node(Line value) : line(std::move(value)), has_line(true), left(-1), right(-1) {}
    };

    T _left;
    T _right;
    int _root;
    std::vector<Node> _nodes;

    static bool better(value_type first, value_type second) {
        if constexpr (Objective == LineOptimization::Minimize) {
            return first < second;
        } else {
            return second < first;
        }
    }

    int new_node() {
        assert(_nodes.size() < std::size_t(std::numeric_limits<int>::max()));
        _nodes.emplace_back();
        return int(_nodes.size()) - 1;
    }

    int new_node(Line line) {
        assert(_nodes.size() < std::size_t(std::numeric_limits<int>::max()));
        _nodes.emplace_back(std::move(line));
        return int(_nodes.size()) - 1;
    }

    int add_line_node(int node, T left, T right, Line line) {
        if (node == -1) return new_node(std::move(line));
        if (!_nodes[node].has_line) {
            _nodes[node].line = std::move(line);
            _nodes[node].has_line = true;
            return node;
        }

        T middle = std::midpoint(left, right);
        bool left_better = better(line(left), _nodes[node].line(left));
        bool middle_better = better(line(middle), _nodes[node].line(middle));
        if (middle_better) std::swap(line, _nodes[node].line);
        if (middle == left) return node;

        if (left_better != middle_better) {
            int child = add_line_node(_nodes[node].left, left, middle, std::move(line));
            _nodes[node].left = child;
        } else {
            int child = add_line_node(_nodes[node].right, middle, right, std::move(line));
            _nodes[node].right = child;
        }
        return node;
    }

    int add_segment_node(int node, T left, T right, T query_left, T query_right, const Line& line) {
        if (query_right <= left || right <= query_left) return node;
        if (query_left <= left && right <= query_right) {
            return add_line_node(node, left, right, line);
        }
        if (node == -1) node = new_node();

        T middle = std::midpoint(left, right);
        if (middle == left) return add_line_node(node, left, right, line);
        int left_child = add_segment_node(_nodes[node].left, left, middle, query_left, query_right, line);
        int right_child = add_segment_node(_nodes[node].right, middle, right, query_left, query_right, line);
        _nodes[node].left = left_child;
        _nodes[node].right = right_child;
        return node;
    }

   public:
    LiChaoTree() : _left(0), _right(0), _root(-1) {}

    LiChaoTree(T left, T right) : _left(left), _right(right), _root(-1) {
        assert(left <= right);
    }

    T left_bound() const {
        return _left;
    }

    T right_bound() const {
        return _right;
    }

    bool empty() const {
        return _root == -1;
    }

    std::size_t node_count() const {
        return _nodes.size();
    }

    void reserve(std::size_t node_capacity) {
        _nodes.reserve(node_capacity);
    }

    void clear() {
        _root = -1;
        _nodes.clear();
    }

    void add_line(T slope, T intercept) {
        assert(_left < _right);
        _root = add_line_node(_root, _left, _right, Line(slope, intercept));
    }

    void add_segment(T segment_left, T segment_right, T slope, T intercept) {
        assert(_left <= segment_left && segment_left <= segment_right && segment_right <= _right);
        if (segment_left == segment_right) return;
        _root = add_segment_node(_root, _left, _right, segment_left, segment_right, Line(slope, intercept));
    }

    // Returns nullopt when no inserted line covers x.
    std::optional<value_type> query(T x) const {
        assert(_left <= x && x < _right);
        std::optional<value_type> result;
        int node = _root;
        T left = _left;
        T right = _right;
        while (node != -1) {
            if (_nodes[node].has_line) {
                value_type candidate = _nodes[node].line(x);
                if (!result || better(candidate, *result)) {
                    result = candidate;
                }
            }

            T middle = std::midpoint(left, right);
            if (middle == left) break;
            if (x < middle) {
                node = _nodes[node].left;
                right = middle;
            } else {
                node = _nodes[node].right;
                left = middle;
            }
        }
        return result;
    }

    value_type get(T x) const {
        std::optional<value_type> result = query(x);
        assert(result.has_value());
        return result.value_or(value_type());
    }
};

template <std::signed_integral T>
using MinLiChaoTree = LiChaoTree<T, LineOptimization::Minimize>;

template <std::signed_integral T>
using MaxLiChaoTree = LiChaoTree<T, LineOptimization::Maximize>;

}  // namespace convex
}  // namespace m1une

#endif  // M1UNE_CONVEX_LI_CHAO_TREE_HPP

#line 1 "convex/li_chao_tree.hpp"



#include <cassert>
#include <concepts>
#include <cstddef>
#include <limits>
#include <numeric>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>

#line 1 "convex/convex_hull_trick.hpp"



#line 10 "convex/convex_hull_trick.hpp"

namespace m1une {
namespace convex {

enum class LineOptimization {
    Minimize,
    Maximize,
};

template <std::signed_integral T>
using line_wide_type = __int128_t;

template <std::signed_integral T>
struct LinearFunction {
    using value_type = line_wide_type<T>;

    value_type slope;
    value_type intercept;

    constexpr LinearFunction() : slope(0), intercept(0) {}

    constexpr LinearFunction(T slope_value, T intercept_value) : slope(slope_value), intercept(intercept_value) {}

    constexpr value_type operator()(T x) const {
        return slope * value_type(x) + intercept;
    }
};

// Convex hull trick for lines inserted in nondecreasing slope order.
template <std::signed_integral T, LineOptimization Objective = LineOptimization::Minimize>
struct ConvexHullTrick {
    using Line = LinearFunction<T>;
    using value_type = typename Line::value_type;

   private:
    std::vector<Line> _lines;

    static bool better(value_type first, value_type second) {
        if constexpr (Objective == LineOptimization::Minimize) {
            return first < second;
        } else {
            return second < first;
        }
    }

    static bool redundant(const Line& first, const Line& middle, const Line& last) {
        value_type left = (first.intercept - middle.intercept) * (last.slope - middle.slope);
        value_type right = (middle.intercept - last.intercept) * (middle.slope - first.slope);
        if constexpr (Objective == LineOptimization::Minimize) {
            return left <= right;
        } else {
            return right <= left;
        }
    }

   public:
    ConvexHullTrick() = default;

    int size() const {
        return int(_lines.size());
    }

    bool empty() const {
        return _lines.empty();
    }

    const std::vector<Line>& lines() const {
        return _lines;
    }

    void reserve(std::size_t line_capacity) {
        _lines.reserve(line_capacity);
    }

    void clear() {
        _lines.clear();
    }

    // Slopes must be inserted in nondecreasing order.
    void add_line(T slope, T intercept) {
        Line line(slope, intercept);
        if (!_lines.empty()) {
            assert(_lines.back().slope <= line.slope);
        }

        if (!_lines.empty() && _lines.back().slope == line.slope) {
            if (!better(line.intercept, _lines.back().intercept)) return;
            _lines.pop_back();
        }

        while (_lines.size() >= 2 && redundant(_lines[_lines.size() - 2], _lines.back(), line)) {
            _lines.pop_back();
        }
        _lines.push_back(line);
    }

    std::optional<value_type> try_query(T x) const {
        if (_lines.empty()) return std::nullopt;
        int low = 0;
        int high = int(_lines.size()) - 1;
        while (low < high) {
            int middle = low + (high - low) / 2;
            value_type first = _lines[middle](x);
            value_type second = _lines[middle + 1](x);
            if (better(first, second) || first == second) {
                high = middle;
            } else {
                low = middle + 1;
            }
        }
        return _lines[low](x);
    }

    value_type query(T x) const {
        assert(!empty());
        return *try_query(x);
    }
};

template <std::signed_integral T>
using MinConvexHullTrick = ConvexHullTrick<T, LineOptimization::Minimize>;

template <std::signed_integral T>
using MaxConvexHullTrick = ConvexHullTrick<T, LineOptimization::Maximize>;

}  // namespace convex
}  // namespace m1une


#line 15 "convex/li_chao_tree.hpp"

namespace m1une {
namespace convex {

// Dynamic Li Chao tree over an integral half-open coordinate domain.
template <std::signed_integral T, LineOptimization Objective = LineOptimization::Minimize>
struct LiChaoTree {
    using Line = LinearFunction<T>;
    using value_type = typename Line::value_type;

   private:
    struct Node {
        Line line;
        bool has_line;
        int left;
        int right;

        Node() : has_line(false), left(-1), right(-1) {}

        explicit Node(Line value) : line(std::move(value)), has_line(true), left(-1), right(-1) {}
    };

    T _left;
    T _right;
    int _root;
    std::vector<Node> _nodes;

    static bool better(value_type first, value_type second) {
        if constexpr (Objective == LineOptimization::Minimize) {
            return first < second;
        } else {
            return second < first;
        }
    }

    int new_node() {
        assert(_nodes.size() < std::size_t(std::numeric_limits<int>::max()));
        _nodes.emplace_back();
        return int(_nodes.size()) - 1;
    }

    int new_node(Line line) {
        assert(_nodes.size() < std::size_t(std::numeric_limits<int>::max()));
        _nodes.emplace_back(std::move(line));
        return int(_nodes.size()) - 1;
    }

    int add_line_node(int node, T left, T right, Line line) {
        if (node == -1) return new_node(std::move(line));
        if (!_nodes[node].has_line) {
            _nodes[node].line = std::move(line);
            _nodes[node].has_line = true;
            return node;
        }

        T middle = std::midpoint(left, right);
        bool left_better = better(line(left), _nodes[node].line(left));
        bool middle_better = better(line(middle), _nodes[node].line(middle));
        if (middle_better) std::swap(line, _nodes[node].line);
        if (middle == left) return node;

        if (left_better != middle_better) {
            int child = add_line_node(_nodes[node].left, left, middle, std::move(line));
            _nodes[node].left = child;
        } else {
            int child = add_line_node(_nodes[node].right, middle, right, std::move(line));
            _nodes[node].right = child;
        }
        return node;
    }

    int add_segment_node(int node, T left, T right, T query_left, T query_right, const Line& line) {
        if (query_right <= left || right <= query_left) return node;
        if (query_left <= left && right <= query_right) {
            return add_line_node(node, left, right, line);
        }
        if (node == -1) node = new_node();

        T middle = std::midpoint(left, right);
        if (middle == left) return add_line_node(node, left, right, line);
        int left_child = add_segment_node(_nodes[node].left, left, middle, query_left, query_right, line);
        int right_child = add_segment_node(_nodes[node].right, middle, right, query_left, query_right, line);
        _nodes[node].left = left_child;
        _nodes[node].right = right_child;
        return node;
    }

   public:
    LiChaoTree() : _left(0), _right(0), _root(-1) {}

    LiChaoTree(T left, T right) : _left(left), _right(right), _root(-1) {
        assert(left <= right);
    }

    T left_bound() const {
        return _left;
    }

    T right_bound() const {
        return _right;
    }

    bool empty() const {
        return _root == -1;
    }

    std::size_t node_count() const {
        return _nodes.size();
    }

    void reserve(std::size_t node_capacity) {
        _nodes.reserve(node_capacity);
    }

    void clear() {
        _root = -1;
        _nodes.clear();
    }

    void add_line(T slope, T intercept) {
        assert(_left < _right);
        _root = add_line_node(_root, _left, _right, Line(slope, intercept));
    }

    void add_segment(T segment_left, T segment_right, T slope, T intercept) {
        assert(_left <= segment_left && segment_left <= segment_right && segment_right <= _right);
        if (segment_left == segment_right) return;
        _root = add_segment_node(_root, _left, _right, segment_left, segment_right, Line(slope, intercept));
    }

    // Returns nullopt when no inserted line covers x.
    std::optional<value_type> query(T x) const {
        assert(_left <= x && x < _right);
        std::optional<value_type> result;
        int node = _root;
        T left = _left;
        T right = _right;
        while (node != -1) {
            if (_nodes[node].has_line) {
                value_type candidate = _nodes[node].line(x);
                if (!result || better(candidate, *result)) {
                    result = candidate;
                }
            }

            T middle = std::midpoint(left, right);
            if (middle == left) break;
            if (x < middle) {
                node = _nodes[node].left;
                right = middle;
            } else {
                node = _nodes[node].right;
                left = middle;
            }
        }
        return result;
    }

    value_type get(T x) const {
        std::optional<value_type> result = query(x);
        assert(result.has_value());
        return result.value_or(value_type());
    }
};

template <std::signed_integral T>
using MinLiChaoTree = LiChaoTree<T, LineOptimization::Minimize>;

template <std::signed_integral T>
using MaxLiChaoTree = LiChaoTree<T, LineOptimization::Maximize>;

}  // namespace convex
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Li Chao Tree
(convex/li_chao_tree.hpp)

Overview

Construction

Methods

Example

Depends on

Required by

Verified with

Code

Li Chao Tree (convex/li_chao_tree.hpp)

Overview

Construction

Methods

Example

Depends on

Required by

Verified with

Code

Li Chao Tree
(convex/li_chao_tree.hpp)