patricia_binary_trie
クラス · 2分パトリシア木
template <std::integral T, int B = 31, bool Multi = false>
struct patricia_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)$ |
size |
要素数を返す | $O(1)$ |
empty |
空か返す | $O(1)$ |
insert |
valを挿入する | $O(B)$ |
erase |
valを1個削除する | $O(B)$ |
max_element |
val XOR biasを最大化するvalを返す | $O(B)$ |
min_element |
val XOR biasを最小化するvalを返す | $O(B)$ |
lower_bound |
val未満の要素数を返す | $O(B)$ |
upper_bound |
val以下の要素数を返す | $O(B)$ |
count |
valの個数を返す | $O(B)$ |
演算子
| 名前 | 説明 | 計算量 |
|---|---|---|
operator[] |
0-indexedでk番目に小さい値を返す | $O(B)$ |
メンバ型
| 名前 | 説明 | 計算量 |
|---|---|---|
node_ptr |
内部ノードへのpointer型 | 型エイリアスで実行時計算量はない |