Convex Hull Trick
(data-structure/cht/convex_hull_trick.hpp)

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

Description

Convex hull trick は，直線集合 $L$ への追加クエリと最小値クエリを効率的に行う手法である．

この実装では，追加する直線の傾きが単調非増加である必要がある．傾きに単調性がないときは平衡二分探索木を用いた CHT または Li Chao tree を使用せよ．

空間計算量: $O(n)$

Operations

• T add(T a, T b)
  • 直線 $ax + b$ を $L$ に追加する
  • 時間計算量: $\mathrm{amortized}\ O(1)$
• T get(T x)
  • 与えられた $x$ に対し，$L$ の中で最小値を取る直線の値を求める
  • 時間計算量: $\mathrm{amortized}\ O(1)$

Reference

• Convex-Hull Trick

Code

#pragma once
#include <algorithm>
#include <deque>
#include <utility>
#include <vector>

template <typename T>
class ConvexHullTrick {
   public:
    void add(T a, T b) {
        Line line(a, b);
        while (lines.size() >= 2 &&
               check(*(lines.end() - 2), lines.back(), line)) {
            lines.pop_back();
        }
        lines.push_back(line);
    }

    T get(T x) {
        while (lines.size() >= 2 && lines.front()(x) > lines[1](x)) {
            lines.pop_front();
        }
        return lines.front()(x);
    }

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

    std::deque<Line> lines;

    static bool check(Line l1, Line l2, Line l3) {
        if (l1.a == l2.a) return l2.b >= l1.b;
        if (l2.a == l3.a) return l2.b >= l3.b;
        return 1.0 * (l2.b - l1.b) / (l2.a - l1.a) <=
               1.0 * (l3.b - l2.b) / (l3.a - l2.a);
    }
};

#line 2 "data-structure/cht/convex_hull_trick.hpp"
#include <algorithm>
#include <deque>
#include <utility>
#include <vector>

template <typename T>
class ConvexHullTrick {
   public:
    void add(T a, T b) {
        Line line(a, b);
        while (lines.size() >= 2 &&
               check(*(lines.end() - 2), lines.back(), line)) {
            lines.pop_back();
        }
        lines.push_back(line);
    }

    T get(T x) {
        while (lines.size() >= 2 && lines.front()(x) > lines[1](x)) {
            lines.pop_front();
        }
        return lines.front()(x);
    }

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

    std::deque<Line> lines;

    static bool check(Line l1, Line l2, Line l3) {
        if (l1.a == l2.a) return l2.b >= l1.b;
        if (l2.a == l3.a) return l2.b >= l3.b;
        return 1.0 * (l2.b - l1.b) / (l2.a - l1.a) <=
               1.0 * (l3.b - l2.b) / (l3.a - l2.a);
    }
};

Back to top page