convex hull trick
(include/emthrm/dynamic_programming/convex_hull_trick.hpp)

• View this file on GitHub
• Last update: 2023-02-23 21:59:12+09:00
• Include: #include "emthrm/dynamic_programming/convex_hull_trick.hpp"

$xy$ 平面上の直線集合 $L$ を考える。

• $L$ に直線 $f(x) = ax + b$ を追加する。
• ある $x$ に対して $\min \lbrace f(x) \mid f \in L \rbrace$ を答える。

上のクエリを高速に処理できるテクニックである。

時間計算量

クエリ	時間計算量
追加クエリ	amortized $O(1)$
解答クエリ	$O(\log{N})$
$x$ に単調性のある解答クエリ	amortized $O(1)$

仕様

template <typename T, bool IS_MINIMIZED = true>
struct ConvexHullTrick

• T
• IS_MINIMIZED：最小化するかを表す変数

メンバ関数

名前	効果・戻り値	要件
ConvexHullTrick();	デフォルトコンストラクタ
void add(T a, T b);	直線 $f(x) = ax + b$ を追加する。	傾きには単調性がある。
T query(const T x) const;	$\min \text{/} \max \lbrace f(x) \mid f \in L \rbrace$
T monotonically_increasing_query(const T x);	query(x)	$x$ は単調増加する。
T monotonically_decreasing_query(const T x);	query(x)	$x$ は単調減少する。

参考文献

• http://satanic0258.hatenablog.com/entry/2016/08/16/181331
• https://ei1333.github.io/luzhiled/snippets/structure/convex-hull-trick-add-monotone.html

TODO

• 直線を削除できる。
  • https://lumakernel.github.io/ecasdqina/dynamic-programming/convex-hull-trick/RemovableCHT
  • https://codeforces.com/blog/entry/60514
  • オフライン版
    • https://mugen1337.github.io/procon/DataStructure/DeletableLiChaoTreeOffline.cpp
    • https://sotanishy.github.io/cp-library-cpp/data-structure/cht/offline_deletable_convex_hull_trick.cpp.html
• 追加する直線の傾きに単調性が必要ない。
  • https://sune2.hatenadiary.org/entry/20140310/1394440369
  • https://lumakernel.github.io/ecasdqina/dynamic-programming/convex-hull-trick/CHT-Ex
• $x \in \mathbb{Z}$
  • https://noshi91.hatenablog.com/entry/2021/03/23/200810
  • https://judge.yosupo.jp/submission/35152
• 永続 convex full trick
  • https://codeforces.com/blog/entry/51684
• $\min_i \lbrace A_i x + B_i y \rbrace$
  • https://twitter.com/maspy_stars/status/1502589106039123970
  • 第41回TechFUL Coding Battle「最大値はいくつ？」
  • https://atcoder.jp/contests/abc244/tasks/abc244_h

Submissons

• query(x)
• monotonically_increasing_query(x)
• monotonically_decreasing_query(x)

Verified with

• 動的計画法/convex full trick (test/dynamic_programming/convex_hull_trick.1.test.cpp)
• 動的計画法/convex full trick（$x$ が単調増加する解答クエリ） (test/dynamic_programming/convex_hull_trick.2.test.cpp)
• 動的計画法/convex full trick（$x$ が単調減少する解答クエリ） (test/dynamic_programming/convex_hull_trick.3.test.cpp)

Code

#ifndef EMTHRM_DYNAMIC_PROGRAMMING_CONVEX_HULL_TRICK_HPP_
#define EMTHRM_DYNAMIC_PROGRAMMING_CONVEX_HULL_TRICK_HPP_

#include <cassert>
#include <deque>
#include <iterator>
#include <numeric>
#include <utility>

namespace emthrm {

template <typename T, bool IS_MINIMIZED = true>
struct ConvexHullTrick {
  ConvexHullTrick() = default;

  void add(T a, T b) {
    if constexpr (!IS_MINIMIZED) {
      a = -a;
      b = -b;
    }
    const Line line(a, b);
    if (deq.empty()) [[unlikely]] {
      deq.emplace_back(line);
    } else if (deq.back().first >= a) {
      if (deq.back().first == a) {
        if (b >= deq.back().second) return;
        deq.pop_back();
      }
      for (int i = std::ssize(deq) - 2; i >= 0; --i) {
        if (!must_pop(deq[i], deq[i + 1], line)) break;
        deq.pop_back();
      }
      deq.emplace_back(line);
    } else {
      if (deq.front().first == a) {
        if (b >= deq.front().second) return;
        deq.pop_front();
      }
      while (deq.size() >= 2 && must_pop(line, deq.front(), deq[1])) {
        deq.pop_front();
      }
      deq.emplace_front(line);
    }
  }

  T query(const T x) const {
    assert(!deq.empty());
    int lb = -1, ub = deq.size() - 1;
    while (ub - lb > 1) {
      const int mid = std::midpoint(lb, ub);
      (f(deq[mid], x) < f(deq[mid + 1], x) ? ub : lb) = mid;
    }
    return IS_MINIMIZED ? f(deq[ub], x) : -f(deq[ub], x);
  }

