OrderedSet

クラス · 順序集合・多重集合（AVL 木）

template <class T, bool Multi = false>
struct OrderedSet;

概要

順序集合・多重集合（AVL 木）

計算量

検索・更新・順位・区間和は $O(\log n)$

構築・破棄

名前	説明	計算量
`(constructor)`	(1) 空集合を構築する (2) 列vの要素から構築する	(1) $O(1)$ (2) $O(n\log n)$

メンバ関数

名前	説明	計算量
`empty`	空か返す	$O(1)$
`size`	要素数を返す	$O(1)$
`insert`	valを挿入する	$O(\log n)$
`erase`	valを1個削除する	$O(\log n)$
`pop_front`	最小要素を削除する	$O(\log n)$
`pop_back`	最大要素を削除する	$O(\log n)$
`front`	最小要素を返す	$O(\log n)$
`back`	最大要素を返す	$O(\log n)$
`at`	0-indexedでk番目に小さい要素を返す	$O(\log n)$
`count`	valの個数を返す	$O(\log n)$
`contains`	valを含むか返す	$O(\log n)$
`lower_bound`	val未満の要素数を返す	$O(\log n)$
`upper_bound`	val以下の要素数を返す	$O(\log n)$
`floor`	val以下で最大の要素を返す	$O(\log n)$
`ceil`	val以上で最小の要素を返す	$O(\log n)$
`prefix_sum`	小さい方からk個の総和を返す	$O(\log n)$
`suffix_sum`	大きい方からk個の総和を返す	$O(\log n)$

メンバ型

名前	説明	計算量
`node_type`	内部ノード型	型エイリアスで実行時計算量はない
`node_ptr`	内部ノードへのpointer型	型エイリアスで実行時計算量はない

メンバの詳細

(constructor)

// (1)
constexpr OrderedSet();

// (2)
constexpr OrderedSet(std::vector<T> v);

(1) 空集合を構築する

計算量: $O(1)$

(2) 列vの要素から構築する

計算量: $O(n\log n)$