BinaryTrie
(Data_structure/BinaryTrie.hpp)

• View this file on GitHub
• Last update: 2023-07-24 07:10:25+00:00
• Include: #include "Data_structure/BinaryTrie.hpp"

BinaryTrie 非負整数を扱うMultiSet

集合 $S$ について、

• insert(x): $S$ に $x$ を追加する
• erase(x): $S$ から $x$ を削除する
• find(x): $S$ に $x$ が含まれるか判定する (TODO) これはcountにして個数を返したほうがうれしい？
• min_element(): $S$ の最小値を返す
• min_element(x): $\min_{s \in S} (s \oplus x)$ ($\oplus$ はXOR) を返す
• (TODO) kth_element(k): $S$ の $k$ 番目に小さい値を返す

コンストラクタ

BinaryTrie<int length = 30> trie()

• 空の集合で初期化
• lengthは必要なビット数 内部的にはbitsetで管理してるので、大きくてもOK

計算量

• $O(1)$

insert

(1) int trie.insert(unsigned long long x)
(2) int trie.insert(const bitset<length> s)

• (1): $S$ に $x$ を追加する
• (2): $S$ に $s$ を追加する
• 返り値は $x$ (もしくは$s$) の葉の頂点番号

制約

• (1): $0 \leq x < 2^{length}$

計算量

• $O(length)$

erase

(1) void trie.erase(unsigned long long x)
(2) void trie.erase(const bitset<length> s)

• (1): $S$ から $x$ を削除する
• (2): $S$ から $s$ を削除する

制約

• (1): $0 \leq x < 2^{length}$

計算量

• $O(length)$

find

bool trie.find(unsigned long long x)
bool trie.find(const bitset<length> s)

• (1): $S$ に $x$ が含まれるか判定する
• (2): $S$ に $s$ が含まれるか判定する

制約

• (1): $0 \leq x < 2^{length}$

計算量

• $O(length)$

min_element

(1) unsigned long long trie.min_element()
(2) unsigned long long trie.min_element(unsigned long long x)
(3) bitset<length> trie.min_element(const bitset<length> s)

• (1): $S$ の最小値を返す
• (2): $\min_{s \in S} (s \oplus x)$ ($\oplus$ はXOR) を返す
• (3): $\min_{s \in S} (s \oplus s)$ ($\oplus$ はXOR) を返す

計算量

• $O(length)$

Verified with

• Test/yosupo-Set-Xor-Min.test.cpp

Code

template<int length = 30> struct BinaryTrie {
    struct Node {
        vector<int> next;
        int parent, val, cnt;
        Node(int parent = -1, int val = -1) : parent(parent), val(val), cnt(0) {
            next = vector<int>(2, -1);
        }
    };
    vector<Node> nodes;

    BinaryTrie() {
        nodes = { Node() };
    }

    int add_node(int parent, int val) {
        nodes.push_back(Node(parent, val));
        return nodes.size() - 1;
    }

    int insert(unsigned long long x) { return insert(bitset<length>(x)); }
    int insert(const bitset<length> &s) {
        int now_node = 0;
        nodes[now_node].cnt++;
        for (int i = length - 1; i >= 0; i--) {
            int next = s[i];
            if (nodes[now_node].next[next] == -1) {
                nodes[now_node].next[next] = add_node(now_node, next);
            }
            now_node = nodes[now_node].next[next];
            nodes[now_node].cnt++;
        }
        return now_node;
    }

    void erase(unsigned long long x) { erase(bitset<length>(x)); }
    void erase(const bitset<length> &s) {
        if (!find(s)) return;
        int now_node = 0;
        nodes[now_node].cnt--;
        for (int i = length - 1; i >= 0; i--) {
            int next = s[i];
            now_node = nodes[now_node].next[next];
            nodes[now_node].cnt--;
        }
    }


    bool find(long long x) { return find(bitset<length>(x)); }
    bool find(const bitset<length> &s) {
        int now_node = 0;
        if (nodes[now_node].cnt == 0) {
            return false;
        }
        for (int i = length - 1; i >= 0; i--) {
            int next = s[i];
            if (nodes[now_node].next[next] == -1) {
                return false;
            }
            now_node = nodes[now_node].next[next];
            if (nodes[now_node].cnt == 0) {
                return false;
            }
        }
        return true;
    }

    unsigned long long min_element(unsigned long long x = 0LL) {
        return min_element(bitset<length>(x)).to_ullong();
    }
    bitset<length> min_element(const bitset<length> &s = bitset<length>()) {
        assert(nodes[0].cnt > 0);
        int now_node = 0;
        bitset<length> ret;
        for (int i = length - 1; i >= 0; i--) {
            int next = s[i];
            if (nodes[now_node].next[next] == -1 || nodes[nodes[now_node].next[next]].cnt == 0) {
                next = 1 - next;
            }
            ret[i] = next ^ s[i];
            now_node = nodes[now_node].next[next];
        }
        return ret;
    }
};

#line 1 "Data_structure/BinaryTrie.hpp"
template<int length = 30> struct BinaryTrie {
    struct Node {
        vector<int> next;
        int parent, val, cnt;
        Node(int parent = -1, int val = -1) : parent(parent), val(val), cnt(0) {
            next = vector<int>(2, -1);
        }
    };
    vector<Node> nodes;

    BinaryTrie() {
        nodes = { Node() };
    }

    int add_node(int parent, int val) {
        nodes.push_back(Node(parent, val));
        return nodes.size() - 1;
    }

    int insert(unsigned long long x) { return insert(bitset<length>(x)); }
    int insert(const bitset<length> &s) {
        int now_node = 0;
        nodes[now_node].cnt++;
        for (int i = length - 1; i >= 0; i--) {
            int next = s[i];
            if (nodes[now_node].next[next] == -1) {
                nodes[now_node].next[next] = add_node(now_node, next);
            }
            now_node = nodes[now_node].next[next];
            nodes[now_node].cnt++;
        }
        return now_node;
    }

    void erase(unsigned long long x) { erase(bitset<length>(x)); }
    void erase(const bitset<length> &s) {
        if (!find(s)) return;
        int now_node = 0;
        nodes[now_node].cnt--;
        for (int i = length - 1; i >= 0; i--) {
            int next = s[i];
            now_node = nodes[now_node].next[next];
            nodes[now_node].cnt--;
        }
    }


    bool find(long long x) { return find(bitset<length>(x)); }
    bool find(const bitset<length> &s) {
        int now_node = 0;
        if (nodes[now_node].cnt == 0) {
            return false;
        }
        for (int i = length - 1; i >= 0; i--) {
            int next = s[i];
            if (nodes[now_node].next[next] == -1) {
                return false;
            }
            now_node = nodes[now_node].next[next];
            if (nodes[now_node].cnt == 0) {
                return false;
            }
        }
        return true;
    }

    unsigned long long min_element(unsigned long long x = 0LL) {
        return min_element(bitset<length>(x)).to_ullong();
    }
    bitset<length> min_element(const bitset<length> &s = bitset<length>()) {
        assert(nodes[0].cnt > 0);
        int now_node = 0;
        bitset<length> ret;
        for (int i = length - 1; i >= 0; i--) {
            int next = s[i];
            if (nodes[now_node].next[next] == -1 || nodes[nodes[now_node].next[next]].cnt == 0) {
                next = 1 - next;
            }
            ret[i] = next ^ s[i];
            now_node = nodes[now_node].next[next];
        }
        return ret;
    }
};

Back to top page