k 番目に小さい値を取得可能な集合を管理するデータ構造
前提
集合に対して N 個の 追加・削除・k番目に小さい値の取得 のクエリがくるとします.
集合の要素は順序が付けられるものだけ考えます.
要素が非負整数の場合は最大値を X とします.
配列(または bitset)
各値の位置にカウントをもたせます.
用途:
k 番目取得が要らない場合は一番使えるので一応.
座標圧縮:
- 要素が非負整数:最大値が小さい場合不要, 大きいと必要
- その他:必要
時間計算量:
- 追加・削除クエリ:O(1)
- k 番目取得クエリ:O(N) または O(X)
空間計算量:O(N) または O(X)
Fenwick Tree
各値の位置にカウントをもたせます.
追加・削除でうまく足し引きして, k番目クエリでは根から二分探索しながら降ります.
用途:
定数倍が速いので, 全操作が均等にくる場合はこれが最強.
座標圧縮:
- 要素が非負整数:最大値が小さい場合不要, 大きいと必要
- その他:必要
時間計算量:
- 全クエリ:O(logN) または O(logX)
空間計算量:O(N) または O(X)
実装例:
class fenwick_tree_set { const int n; int cnt; vector<int> data; int find(int p) const { int res = 0; while (p > 0) { res += data[p]; p -= p & -p; } return res; } void add(int p, int x) { ++p; while (p <= n) { data[p] += x; p += p & -p; } } public: fenwick_tree_set(int maxi) : n(maxi + 1), cnt(0), data(n + 1) {} int size() const { return cnt; } int count(int val) const { assert(0 <= val && val < n); return find(val + 1) - find(val); } void insert(int val) { assert(0 <= val && val < n); add(val, 1); cnt += 1; } void erase(int val) { assert(0 <= val && val < n); assert(0 < count(val)); add(val, -1); cnt -= 1; } int kth_element(int k) const { assert(0 <= k && k < cnt); int p = 1 << (32 - __builtin_clz(n)), res = 0; while (p >>= 1) { if (res + p <= n && data[res + p] <= k) { k -= data[res + p]; res += p; } } return res; } };
平方分割
配列の方法 + 各バケット毎の個数の合計 を持ちます.
用途:
追加・削除が高速で Mo's Algorithm と相性がよいです.
座標圧縮:
- 要素が非負整数:最大値が小さい場合不要, 大きいと必要
- その他:必要
時間計算量:
- 追加・削除クエリ:O(1)
- k 番目取得クエリ:O(sqrt(N)) または O(sqrt(X))
空間計算量:O(N) または O(X)
実装例:
sqrtX を二冪で丸めてます.
class sqrt_decomposition_set { const int n, b; int cnt; vector<int> data, sum; int get_b(int x) const { int t = 0; while ((1 << t) < x) ++t; return t >> 1; } public: sqrt_decomposition_set(int maxi) : n(maxi + 1), b(get_b(n)), cnt(0), data(n), sum((n + (1 << b) - 1) >> b) {} int size() const { return cnt; } int count(int val) const { assert(0 <= val && val < n); return data[val]; } void insert(int val) { assert(0 <= val && val < n); ++data[val]; ++sum[val >> b]; ++cnt; } void erase(int val) { assert(0 <= val && val < n); assert(0 < data[val]); --data[val]; --sum[val >> b]; --cnt; } int kth_element(int k) const { assert(0 <= k && k < cnt); int it = 0; while (sum[it] < k) k -= sum[it++]; int id = it << b; while (data[id] == 0 || data[id] <= k) k -= data[id++]; return id; } };
Trie(動的 Segment Tree)
各値の位置にカウントをもたせます.
くわしくはこれ
http://kazuma8128.hatenablog.com/entry/2018/05/06/022654
用途:
座圧ができないオンラインクエリのときに使えます.
ちなみに, ある値で XOR したときの k 番目の値とかも O(logX) でできます.
座標圧縮:
- 要素が非負整数:不要
- その他:必要(文字列とかはそのままで可能だけどもはや別物)
時間計算量:
- 全クエリ:O(logN) または O(logX)
空間計算量:O(N logN) または O(N logX)
実装例:上のリンクに載ってるので省略
平衡二分木
std::set では k番目取得クエリができないので自分で書きます.
g++拡張が使える場合は tree とかいうのを使うのが楽そう.
用途:
Trie でも MLE するときとかに使います.
定数倍が異常にデカいので速度は期待しない方が良いです.
座標圧縮:
- 要素が非負整数:不要
- その他:不要
時間計算量:
- 全クエリ:O(logN)
空間計算量:O(N)
実装例:
おまけ
趣旨がずれますが, van Emde Boas Tree(通称:謎木)というものを使うと非負整数に対して以下の操作が全て O(log log X) でできます.
- 要素の追加
- 要素の削除
- lower_bound / upper_bound
ちなみに最大/最小値の取得は O(1) です.
これを使えば速い set とか map が作れます.
空間計算量は O(X) です.
unordered_map を内部で使えば O(N) にできますが, 定数倍が遅くなるのでちょっと残念になります.
実装例:
雑に書いたので定数倍が遅めかもしれません.
コード