BinaryTrie
(src/data_structure/binary_trie.hpp)

• View this file on GitHub
• Last update: 2024-11-09 01:34:39+09:00
• Include: #include "src/data_structure/binary_trie.hpp"

BinaryTrie

• 値の挿入・削除
• 値の検索
• 要素数の取得
• 全要素に xor を作用させる
• 最小値，最大値，ランダムアクセス
• lower_bound, upper_bound

を $O(d)$ で行えるデータ構造です．( $d$ は値の桁数)

コンストラクタ

BinaryTrie<T, MAX_LOG> trie

• $0$ 以上 $2^{MAX\_LOG}$ 未満の値を格納できる空の trie を構築します．

制約

• $T$ は int / uint / ll / ull
• $2^{MAX\_LOG}$ が $T$ で表現できる値に収まる

計算量

• $O(1)$

insert

void trie.insert(T x)

trie に $x$ を挿入します．
すでに trie に $x$ が存在する場合は何もしません．

制約

• $0 \leq x < 2^{MAX\_LOG}$

計算量

• $O(MAX\_LOG)$

erase

void trie.erase(T x)

trie から $x$ を削除します．
すでに trie に $x$ が存在しない場合は何もしません．

制約

• $0 \leq x < 2^{MAX\_LOG}$

計算量

• $O(MAX\_LOG)$

contains

bool trie.contains(T x)

trie に $x$ が含まれるかどうかを返します．

制約

• $0 \leq x < 2^{MAX\_LOG}$

計算量

• $O(MAX\_LOG)$

size

int trie.size()

trie に何個の要素が格納されているかを返します．

計算量

• $O(1)$

min

T trie.min(T x = 0)

trie に格納されている要素全てに対して $\mathrm{xor} ~ x$ を作用させたときの最小値を返します．

制約

• $0 \leq x < 2^{MAX\_LOG}$

計算量

• $O(MAX\_LOG)$

max

T trie.max(T x = 0)

trie に格納されている要素全てに対して $\mathrm{xor} ~ x$ を作用させたときの最大値を返します．

制約

• $0 \leq x < 2^{MAX\_LOG}$

計算量

• $O(MAX\_LOG)$

kth_element

T trie.kth_element(T x = 0)

trie に格納されている要素全てに対して $\mathrm{xor} ~ x$ を作用させたときの $k$ 番目に小さい値を返します．

制約

• $0 \leq k < \mathrm{trie.size()}$
• $0 \leq x < 2^{MAX\_LOG}$

計算量

• $O(MAX\_LOG)$

lower_bound

int trie.lower_bound(T val, T x = 0)

trie に格納されている要素全てに対して $\mathrm{xor} ~ x$ を作用させたときの $\mathrm{val}$ 以上の最小値が何番目に小さいかを返します．

制約

• $0 \leq \mathrm{val} < 2^{MAX\_LOG}$
• $0 \leq x < 2^{MAX\_LOG}$

計算量

• $O(MAX\_LOG)$

upper_bound

int trie.upper_bound(T val, T x = 0)

trie に格納されている要素全てに対して $\mathrm{xor} ~ x$ を作用させたときの $\mathrm{val}$ より大きい最小値が何番目に小さいかを返します．

制約

• $0 \leq \mathrm{val} < 2^{MAX\_LOG} - 1$
• $0 \leq x < 2^{MAX\_LOG}$

計算量

• $O(MAX\_LOG)$

Depends on

• template (src/template/template.hpp)

Verified with

• verify/library_checker/data_structure/set_xor_min.test.cpp

Code

#pragma once
#include "../template/template.hpp"
template <typename T, int MAX_LOG>
struct BinaryTrie {
    BinaryTrie()
        : root(new Node) {}
    void insert(const T& x) {
        assert(0 <= x and x < (T(1) << MAX_LOG));
        if(!contains(x)) update(x, 1);
    }
    void erase(const T& x) {
        assert(0 <= x and x < (T(1) << MAX_LOG));
        if(contains(x)) update(x, -1);
    }
    bool contains(const T& x) const {
        assert(0 <= x and x < (T(1) << MAX_LOG));
        Node* cur = root;
        for(int i = MAX_LOG - 1; i >= 0; --i) {
            if(!cur) break;
            const int nex = (x >> i) & 1;
            cur = cur->child[nex];
        }
        return cur and cur->cnt;
    }
    int size() const {
        return root->cnt;
    }
    T min(const T& x = 0) const {
        assert(root->cnt > 0);
        assert(0 <= x and x < (T(1) << MAX_LOG));
        return kth_element(0, x);
    }
    T max(const T& x = 0) const {
        assert(root->cnt > 0);
        assert(0 <= x and x < (T(1) << MAX_LOG));
        return kth_element(root->cnt - 1, x);
    }
    T kth_element(int k, const T& x = 0) const {
        assert(0 <= k and k < root->cnt);
        assert(0 <= x and x < (T(1) << MAX_LOG));
        T res = 0;
        Node* cur = root;
        for(int i = MAX_LOG - 1; i >= 0; --i) {
            const int nex = (x >> i) & 1;
            const int cnt = (cur->child[nex] ? cur->child[nex]->cnt : 0);
            if(cnt <= k) {
                k -= cnt;
                res += T(1) << i;
                cur = cur->child[nex ^ 1];
            } else {
                cur = cur->child[nex];
            }
        }
        return res;
    }
    int lower_bound(const T& val, const T& x = 0) const {
        assert(0 <= val and val < (T(1) << MAX_LOG));
        assert(0 <= x and x < (T(1) << MAX_LOG));
        int res = 0;
        Node* cur = root;
        for(int i = MAX_LOG - 1; i >= 0; --i) {
            if(!cur) break;
            const int xi = (x >> i) & 1, vi = (val >> i) & 1;
            const int nex = xi xor vi;
            if(vi and cur->child[xi]) {
                res += cur->child[xi]->cnt;
            }
            cur = cur->child[nex];
        }
        return res;
    }
    int upper_bound(const T& val, const T& x = 0) const {
        assert(0 <= val and val < (T(1) << MAX_LOG));
        assert(0 <= x and x < (T(1) << MAX_LOG));
        return lower_bound(val + 1, x);
    }

