Binary Trie (binary_trie.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-06-03 04:04:59+09:00
• Include: #include "binary_trie.hpp"

非負整数を 2 進表記で管理する Trie 木。

コンストラクタ

BinaryTrie()

空の Binary Trie を作成。

計算量

• $O(1)$

insert

void insert(T x)

x を追加。

計算量

• $O(\log A)$

erase

void erase(T x)

x を削除。

計算量

• $O(\log A)$

contains

bool contains(T x) 

x が含まれているか判定。

計算量

• $O(\log A)$

max_element, min_element

T max_element()
T min_element()

集合の最大値/最小値を返す。

計算量

• $O(\log A)$

apply_xor

void apply_xor(T x)

集合の要素全てに xor を作用させる。

計算量

• $O(1)$

Verified with

• test/lc_set_xor_min.cpp

Code

template <typename T>
class BinaryTrie {
   private:
    static constexpr int depth = bit_width(static_cast<unsigned long long>(numeric_limits<T>::max()));

    struct Node;
    using Nodeptr_t = Node*;

    struct Node {
        Nodeptr_t c0, c1;
        int cnt = 0;

        Node() : c0(nullptr), c1(nullptr), cnt(0) {}
    };

    Nodeptr_t root;

    T lazy_xor = 0;

    void del(Nodeptr_t& node) {
        if (node == nullptr) return;

        del(node->c0);
        del(node->c1);
        delete node;
    }

    void erase(T x, Nodeptr_t& node, int d) {
        if (d == -1) {
            node = nullptr;
            return;
        }

        if ((x >> d & 1) == (lazy_xor >> d & 1))
            erase(x, node->c0, d - 1);
        else
            erase(x, node->c1, d - 1);

        node->cnt--;
        if (node->cnt == 0) node = nullptr;
    }

   public:
    BinaryTrie() { root = new Node(); }

    ~BinaryTrie() { del(root); }

    void insert(T x) {
        if (contains(x)) return;
        if (root == nullptr) root = new Node();

        Nodeptr_t node = root;
        for (int i = depth - 1; i >= 0; --i) {
            node->cnt++;
            if ((x >> i & 1) == (lazy_xor >> i & 1)) {
                if (node->c0 == nullptr) node->c0 = new Node();
                node = node->c0;
            } else {
                if (node->c1 == nullptr) node->c1 = new Node();
                node = node->c1;
            }
        }
    }
    void erase(T x) {
        if (!contains(x)) return;

        erase(x, root, depth - 1);
    }
    bool contains(T x) {
        if (root == nullptr) return false;

        Nodeptr_t node = root;
        for (int i = depth - 1; i >= 0; --i) {
            if ((x >> i & 1) == (lazy_xor >> i & 1)) {
                if (node->c0 == nullptr) return false;
                node = node->c0;
            } else {
                if (node->c1 == nullptr) return false;
                node = node->c1;
            }
        }
        return true;
    }

    T min_element() {
        Nodeptr_t node = root;
        T res = 0;
        for (int i = depth - 1; i >= 0; --i) {
            if (lazy_xor >> i & 1) {
                if (node->c1 != nullptr)
                    node = node->c1;
                else
                    node = node->c0, res |= (T(1) << i);
            } else {
                if (node->c0 != nullptr)
                    node = node->c0;
                else
                    node = node->c1, res |= (T(1) << i);
            }
        }
        return res;
    }
    T max_element() {
        Nodeptr_t node = root;
        T res = 0;
        for (int i = depth - 1; i >= 0; --i) {
            if (lazy_xor >> i & 1) {
                if (node->c0 != nullptr)
                    node = node->c0, res |= (T(1) << i);
                else
                    node = node->c1;
            } else {
                if (node->c1 != nullptr)
                    node = node->c1, res |= (T(1) << i);
                else
                    node = node->c0;
            }
        }
        return res;
    }

    void apply_xor(T x) { lazy_xor ^= x; }
};

#line 1 "binary_trie.hpp"
template <typename T>
class BinaryTrie {
   private:
    static constexpr int depth = bit_width(static_cast<unsigned long long>(numeric_limits<T>::max()));

    struct Node;
    using Nodeptr_t = Node*;

    struct Node {
        Nodeptr_t c0, c1;
        int cnt = 0;

        Node() : c0(nullptr), c1(nullptr), cnt(0) {}
    };

    Nodeptr_t root;

    T lazy_xor = 0;

    void del(Nodeptr_t& node) {
        if (node == nullptr) return;

        del(node->c0);
        del(node->c1);
        delete node;
    }

    void erase(T x, Nodeptr_t& node, int d) {
        if (d == -1) {
            node = nullptr;
            return;
        }

        if ((x >> d & 1) == (lazy_xor >> d & 1))
            erase(x, node->c0, d - 1);
        else
            erase(x, node->c1, d - 1);

        node->cnt--;
        if (node->cnt == 0) node = nullptr;
    }

   public:
    BinaryTrie() { root = new Node(); }

    ~BinaryTrie() { del(root); }

    void insert(T x) {
        if (contains(x)) return;
        if (root == nullptr) root = new Node();

        Nodeptr_t node = root;
        for (int i = depth - 1; i >= 0; --i) {
            node->cnt++;
            if ((x >> i & 1) == (lazy_xor >> i & 1)) {
                if (node->c0 == nullptr) node->c0 = new Node();
                node = node->c0;
            } else {
                if (node->c1 == nullptr) node->c1 = new Node();
                node = node->c1;
            }
        }
    }
    void erase(T x) {
        if (!contains(x)) return;

        erase(x, root, depth - 1);
    }
    bool contains(T x) {
        if (root == nullptr) return false;

        Nodeptr_t node = root;
        for (int i = depth - 1; i >= 0; --i) {
            if ((x >> i & 1) == (lazy_xor >> i & 1)) {
                if (node->c0 == nullptr) return false;
                node = node->c0;
            } else {
                if (node->c1 == nullptr) return false;
                node = node->c1;
            }
        }
        return true;
    }

    T min_element() {
        Nodeptr_t node = root;
        T res = 0;
        for (int i = depth - 1; i >= 0; --i) {
            if (lazy_xor >> i & 1) {
                if (node->c1 != nullptr)
                    node = node->c1;
                else
                    node = node->c0, res |= (T(1) << i);
            } else {
                if (node->c0 != nullptr)
                    node = node->c0;
                else
                    node = node->c1, res |= (T(1) << i);
            }
        }
        return res;
    }
    T max_element() {
        Nodeptr_t node = root;
        T res = 0;
        for (int i = depth - 1; i >= 0; --i) {
            if (lazy_xor >> i & 1) {
                if (node->c0 != nullptr)
                    node = node->c0, res |= (T(1) << i);
                else
                    node = node->c1;
            } else {
                if (node->c1 != nullptr)
                    node = node->c1, res |= (T(1) << i);
                else
                    node = node->c0;
            }
        }
        return res;
    }

    void apply_xor(T x) { lazy_xor ^= x; }
};

Back to top page