CompressedWaveletMatrix

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

template <class T, int L = 20>
struct CompressedWaveletMatrix;

概要

ウェーブレット行列（座標圧縮）

計算量

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

構築・破棄

名前	説明	計算量
`(constructor)`	(1) 空のウェーブレット行列を作る (2) 列 `v` を座標圧縮してウェーブレット行列を構築する	(1) $O(1)$ (2) $O(n\log n+nL)$

メンバ関数

名前	説明	計算量
`access`	`k` 番目の値を返す	$O(L)$
`rank`	(1) $0 \le i < r$ かつ $v_i=x$ を満たす要素数を返す (2) $l \le i < r$ かつ $v_i=x$ を満たす要素数を返す	$O(L+\log n)$
`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+\log n)$
`prev_value`	区間 $[l,r)$ にある `upper` 未満の最大値を返す	$O(L+\log n)$
`next_value`	区間 $[l,r)$ にある `lower` 以上の最小値を返す	$O(L+\log n)$

演算子

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

メンバの詳細

(constructor)

// (1)
CompressedWaveletMatrix() = default;

// (2)
CompressedWaveletMatrix(const std::vector<T> &v);

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

計算量: $O(1)$

(2) 列 v を座標圧縮してウェーブレット行列を構築する

計算量: $O(n\log n+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+\log n)$

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

計算量: $O(L+\log 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) 区間 $[l,r)$ にある upper 未満の要素数を返す

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

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

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

prev_value

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

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

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

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

next_value

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

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