WaveletMatrix

クラス · ウェーブレット行列

template <class T, int L = 20>
struct WaveletMatrix : internal::WaveletMatrixCore<internal::bit_vector, T, L>;

概要

ウェーブレット行列

計算量

構築は $O(nL)$、各問い合わせは $O(L)$

構築・破棄

名前	説明	計算量
`(constructor)`	(1) 空のウェーブレット行列を作る (2) 列 `v` からウェーブレット行列を構築する	(1) $O(1)$ (2) $O(nL)$

メンバ関数

名前	説明	計算量
`access`	`k` 番目の値を返す	$O(L)$
`rank`	(1) $0 \le i < r$ かつ $v_i=x$ を満たす要素数を返す (2) $l \le i < r$ かつ $v_i=x$ を満たす要素数を返す	$O(L)$
`kth_smallest`	区間 $[l,r)$ 内で `k` 番目に小さい値を返す（0-indexed）	$O(L)$
`kth_largest`	区間 $[l,r)$ 内で `k` 番目に大きい値を返す（0-indexed）	$O(L)$
`range_freq`	(1) 区間 $[l,r)$ にある `upper` 未満の要素数を返す (2) 区間 $[l,r)$ にある $[lower,upper)$ 内の要素数を返す	$O(L)$
`prev_value`	区間 $[l,r)$ にある `upper` 未満の最大値を返す	$O(L)$
`next_value`	区間 $[l,r)$ にある `lower` 以上の最小値を返す	$O(L)$

演算子

名前	説明	計算量
`operator[]`	`access(k)` の別名	$O(L)$

メンバ型

名前	説明	計算量
`Base`	共通実装の基底型	型エイリアスのため実行時コストなし
`length`	要素数を保持する基底クラスのメンバ	$O(1)$ で参照可能
`matrix`	各レベルのビットベクトルを保持する基底クラスのメンバ	1 レベルの参照は $O(1)$
`mid`	各レベルの 0 の個数を保持する基底クラスのメンバ	1 レベルの参照は $O(1)$

メンバの詳細

(constructor)

// (1)
WaveletMatrix() = default;

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

(1) 空のウェーブレット行列を作る

計算量: $O(1)$

(2) 列 v からウェーブレット行列を構築する

計算量: $O(nL)$

rank

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

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

(1) $0 \le i < r$ かつ $v_i=x$ を満たす要素数を返す

計算量: $O(L)$

(2) $l \le i < r$ かつ $v_i=x$ を満たす要素数を返す

計算量: $O(L)$

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) 区間 $[l,r)$ にある upper 未満の要素数を返す

計算量: $O(L)$

(2) 区間 $[l,r)$ にある $[lower,upper)$ 内の要素数を返す

計算量: $O(L)$

prev_value

T prev_value(int l, int r, T upper) const;

区間 $[l,r)$ にある upper 未満の最大値を返す

該当する値がなければ T(-1) を返す。

計算量: $O(L)$

next_value

T next_value(int l, int r, T lower) const;

区間 $[l,r)$ にある lower 以上の最小値を返す