li_chao_tree
クラス · Li Chao Tree
template <class Comp = std::less<>, std::int64_t Inf = std::numeric_limits<std::int64_t>::max()>
struct li_chao_tree;
概要
Li Chao Tree
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
(1) 定義域を $[0,x_r)$ として構築する (2) 定義域を $[x_l,x_r)$ として構築する |
$O(1)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
add_line |
Add line ($ax+b$) | 定義域幅を $C$ として $O(\log C)$ |
add_segment |
Add segment ($ax+b$) | $O(\log^2 C)$ |
query |
xにおける最小値または最大値を返す | $O(\log C)$ |
メンバ型
| 名前 | 説明 | 計算量 |
|---|---|---|
line_type |
直線を表す型 | 型別名であり実行時計算量はない |
node_ptr |
ノードポインタ型 | 型別名であり実行時計算量はない |
メンバ変数
| 名前 | 説明 | 計算量 |
|---|---|---|
inf |
未登録時に返す値 | コンパイル時定数で実行時計算量はない |
メンバの詳細
(constructor)
// (1)
constexpr li_chao_tree(std::int64_t _xr);
// (2)
constexpr li_chao_tree(std::int64_t _xl, std::int64_t _xr);
(1) 定義域を $[0,x_r)$ として構築する
- 計算量: $O(1)$
(2) 定義域を $[x_l,x_r)$ として構築する
- 計算量: $O(1)$