kazuma8128’s blog

競プロの面白い問題を解きます

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) にできますが, 定数倍が遅くなるのでちょっと残念になります.

実装例
雑に書いたので定数倍が遅めかもしれません.
コード