← all categories

Xor Trie b2a92c88

Binary trie over BITS-bit integers, multiset semantics via ref-counted soft erase (no physical deletion). query(x) needs >=1 element currently inserted; insert(0) once up front as a sentinel if the set might otherwise be empty.

Time: O(BITS) per operation. tested

content/data-structures/xor-trie.h

template <int BITS = 31>
struct XorTrie {
    struct Node {
        int cnt = 0, ch[2] = {-1, -1};
    };
    vector<Node> pool{Node()};  // pool[0] is the root

    void insert(int x) {
        int at = 0;
        pool[at].cnt++;
        for (int i = BITS - 1; i >= 0; i--) {
            int b = (x >> i) & 1;
            if (pool[at].ch[b] == -1) { pool[at].ch[b] = pool.size(); pool.push_back(Node()); }
            at = pool[at].ch[b];
            pool[at].cnt++;
        }
    }

    void erase(int x) {  // x must currently be present
        int at = 0;
        pool[at].cnt--;
        for (int i = BITS - 1; i >= 0; i--) {
            at = pool[at].ch[(x >> i) & 1];
            pool[at].cnt--;
        }
    }

    int query(int x) {  // max (x ^ elem) over currently inserted elements
        int at = 0, res = 0;
        for (int i = BITS - 1; i >= 0; i--) {
            int b = (x >> i) & 1, want = b ^ 1;
            if (pool[at].ch[want] != -1 && pool[pool[at].ch[want]].cnt > 0) {
                res |= (1 << i);
                at = pool[at].ch[want];
            } else {
                at = pool[at].ch[b];
            }
        }
        return res;
    }
};