Li Chao segment tree (tools/li_chao_segtree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-02-10 20:05:30+09:00
• Include: #include "tools/li_chao_segtree.hpp"

It is a data structure which supports the following operations.

• Add a straight line $y = ax + b$.
• Add a line segment $y = ax + b\,(l \leq x \leq r)$.
• Find the maximal or minimal $y$ at given $x$.

It is required to give a predefined list of possible $x$s to a constructor.

License

• CC0

Author

• anqooqie

Constructor

template <typename Iterator>
li_chao_segtree<T> segtree(Iterator begin, Iterator end, bool maximal);

It creates an empty set of straight lines and line segments. The elements from begin to end represent possible $x$s. If maximal is true, it will calculate the maximal $y$ at given $x$. If maximal is false, it will calculate the minimal $y$ at given $x$.

Constraints

• $\mathrm{begin} \leq \mathrm{end}$
• The elements from begin to end are sorted.

Time Complexity

• $O(n)$ where $n$ is $\mathrm{end} - \mathrm{begin}$

add

(1) void segtree.add(T a, T b);
(2) void segtree.add(T a, T b, T l, T r);

• (1) It adds a straight line $y = ax + b$ to the set.
• (2) It adds a line segment $y = ax + b\,(l \leq x \leq r)$ to the set.

Constraints

• None

Time Complexity

• (1): $O(\log n)$ where $n$ is $\mathrm{end} - \mathrm{begin}$
• (2): $O((\log n)^2)$ where $n$ is $\mathrm{end} - \mathrm{begin}$

query

T segtree.query(T x);

If maximal was true, it returns

\[\begin{align*} \left\{\begin{array}{ll} \text{the maximal $y$ at given $x$} & \text{(if the maximal exists.)}\\ \mathrm{std::numeric\_limits<T>::min()} & \text{(if the maximal does not exist.)} \end{array}\right.& \end{align*}\]

If maximal was false, it returns

\[\begin{align*} \left\{\begin{array}{ll} \text{the minimal $y$ at given $x$} & \text{(if the minimal exists.)}\\ \mathrm{std::numeric\_limits<T>::max()} & \text{(if the minimal does not exist.)} \end{array}\right.& \end{align*}\]

Constraints

• $x$ is in the predefined list of possible $x$s.

Time Complexity

• $O(\log n)$ where $n$ is $\mathrm{end} - \mathrm{begin}$

Depends on

• Bit width required to represent a given integer (tools/bit_width.hpp)
• $\left\lceil \log_2(x) \right\rceil$ (tools/ceil_log2.hpp)
• $\left\lfloor \log_2(x) \right\rfloor$ (tools/floor_log2.hpp)
• std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
• std::is_signed extended for tools::int128_t and tools::uint128_t (tools/is_signed.hpp)
• std::lower_bound, but returns index (tools/lower_bound.hpp)
• std::make_unsigned extended for tools::int128_t and tools::uint128_t (tools/make_unsigned.hpp)
• $2^x$ (tools/pow2.hpp)

Verified with

• tests/li_chao_segtree/line.test.cpp
• tests/li_chao_segtree/segment.test.cpp

Code

#ifndef TOOLS_LI_CHAO_SEGTREE_HPP
#define TOOLS_LI_CHAO_SEGTREE_HPP

#include <vector>
#include <cstddef>
#include <utility>
#include <limits>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <iterator>
#include "tools/pow2.hpp"
#include "tools/floor_log2.hpp"
#include "tools/ceil_log2.hpp"
#include "tools/pow2.hpp"
#include "tools/lower_bound.hpp"

namespace tools {
  template <typename T>
  class li_chao_segtree {
  private:
    bool m_maximal;
    ::std::vector<T> m_xs;
    ::std::size_t m_height;
    ::std::vector<::std::pair<T, T>> m_nodes;

    ::std::size_t capacity() const {
      return this->m_nodes.size() / 2;
    }

    bool comp(const T& x, const T& y) const {
      return this->m_maximal ? x < y : y < x;
    }

    void add_impl(T fa, T fb, ::std::size_t node_id) {
      assert(::tools::floor_log2(node_id) <= this->m_height);
      ::std::size_t l = (node_id - ::tools::pow2(::tools::floor_log2(node_id))) * ::tools::pow2(this->m_height - ::tools::floor_log2(node_id));
      ::std::size_t r = l + ::tools::pow2(this->m_height - ::tools::floor_log2(node_id));
      while (node_id < this->m_nodes.size()) {
        const ::std::size_t m = (l + r) / 2;
        auto& [ga, gb] = this->m_nodes[node_id];
        bool greater_l = this->comp(ga * this->m_xs[l] + gb, fa * this->m_xs[l] + fb);
        bool greater_m = this->comp(ga * this->m_xs[m] + gb, fa * this->m_xs[m] + fb);
        bool greater_r = this->comp(ga * this->m_xs[r] + gb, fa * this->m_xs[r] + fb);
        if (greater_l == greater_m && greater_m == greater_r) {
          if (greater_l) {
            ::std::swap(fa, ga);
            ::std::swap(fb, gb);
          }
          return;
        }
        if (greater_m) {
          ::std::swap(fa, ga);
          ::std::swap(fb, gb);
          greater_l = !greater_l;
          greater_m = !greater_m;
          greater_r = !greater_r;
        }
        if (greater_l) {
          node_id = node_id * 2;
          r = m;
        } else {
          node_id = node_id * 2 + 1;
          l = m;
        }
      }
    }

  public:
    template <typename Iterator>
    li_chao_segtree(const Iterator& begin, const Iterator& end, const bool maximal) :
      m_maximal(maximal),
      m_xs(begin, end),
      m_height(this->m_xs.empty() ? ::std::numeric_limits<T>::min() : ::tools::ceil_log2(this->m_xs.size())),
      m_nodes(this->m_xs.empty() ? 0 : ::tools::pow2(this->m_height + 1), ::std::pair<T, T>(0, maximal ? ::std::numeric_limits<T>::min() : ::std::numeric_limits<T>::max())) {
      if (this->m_xs.empty()) return;

      assert(::std::is_sorted(this->m_xs.begin(), this->m_xs.end()));
      const ::std::size_t n = this->m_xs.size();
      this->m_xs.resize(this->capacity() + 1);
      ::std::iota(this->m_xs.begin() + n, this->m_xs.end(), this->m_xs[n - 1] + 1);
    }

    li_chao_segtree() = default;
    li_chao_segtree(const ::tools::li_chao_segtree<T>&) = default;
    li_chao_segtree(::tools::li_chao_segtree<T>&&) = default;
    ~li_chao_segtree() = default;
    ::tools::li_chao_segtree<T>& operator=(const ::tools::li_chao_segtree<T>&) = default;
    ::tools::li_chao_segtree<T>& operator=(::tools::li_chao_segtree<T>&&) = default;

    void add(const T& a, const T& b) {
      if (this->m_xs.empty()) return;

      this->add_impl(a, b, 1);
    }

    void add(const T& a, const T& b, const T& l, const T& r) {
      if (this->m_xs.empty()) return;

      auto l_id = ::tools::lower_bound(this->m_xs.begin(), ::std::prev(this->m_xs.end()), l);
      auto r_id = ::tools::lower_bound(this->m_xs.begin(), ::std::prev(this->m_xs.end()), r);
      if (r_id == ::std::ssize(this->m_xs) - 1 || r < this->m_xs[r_id]) --r_id;
      if (r_id < l_id) return;
      l_id += this->capacity();
      r_id += this->capacity() + 1;

      for (; l_id < r_id; l_id >>= 1, r_id >>= 1) {
        if (l_id & 1) {
          this->add_impl(a, b, l_id);
          ++l_id;
        }
        if (r_id & 1) {
          --r_id;
          this->add_impl(a, b, r_id);
        }
      }
    }

    T query(const T& x) const {
      const auto it = ::std::lower_bound(this->m_xs.begin(), this->m_xs.end(), x);
      assert(*it == x);
      const ::std::size_t node_id = this->capacity() + ::std::distance(this->m_xs.begin(), it);

      T answer = this->m_maximal ? ::std::numeric_limits<T>::min() : ::std::numeric_limits<T>::max();
      for (::std::size_t h = this->m_height + 1; h --> 0;) {
        const auto& [fa, fb] = this->m_nodes[node_id >> h];
        if (this->comp(answer, fa * x + fb)) {
          answer = fa * x + fb;
        }
      }
      
      return answer;
    }
  };
}

#endif

#line 1 "tools/li_chao_segtree.hpp"



#include <vector>
#include <cstddef>
#include <utility>
#include <limits>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <iterator>
#line 1 "tools/pow2.hpp"



#include <type_traits>
#line 6 "tools/pow2.hpp"

namespace tools {

  template <typename T, typename ::std::enable_if<::std::is_unsigned<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(1) << x;
  }

  template <typename T, typename ::std::enable_if<::std::is_signed<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(static_cast<typename ::std::make_unsigned<T>::type>(1) << static_cast<typename ::std::make_unsigned<T>::type>(x));
  }
}


#line 1 "tools/floor_log2.hpp"



#line 1 "tools/bit_width.hpp"



#include <bit>
#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 1 "tools/is_signed.hpp"



#line 5 "tools/is_signed.hpp"

namespace tools {
  template <typename T>
  struct is_signed : ::std::is_signed<T> {};

  template <typename T>
  inline constexpr bool is_signed_v = ::tools::is_signed<T>::value;
}


#line 1 "tools/make_unsigned.hpp"



#line 5 "tools/make_unsigned.hpp"

namespace tools {
  template <typename T>
  struct make_unsigned : ::std::make_unsigned<T> {};

  template <typename T>
  using make_unsigned_t = typename ::tools::make_unsigned<T>::type;
}


#line 10 "tools/bit_width.hpp"

namespace tools {
  template <typename T>
  constexpr int bit_width(T) noexcept;

  template <typename T>
  constexpr int bit_width(const T x) noexcept {
    static_assert(::tools::is_integral_v<T> && !::std::is_same_v<::std::remove_cv_t<T>, bool>);
    if constexpr (::tools::is_signed_v<T>) {
      assert(x >= 0);
      return ::tools::bit_width<::tools::make_unsigned_t<T>>(x);
    } else {
      return ::std::bit_width(x);
    }
  }
}


#line 6 "tools/floor_log2.hpp"

namespace tools {
  template <typename T>
  constexpr T floor_log2(T x) noexcept {
    assert(x > 0);
    return ::tools::bit_width(x) - 1;
  }
}


#line 1 "tools/ceil_log2.hpp"



#line 6 "tools/ceil_log2.hpp"

namespace tools {
  template <typename T>
  constexpr T ceil_log2(T x) noexcept {
    assert(x > 0);
    return ::tools::bit_width(x - 1);
  }
}


#line 1 "tools/lower_bound.hpp"



#line 6 "tools/lower_bound.hpp"

namespace tools {

  template <class ForwardIterator, class T>
  auto lower_bound(ForwardIterator first, ForwardIterator last, const T& value) {
    return ::std::distance(first, ::std::lower_bound(first, last, value));
  }

  template <class ForwardIterator, class T, class Compare>
  auto lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp) {
    return ::std::distance(first, ::std::lower_bound(first, last, value, comp));
  }
}


