WaveletMatrixCore
クラス · ウェーブレット行列の共通コア（各 level のビットベクトル型を差し替え可能にする）
template <class BitVector, class T, int L>
struct WaveletMatrixCore;
概要
ウェーブレット行列の共通コア（各 level のビットベクトル型を差し替え可能にする）
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
rank |
— | — |
kth_smallest |
— | — |
kth_largest |
— | — |
range_freq |
— | — |
prev_value |
— | — |
next_value |
— | — |
メンバの詳細
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
(2)
count i s.t. (l <= i < r) && v[i] == x
kth_smallest
T kth_smallest(int l, int r, int k) const;
k-th smallest number in v[l … r-1]
kth_largest
T kth_largest(int l, int r, int k) const;
k-th largest number in v[l … r-1]
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)
(2)
count i s.t. (l <= i < r) && (lower <= v[i] < upper)
prev_value
T prev_value(int l, int r, T upper) const;
max v[i] s.t. (l <= i < r) && (v[i] < upper)
next_value
T next_value(int l, int r, T lower) const;
min v[i] s.t. (l <= i < r) && (lower <= v[i])