Treap
(data-structure/bst/treap.hpp)
Description
Treap は,平衡二分探索木の一種である.キーと別に,ランダムに割り当てられた優先度を用いてヒープ性を持たせることで,木の平衡を保つ.モノイドを扱い,セグメント木が提供する操作に加えて挿入,削除,併合,分割,区間反転が可能である.
空間計算量: $O(n)$
Operations
-
static Treap join(Treap l, Treap r)
-
l
と r
を併合する
- 時間計算量: $\mathrm{expected}\ O(\log n)$
-
pair<Treap, Treap> split(int k)
- $[0, k)$ と $[k, n)$ に分割する
- 時間計算量: $\mathrm{expected}\ O(\log n)$
-
void update(int k, T x)
- $k$ 番目の要素の値を $x$ に変更する
- 時間計算量: $\mathrm{expected}\ O(\log n)$
-
T fold(int l, int r)
- 区間 $[l, r)$ の値を fold する
- 時間計算量: $\mathrm{expected}\ O(\log n)$
-
void reverse(int l, int r)
- 区間 $[l, r)$ を反転する
- 時間計算量: $\mathrm{expected}\ O(\log n)$
-
void insert(int k, T x)
- $k$ 番目に $x$ を挿入する
- 時間計算量: $\mathrm{expected}\ O(\log n)$
-
void erase(int k)
- $k$ 番目の要素を削除する
- 時間計算量: $\mathrm{expected}\ O(\log n)$
void push_front(T x)
void push_back(T x)
void pop_front()
-
void pop_back()
- 先頭/末尾への要素の追加/削除
- 時間計算量: $\mathrm{expected}\ O(\log n)$
-
int size()
-
bool empty()
Reference
Verified with
Code
Back to top page