区間内の x 未満の値の個数, 区間内の k 番目に小さい値
クエリの定義
長さ N の整数列 X に対して, 以下の操作を定義します. (X の値の最大値を M とする)
- rank(p, x) ：X[0], X[1], ... , X[p - 1] の中で x 未満の値の個数を取得
- rank(l, r, x) ：X[l], X[l + 1], ... , X[r - 1] の中で x 未満の値の個数を取得
- rank(l, r, x, y) ：X[l], X[l + 1], ... , X[r - 1] の中で x 以上 y 未満の値の個数を取得
- kth_min(l, r, k) ：X[l], X[l + 1], ... , X[r - 1] を昇順にソートしたときの k 番目の値を取得(0-indexed)
基本的なテクニック
rank はどれか一つができれば残りはそれを使えばできます.
なので大抵は 1つ目の方法のみを考えればよいです.
また, 一応 kth_min はオンラインクエリの rank ができれば値の二分探索で求まります.
ただし logM 倍が余計に付くので最適な方法ではないことが多いです.
値の変更なし ver
オフラインクエリ
rank
解法：座圧+クエリをソートして Fenwick Tree に各値の個数を持たせながら左端から順に追加していく
計算量：均し O(logN) で定数倍かなり高速
メモリ：O(N)
kth_min
オンラインクエリと同じ方法でいい
オンラインクエリ
rank
解法①：前処理で永続 Segment Tree で各値の個数を持って左から順に追加していき, 各位置でバージョンを持っておく. 各クエリには, 適切な位置の木に区間和クエリを投げればよい
計算量：O(logN)
メモリ：O(NlogN)
解法②：ソートされた列を持つ Segment Tree に入れて, さらに Fractional-Cascading で高速化する
計算量：O(logN)
メモリ：O(NlogN)
解法③：Wavelet Matrix を使う
計算量：O(logM) ※座圧すれば O(logN)
メモリ：O(NlogM)
kth_min
解法①：rank の解法①と同じ前処理をする. あとは各クエリで, l の位置と r の位置の木を同時に降りながら二分探索すれば求まる
計算量：O(logN)
メモリ：O(NlogN)
解法②：Wavelet Matrix を使う
計算量：O(logM) ※座圧すれば O(logN)
メモリ：O(NlogM)
まとめ
ライブラリを持ってるなら全部 Wavelet Matrix を使うのが楽そう.
値の変更あり ver
値の一点更新クエリなどと一緒にくるときの場合です.
N * M の動的な二次元 Segment Tree を使います.
(i, X[i]) (0 <= i < N) は 1 , 他は 0 にしておきます.
X[p] の値を v に変更
解法：(p, X[p]) を 0 に, (p, v) を 1 に更新する
計算量：O(logM * logN)
rank
解法：rank(l, r, x, y) では [l, r) * [x, y) の範囲の値の和を求める
計算量：O(logM * logN)
kth_min
解法：[l, r) の範囲に対応する O(logN) 個の一次元 Segment Tree を同時に降りながら, 二分探索していく
計算量：O(logM * logN)
その他
空間計算量は O(N * logN * logM).
全クエリを先読みして座圧できれば logM の部分を log(Q+N) とかにできたりします.
また, 任意の位置での削除クエリなどが来る場合は各位置で削除されたかどうかを Segment Tree で持てば計算量を変えずに行えます. この場合削除クエリは O(logN).
もし, メモリが足りない場合はM個のセグメントツリーを平衡二分木で代用すると定数倍が悪くなる代わりに空間計算量 O(N * logN) にできます.
値の変更/挿入あり ver
列の任意の位置に値の挿入クエリがきたりする場合です.
このときは動的 Wavelet Matrix を使います.
動的 Wavelet Matrix とは, 完備辞書を insert/erase 操作ができる平衡二分木に置き換えた Wavelet Matrix です.
これを使うと insert, erase, rank, kth_min の全て O(logM * logN) でできます.
空間計算量は O(N * logM).
ただし二個目の log は平衡二分木なので非常に重く, 赤黒木を使っても僕の書いたものは 10^5 回のクエリに数秒程かかります.
使える状況はほとんど無いと思った方が良いです.
欲しくなったときは想定解が平方分割とかだったりする気がします.
