merge_sort_tree

クラス · merge-sort tree

template <class T>
struct merge_sort_tree;

概要

merge-sort tree

構築・破棄

メンバ関数

メンバの詳細

(constructor)

// (1)
merge_sort_tree() = default;

// (2)
template <class U>
explicit merge_sort_tree(const std::vector<U> &v);

(1) 空のmerge-sort treeを構築する

• 計算量: $O(1)$

(2) 列からmerge-sort treeを構築する

• 計算量: 要素数を $n$ として時間・空間ともに $O(n\log n)$

rank

// (1)
int rank(int r, T x) const;

// (2)
int rank(int l, int r, T x) const;

(1)

count i s.t. (0 <= i < r) && v[i] == x

• 計算量: $O(\log^2 n)$

(2)

count i s.t. (l <= i < r) && v[i] == x

• 計算量: $O(\log^2 n)$

range_freq

// (1)
int range_freq(int l, int r, T upper) const;

// (2)
int range_freq(int l, int r, T lower, T upper) const;

(1)

count i s.t. (l <= i < r) && (v[i] < upper)

• 計算量: $O(\log^2 n)$

(2)

count i s.t. (l <= i < r) && (lower <= v[i] < upper)

• 計算量: $O(\log^2 n)$