#line 17 "tools/li_chao_segtree.hpp"

namespace tools {
  template <typename T>
  class li_chao_segtree {
  private:
    bool m_maximal;
    ::std::vector<T> m_xs;
    ::std::size_t m_height;
    ::std::vector<::std::pair<T, T>> m_nodes;

    ::std::size_t capacity() const {
      return this->m_nodes.size() / 2;
    }

    bool comp(const T& x, const T& y) const {
      return this->m_maximal ? x < y : y < x;
    }

    void add_impl(T fa, T fb, ::std::size_t node_id) {
      assert(::tools::floor_log2(node_id) <= this->m_height);
      ::std::size_t l = (node_id - ::tools::pow2(::tools::floor_log2(node_id))) * ::tools::pow2(this->m_height - ::tools::floor_log2(node_id));
      ::std::size_t r = l + ::tools::pow2(this->m_height - ::tools::floor_log2(node_id));
      while (node_id < this->m_nodes.size()) {
        const ::std::size_t m = (l + r) / 2;
        auto& [ga, gb] = this->m_nodes[node_id];
        bool greater_l = this->comp(ga * this->m_xs[l] + gb, fa * this->m_xs[l] + fb);
        bool greater_m = this->comp(ga * this->m_xs[m] + gb, fa * this->m_xs[m] + fb);
        bool greater_r = this->comp(ga * this->m_xs[r] + gb, fa * this->m_xs[r] + fb);
        if (greater_l == greater_m && greater_m == greater_r) {
          if (greater_l) {
            ::std::swap(fa, ga);
            ::std::swap(fb, gb);
          }
          return;
        }
        if (greater_m) {
          ::std::swap(fa, ga);
          ::std::swap(fb, gb);
          greater_l = !greater_l;
          greater_m = !greater_m;
          greater_r = !greater_r;
        }
        if (greater_l) {
          node_id = node_id * 2;
          r = m;
        } else {
          node_id = node_id * 2 + 1;
          l = m;
        }
      }
    }

