Luzhiled's Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub ei1333/library

:heavy_check_mark: Li Chao Tree (structure/convex-hull-trick/li-chao-tree.hpp)

あらかじめ指定した $x$ 座標に対して、直線 $ax+b$ の追加と最小値クエリを効率的に処理するデータ構造。

テンプレート引数

  • T: 座標、直線の係数、および計算結果の型

記法

  • $m$: コンストラクタに渡した座標の個数
  • $n$: コンストラクタに渡した座標の重複を除いた個数

コンストラクタ

LiChaoTree(const vector<T>& x, T INF)

クエリ対象の座標を指定し、直線を含まない状態で初期化する。x は内部で昇順にソートされ、重複する座標は除かれる。

引数

  • x: クエリ対象の座標。入力時点ではソート済みでなくてもよく、重複を含んでもよい
  • INF: 直線が追加されていないときに返す値

制約

  • $1 \leq m$
  • INF はすべてのクエリ結果以上
  • 直線の値 $ax+b$ は T で表現できる

計算量

  • 時間計算量: $O(m \log m)$
  • 空間計算量: $O(n)$

update

void update(T a, T b)

直線 $ax+b$ を追加する。

引数

  • a: 直線の傾き
  • b: 直線の切片

計算量

  • $O(\log n)$

query

T query(int k)

コンストラクタに渡した座標を昇順に並べて重複を除いた列の $k$ 番目の座標における、追加済みの直線の最小値を返す。直線が追加されていない場合は INF を返す。

引数

  • k: クエリ対象の座標の添字

制約

  • $0 \leq k < n$

計算量

  • $O(\log n)$

Verified with

Code

#pragma once

#include <algorithm>
#include <iterator>
#include <utility>
#include <vector>

template <typename T>
struct LiChaoTree {
  struct Line {
    T a, b;

    Line(T a, T b) : a(a), b(b) {}

    inline T get(T x) const { return a * x + b; }

    inline bool over(const Line& b, const T& x) const {
      return get(x) < b.get(x);
    }
  };

  std::vector<T> xs;
  std::vector<Line> seg;
  int sz;

  LiChaoTree(const std::vector<T>& x, T INF) : xs(x) {
    std::sort(std::begin(xs), std::end(xs));
    xs.erase(std::unique(std::begin(xs), std::end(xs)), std::end(xs));
    sz = 1;
    while (sz < (int)xs.size()) sz <<= 1;
    while ((int)xs.size() < sz) xs.push_back(xs.back());
    seg.assign(2 * sz - 1, Line(0, INF));
  }

  void update(Line& x, int k, int l, int r) {
    int mid = (l + r) >> 1;
    auto latte = x.over(seg[k], xs[l]), malta = x.over(seg[k], xs[mid]);
    if (malta) std::swap(seg[k], x);
    if (l + 1 >= r)
      return;
    else if (latte != malta)
      update(x, 2 * k + 1, l, mid);
    else
      update(x, 2 * k + 2, mid, r);
  }

  void update(T a, T b) {  // ax+b
    Line l(a, b);
    update(l, 0, 0, sz);
  }

  T query(int k) {  // xs[k]
    const T x = xs[k];
    k += sz - 1;
    T ret = seg[k].get(x);
    while (k > 0) {
      k = (k - 1) >> 1;
      ret = std::min(ret, seg[k].get(x));
    }
    return ret;
  }
};
#line 2 "structure/convex-hull-trick/li-chao-tree.hpp"

#include <algorithm>
#include <iterator>
#include <utility>
#include <vector>

template <typename T>
struct LiChaoTree {
  struct Line {
    T a, b;

    Line(T a, T b) : a(a), b(b) {}

    inline T get(T x) const { return a * x + b; }

    inline bool over(const Line& b, const T& x) const {
      return get(x) < b.get(x);
    }
  };

  std::vector<T> xs;
  std::vector<Line> seg;
  int sz;

  LiChaoTree(const std::vector<T>& x, T INF) : xs(x) {
    std::sort(std::begin(xs), std::end(xs));
    xs.erase(std::unique(std::begin(xs), std::end(xs)), std::end(xs));
    sz = 1;
    while (sz < (int)xs.size()) sz <<= 1;
    while ((int)xs.size() < sz) xs.push_back(xs.back());
    seg.assign(2 * sz - 1, Line(0, INF));
  }

  void update(Line& x, int k, int l, int r) {
    int mid = (l + r) >> 1;
    auto latte = x.over(seg[k], xs[l]), malta = x.over(seg[k], xs[mid]);
    if (malta) std::swap(seg[k], x);
    if (l + 1 >= r)
      return;
    else if (latte != malta)
      update(x, 2 * k + 1, l, mid);
    else
      update(x, 2 * k + 2, mid, r);
  }

  void update(T a, T b) {  // ax+b
    Line l(a, b);
    update(l, 0, 0, sz);
  }

  T query(int k) {  // xs[k]
    const T x = xs[k];
    k += sz - 1;
    T ret = seg[k].get(x);
    while (k > 0) {
      k = (k - 1) >> 1;
      ret = std::min(ret, seg[k].get(x));
    }
    return ret;
  }
};
Back to top page