Wavelet 行列ライブラリを書いた．
使用法
vector<ll> vec{...};
WaveletMatrix wm(vec, -1);
cout << wm.kth_rank(10, 20) << endl;
コンストラクタ
WaveletMatrix wm(vec, amax);
- vec … データを格納したベクトルなど．すべて非負整数であることが必要．
- amax … 「データがこの値を超えない」という値．
-1を与えると，ライブラリの方で最大値を取ってくれる
データメンバ
wm.N… データの個数
他にもあるが，使わないと思う．
データ値の取得
wm.access(i);
i 番目の値を取得する．vec[i] と同じになるはずなので，あまり使いではない．
出現回数
wm.rank(t, r);
- 区間
[0, r)にtが現れる回数を返す． tは非負整数であればよい．rは，wm.N以下でなければならない．
k番目
wm.kth_smallest(k, l, r);
wm.kth_largest(k, l, r);
- 区間
[l, r)で，k番目に小さい / 大きい 値を返す． kは 0-indexed. たとえば最小値はkth_smallest(0, l, r).kは意味がある値でなければならない．つまり，0 <= k < r - lが必要．0 <= l < r <= wm.Nでなければならない．
出現回数
wm.range_freq(hi, l, r);
wm.range_freq(lo, hi, l, r);
- 区間
[l, r)において各々，t < hiまたはlo <= t < hiであるような要素 t の個数を返す． 0 <= lo <= hiでなければならない．(amax に関する制約は無い)0 <= l <= r <= wm.Nでなければならない．