binary_trie
クラス · 2分トライ木
template <std::integral T, int B = 31, bool Multi = false>
struct binary_trie;
概要
2分トライ木
計算量
- 要素数に依らず各操作 $O(B)$、
sizeとemptyは $O(1)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
空のtrieを構築する | $O(1)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
at |
k番目に小さい値を返す | $O(B)$ |
get |
k番目に小さい値を返す | $O(B)$ |
kth_element |
k番目に小さい値を返す | $O(B)$ |
empty |
空か返す | $O(1)$ |
size |
要素数を返す | $O(1)$ |
insert |
valを挿入する | $O(B)$ |
erase |
valを1個削除する | $O(B)$ |
min_element |
val XOR biasを最小化するvalを返す | $O(B)$ |
max_element |
val XOR biasを最大化するvalを返す | $O(B)$ |
contains |
valを含むか返す | $O(B)$ |
count_less |
val未満の要素数を返す | $O(B)$ |
count |
(1) valの個数を返す (2) 半開区間[l,r)の要素数を返す |
$O(B)$ |
lower_bound |
val未満の要素数を返す | $O(B)$ |
upper_bound |
val以下の要素数を返す | $O(B)$ |
floor |
val以下で最大の要素を返す | $O(B)$ |
ceil |
val以上で最小の要素を返す | $O(B)$ |
演算子
| 名前 | 説明 | 計算量 |
|---|---|---|
operator[] |
0-indexedでk番目に小さい値を返す | $O(B)$ |
メンバの詳細
count
// (1)
constexpr int count(T val) const;
// (2)
constexpr int count(T l, T r) const;
(1) valの個数を返す
- 計算量: $O(B)$
(2) 半開区間[l,r)の要素数を返す
- 計算量: $O(B)$