DynamicWaveletMatrix

template <class T, int L = 20>
struct DynamicWaveletMatrix : internal::WaveletMatrixCore<internal::dynamic_bit_vector, T, L>;

概要

要素の挿入・削除が可能な動的ウェーブレット行列

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

名前	説明	計算量
`insert`	位置 `k` に値 `val` を挿入する	期待 $O(L\log n)$
`erase`	位置 `k` の要素を削除する	期待 $O(L\log n)$
`access`	`k` 番目の値を返す	期待 $O(L\log n)$
`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\log n)$
`kth_largest`	区間 $[l,r)$ 内で `k` 番目に大きい値を返す（0-indexed）	期待 $O(L\log n)$
`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\log n)$

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

// (1)
DynamicWaveletMatrix() = default;

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

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

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

// (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$ を満たす要素数を返す

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

// (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 未満の要素数を返す

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

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

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

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

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

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

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