  public:
    template <typename Iterator>
    li_chao_segtree(const Iterator& begin, const Iterator& end, const bool maximal) :
      m_maximal(maximal),
      m_xs(begin, end),
      m_height(this->m_xs.empty() ? ::std::numeric_limits<T>::min() : ::tools::ceil_log2(this->m_xs.size())),
      m_nodes(this->m_xs.empty() ? 0 : ::tools::pow2(this->m_height + 1), ::std::pair<T, T>(0, maximal ? ::std::numeric_limits<T>::min() : ::std::numeric_limits<T>::max())) {
      if (this->m_xs.empty()) return;

      assert(::std::is_sorted(this->m_xs.begin(), this->m_xs.end()));
      const ::std::size_t n = this->m_xs.size();
      this->m_xs.resize(this->capacity() + 1);
      ::std::iota(this->m_xs.begin() + n, this->m_xs.end(), this->m_xs[n - 1] + 1);
    }

    li_chao_segtree() = default;
    li_chao_segtree(const ::tools::li_chao_segtree<T>&) = default;
    li_chao_segtree(::tools::li_chao_segtree<T>&&) = default;
    ~li_chao_segtree() = default;
    ::tools::li_chao_segtree<T>& operator=(const ::tools::li_chao_segtree<T>&) = default;
    ::tools::li_chao_segtree<T>& operator=(::tools::li_chao_segtree<T>&&) = default;