  T monotonically_increasing_query(const T x) {
    while (deq.size() >= 2 && f(deq.front(), x) >= f(deq[1], x)) {
      deq.pop_front();
    }
    return IS_MINIMIZED ? f(deq.front(), x) : -f(deq.front(), x);
  }

  T monotonically_decreasing_query(const T x) {
    for (int i = std::ssize(deq) - 2; i >= 0; --i) {
      if (f(deq[i], x) > f(deq[i + 1], x)) break;
      deq.pop_back();
    }
    return IS_MINIMIZED ? f(deq.back(), x) : -f(deq.back(), x);
  }

 private:
  using Line = std::pair<T, T>;

  std::deque<Line> deq;

  bool must_pop(const Line& l1, const Line& l2, const Line& l3) const {
#ifdef __SIZEOF_INT128__
    const T lhs_num = l3.second - l2.second, lhs_den = l2.first - l3.first;
    const T rhs_num = l2.second - l1.second, rhs_den = l1.first - l2.first;
    return __int128{lhs_num} * rhs_den <= __int128{rhs_num} * lhs_den;
#else
    const long double lhs =
        static_cast<long double>(l3.second - l2.second) / (l2.first - l3.first);
    const long double rhs =
        static_cast<long double>(l2.second - l1.second) / (l1.first - l2.first);
    return lhs <= rhs;
#endif  // __SIZEOF_INT128__
  }

  T f(const Line& l, const T x) const { return l.first * x + l.second; }
};

}  // namespace emthrm

#endif  // EMTHRM_DYNAMIC_PROGRAMMING_CONVEX_HULL_TRICK_HPP_

#line 1 "include/emthrm/dynamic_programming/convex_hull_trick.hpp"



#include <cassert>
#include <deque>
#include <iterator>
#include <numeric>
#include <utility>

namespace emthrm {

template <typename T, bool IS_MINIMIZED = true>
struct ConvexHullTrick {
  ConvexHullTrick() = default;

  void add(T a, T b) {
    if constexpr (!IS_MINIMIZED) {
      a = -a;
      b = -b;
    }
    const Line line(a, b);
    if (deq.empty()) [[unlikely]] {
      deq.emplace_back(line);
    } else if (deq.back().first >= a) {
      if (deq.back().first == a) {
        if (b >= deq.back().second) return;
        deq.pop_back();
      }
      for (int i = std::ssize(deq) - 2; i >= 0; --i) {
        if (!must_pop(deq[i], deq[i + 1], line)) break;
        deq.pop_back();
      }
      deq.emplace_back(line);
    } else {
      if (deq.front().first == a) {
        if (b >= deq.front().second) return;
        deq.pop_front();
      }
      while (deq.size() >= 2 && must_pop(line, deq.front(), deq[1])) {
        deq.pop_front();
      }
      deq.emplace_front(line);
    }
  }

  T query(const T x) const {
    assert(!deq.empty());
    int lb = -1, ub = deq.size() - 1;
    while (ub - lb > 1) {
      const int mid = std::midpoint(lb, ub);
      (f(deq[mid], x) < f(deq[mid + 1], x) ? ub : lb) = mid;
    }
    return IS_MINIMIZED ? f(deq[ub], x) : -f(deq[ub], x);
  }

  T monotonically_increasing_query(const T x) {
    while (deq.size() >= 2 && f(deq.front(), x) >= f(deq[1], x)) {
      deq.pop_front();
    }
    return IS_MINIMIZED ? f(deq.front(), x) : -f(deq.front(), x);
  }

  T monotonically_decreasing_query(const T x) {
    for (int i = std::ssize(deq) - 2; i >= 0; --i) {
      if (f(deq[i], x) > f(deq[i + 1], x)) break;
      deq.pop_back();
    }
    return IS_MINIMIZED ? f(deq.back(), x) : -f(deq.back(), x);
  }

 private:
  using Line = std::pair<T, T>;

  std::deque<Line> deq;

  bool must_pop(const Line& l1, const Line& l2, const Line& l3) const {
#ifdef __SIZEOF_INT128__
    const T lhs_num = l3.second - l2.second, lhs_den = l2.first - l3.first;
    const T rhs_num = l2.second - l1.second, rhs_den = l1.first - l2.first;
    return __int128{lhs_num} * rhs_den <= __int128{rhs_num} * lhs_den;
#else
    const long double lhs =
        static_cast<long double>(l3.second - l2.second) / (l2.first - l3.first);
    const long double rhs =
        static_cast<long double>(l2.second - l1.second) / (l1.first - l2.first);
    return lhs <= rhs;
#endif  // __SIZEOF_INT128__
  }

  T f(const Line& l, const T x) const { return l.first * x + l.second; }
};

}  // namespace emthrm

Back to top page