YS - Set XOR-Min

Explanation

We can construct a binary trie, with nodes representing the most significant bits near the root down to the least significant bits. When we add or remove a number fo a trie, we can simply add or subtract nodes with its binary representation. To answer queries, we can go down the trie and pick the same bit if possible to minimize total xor. Note when we go down any path in the trie, it is guaranteed that it will lead to the bottom so we don't have to worry about backtracking.

Implentation

Time Complexity: $\mathcal{O}(q\log x)$

Copy
#include <iostream>
#include <set>
using namespace std;

struct Trie {
	Trie *children[2] = {};
	int cnt = 0;  // # of numbers with this bit
};

void add(Trie *root, int x) {