01Trie 最大异或对

思路：

异或运算 二进制位 N个整数均转化为二进制数表示 构造 Tire树 在树上进行异或运算

说明：

  • Trie存单词，由26个小写字母构造，是一棵26叉树，深度为最长单词的长度
  • Trie存整数，由整数的十进制位构造，是一棵10叉树，深度为10层
  • Trie存整数，由整数的二进制位构造，是一棵二叉树，深度为31层
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// 01 Trie (max xor), supports:
  // 1) insert(x)
  // 2) max_xor(x): max value of (x ^ y) among inserted y
  // 3) erase(x): optional (requires count maintenance)

  #include <bits/stdc++.h>
  using namespace std;

  template<int MAX_BIT = 30>  // for int up to 1e9 use 30, for signed int full use 31
  struct BinaryTrie {
      struct Node {
          int ch[2];
          int cnt; // how many numbers pass this node
          Node() : ch{-1, -1}, cnt(0) {}
      };

      vector<Node> tr;
      BinaryTrie() { tr.emplace_back(); } // root

      void clear() {
          tr.clear();
          tr.emplace_back();
      }

      void insert(int x) {
          int p = 0;
          tr[p].cnt++;
          for (int b = MAX_BIT; b >= 0; --b) {
              int bit = (x >> b) & 1;
              if (tr[p].ch[bit] == -1) {
                  tr[p].ch[bit] = (int)tr.size();
                  tr.emplace_back();
              }
              p = tr[p].ch[bit];
              tr[p].cnt++;
          }
      }

      // erase one x (assume x exists)
      void erase(int x) {
          int p = 0;
          tr[p].cnt--;
          for (int b = MAX_BIT; b >= 0; --b) {
              int bit = (x >> b) & 1;
              p = tr[p].ch[bit];
              tr[p].cnt--;
          }
      }

      bool empty() const { return tr[0].cnt == 0; }

      // return max (x ^ y), y from trie
      int max_xor(int x) const {
          if (empty()) return 0; // or throw
          int p = 0, ans = 0;
          for (int b = MAX_BIT; b >= 0; --b) {
              int bit = (x >> b) & 1;
              int want = bit ^ 1; // greedy opposite bit
              int nxt = tr[p].ch[want];
              if (nxt != -1 && tr[nxt].cnt > 0) {
                  ans |= (1 << b);
                  p = nxt;
              } else {
                  p = tr[p].ch[bit];
              }
          }
          return ans;
      }

      // return min (x ^ y), y from trie
      int min_xor(int x) const {
          if (empty()) return 0; // or throw
          int p = 0, ans = 0;
          for (int b = MAX_BIT; b >= 0; --b) {
              int bit = (x >> b) & 1;
              int same = tr[p].ch[bit];
              if (same != -1 && tr[same].cnt > 0) {
                  p = same;
              } else {
                  ans |= (1 << b);
                  p = tr[p].ch[bit ^ 1];
              }
          }
          return ans;
      }
  };

  // ---------------- example ----------------
  // int main() {
  //     ios::sync_with_stdio(false);
  //     cin.tie(nullptr);
  //
  //     vector<int> a = {1, 2, 3, 10};
  //     BinaryTrie<30> bt;
  //     for (int x : a) bt.insert(x);
  //
  //     cout << bt.max_xor(5) << "\n"; // max of (5^x)
  //     bt.erase(2);
  //     cout << bt.max_xor(5) << "\n";
  // }