MergeSortTree< T > 構造体テンプレート

マージソート木 [詳解]

#include "merge_sort_tree.hpp"

公開メンバ関数
	MergeSortTree ()=default
	MergeSortTree (const vector< T > &v)
	配列 v からマージソート木を構築する
int	count_lt (int l, int r, T val)
	区間 [l, r) に存在する val 未満の値の個数を返す
int	count_le (int l, int r, T val)
	区間 [l, r) に存在する val 以下の値の個数を返す
int	count_gt (int l, int r, T val)
	区間 [l, r) に存在する val より大きい値の個数を返す
int	count_ge (int l, int r, T val)
	区間 [l, r) に存在する val 以上の値の個数を返す
T	kth (int l, int r, int k)
	区間 [l, r) の小さい方から k(1-indexed) 番目の値を返す

詳解

template<typename T>
struct MergeSortTree< T >

マージソート木

merge_sort_tree.hpp の 5 行目に定義があります。

構築子と解体子

MergeSortTree() [1/2]

template<typename T>

MergeSortTree< T >::MergeSortTree ( )

default

MergeSortTree() [2/2]

template<typename T>

MergeSortTree< T >::MergeSortTree ( const vector< T > & v )

inline

配列 v からマージソート木を構築する

merge_sort_tree.hpp の 9 行目に定義があります。

関数詳解

count_lt()

template<typename T>

int MergeSortTree< T >::count_lt ( int l, int r, T val )

inline

区間 [l, r) に存在する val 未満の値の個数を返す

覚え書き

O(log(N)^2)

merge_sort_tree.hpp の 21 行目に定義があります。

count_le()

template<typename T>

int MergeSortTree< T >::count_le ( int l, int r, T val )

inline

区間 [l, r) に存在する val 以下の値の個数を返す

覚え書き

O(log(N)^2)

merge_sort_tree.hpp の 34 行目に定義があります。

参照先 count_lt().

count_gt()

template<typename T>

int MergeSortTree< T >::count_gt ( int l, int r, T val )

inline

区間 [l, r) に存在する val より大きい値の個数を返す

覚え書き

O(log(N)^2)

merge_sort_tree.hpp の 40 行目に定義があります。

参照先 count_le().

count_ge()

template<typename T>

int MergeSortTree< T >::count_ge ( int l, int r, T val )

inline

区間 [l, r) に存在する val 以上の値の個数を返す

覚え書き

O(log(N)^2)

merge_sort_tree.hpp の 46 行目に定義があります。

参照先 count_lt().

kth()

template<typename T>

T MergeSortTree< T >::kth ( int l, int r, int k )

inline

区間 [l, r) の小さい方から k(1-indexed) 番目の値を返す

覚え書き

O(log(N)^3)

merge_sort_tree.hpp の 52 行目に定義があります。

参照先 count_lt().

---

この構造体詳解は次のファイルから抽出されました:

• data_structure/merge_sort_tree.hpp