    void add(const T& a, const T& b) {
      if (this->m_xs.empty()) return;

      this->add_impl(a, b, 1);
    }

    void add(const T& a, const T& b, const T& l, const T& r) {
      if (this->m_xs.empty()) return;

      auto l_id = ::tools::lower_bound(this->m_xs.begin(), ::std::prev(this->m_xs.end()), l);
      auto r_id = ::tools::lower_bound(this->m_xs.begin(), ::std::prev(this->m_xs.end()), r);
      if (r_id == ::std::ssize(this->m_xs) - 1 || r < this->m_xs[r_id]) --r_id;
      if (r_id < l_id) return;
      l_id += this->capacity();
      r_id += this->capacity() + 1;

      for (; l_id < r_id; l_id >>= 1, r_id >>= 1) {
        if (l_id & 1) {
          this->add_impl(a, b, l_id);
          ++l_id;
        }
        if (r_id & 1) {
          --r_id;
          this->add_impl(a, b, r_id);
        }
      }
    }

    T query(const T& x) const {
      const auto it = ::std::lower_bound(this->m_xs.begin(), this->m_xs.end(), x);
      assert(*it == x);
      const ::std::size_t node_id = this->capacity() + ::std::distance(this->m_xs.begin(), it);

      T answer = this->m_maximal ? ::std::numeric_limits<T>::min() : ::std::numeric_limits<T>::max();
      for (::std::size_t h = this->m_height + 1; h --> 0;) {
        const auto& [fa, fb] = this->m_nodes[node_id >> h];
        if (this->comp(answer, fa * x + fb)) {
          answer = fa * x + fb;
        }
      }
      
      return answer;
    }
  };
}

Back to top page