   private:
    struct Node {
        Node* child[2] = {};
        int cnt = 0;
        Node() {}
    };
    Node* root;
    void update(const T& x, const int delta) {
        Node* cur = root;
        cur->cnt += delta;
        for(int i = MAX_LOG - 1; i >= 0; --i) {
            const int nex = (x >> i) & 1;
            if(!cur->child[nex]) {
                cur->child[nex] = new Node;
            }
            cur = cur->child[nex];
            cur->cnt += delta;
        }
    }
};

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/data_structure/binary_trie.hpp"
template <typename T, int MAX_LOG>
struct BinaryTrie {
    BinaryTrie()
        : root(new Node) {}
    void insert(const T& x) {
        assert(0 <= x and x < (T(1) << MAX_LOG));
        if(!contains(x)) update(x, 1);
    }
    void erase(const T& x) {
        assert(0 <= x and x < (T(1) << MAX_LOG));
        if(contains(x)) update(x, -1);
    }
    bool contains(const T& x) const {
        assert(0 <= x and x < (T(1) << MAX_LOG));
        Node* cur = root;
        for(int i = MAX_LOG - 1; i >= 0; --i) {
            if(!cur) break;
            const int nex = (x >> i) & 1;
            cur = cur->child[nex];
        }
        return cur and cur->cnt;
    }
    int size() const {
        return root->cnt;
    }
    T min(const T& x = 0) const {
        assert(root->cnt > 0);
        assert(0 <= x and x < (T(1) << MAX_LOG));
        return kth_element(0, x);
    }
    T max(const T& x = 0) const {
        assert(root->cnt > 0);
        assert(0 <= x and x < (T(1) << MAX_LOG));
        return kth_element(root->cnt - 1, x);
    }
    T kth_element(int k, const T& x = 0) const {
        assert(0 <= k and k < root->cnt);
        assert(0 <= x and x < (T(1) << MAX_LOG));
        T res = 0;
        Node* cur = root;
        for(int i = MAX_LOG - 1; i >= 0; --i) {
            const int nex = (x >> i) & 1;
            const int cnt = (cur->child[nex] ? cur->child[nex]->cnt : 0);
            if(cnt <= k) {
                k -= cnt;
                res += T(1) << i;
                cur = cur->child[nex ^ 1];
            } else {
                cur = cur->child[nex];
            }
        }
        return res;
    }
    int lower_bound(const T& val, const T& x = 0) const {
        assert(0 <= val and val < (T(1) << MAX_LOG));
        assert(0 <= x and x < (T(1) << MAX_LOG));
        int res = 0;
        Node* cur = root;
        for(int i = MAX_LOG - 1; i >= 0; --i) {
            if(!cur) break;
            const int xi = (x >> i) & 1, vi = (val >> i) & 1;
            const int nex = xi xor vi;
            if(vi and cur->child[xi]) {
                res += cur->child[xi]->cnt;
            }
            cur = cur->child[nex];
        }
        return res;
    }
    int upper_bound(const T& val, const T& x = 0) const {
        assert(0 <= val and val < (T(1) << MAX_LOG));
        assert(0 <= x and x < (T(1) << MAX_LOG));
        return lower_bound(val + 1, x);
    }

   private:
    struct Node {
        Node* child[2] = {};
        int cnt = 0;
        Node() {}
    };
    Node* root;
    void update(const T& x, const int delta) {
        Node* cur = root;
        cur->cnt += delta;
        for(int i = MAX_LOG - 1; i >= 0; --i) {
            const int nex = (x >> i) & 1;
            if(!cur->child[nex]) {
                cur->child[nex] = new Node;
            }
            cur = cur->child[nex];
            cur->cnt += delta;
        }
    }
};

Back to top page