01Trie

---

01Trie-最大异或对

---

• 01Trie

  1、Trie 指字典树：简单地说，对于 $abcd, abcc, abca, acca$ 这四个字符串，互相之间有相同前缀，将它拆分成字符，建成边权为字符、点权为到该点为止相同前缀的字符串个数的树，称为 Trie 树，树的高度为字符串长度，如下图(蓝色为边权，红色为点权)。其通常处理前缀问题(如判断某个字符串作为前缀出现多少次)，但实际很少用到 Trie 树，常用的是 01Trie 树
  2、01Trie 存储的不是字符，而是二进制的 $0, 1$，用于表示数字，基于二叉树：例如数组内有数字 $5 = 0101_2, 7 = 0111_2, 2 = 0010_2, 10 = 1010_2$，便可以用01Trie 树来存储表示这个数组，树的高度为最长二进制位数，如下图所示
  3、01Trie初始只有一个空节点(初始节点 $0$)，采用动态开点的方式，其每个节点存储点权 $val$ 和两条边 $0, 1$ 分别指向的子节点 $son[0], son[1]$。更新时，没有的节点就动态开点，经过的节点点权 $+1$，对应二进制位为 $0$ 就左走，为 $1$ 就右走。对于数值范围在 $10^9$ 内的(约 $30$ 位二进制)，01Trie 通常需要 $32n = N \lt\lt 5$ 的空间

  

• 最大异或对

  1、最大异或对：给定一个长度为 $n$ ($n \leq 2 \times 10^5$) 的数组 $a[]$，找出一个二元组 $(a_i, a_j)$，使得 $a_i \oplus a_j$ 最大并输出
  2、分析可知，从 01Trie 起点开始，只要 $a_i, a_j$ 每次选择相反的路(一个走 $0$，一个走 $1$)，那么异或后该位结果为 $1$，否则该位结果为 $0$。又因为01Trie对于异或运算满足从高位向低位的贪心性质，向下走的过程是从二进制高位向低位的，所以每次只要选择相反的路就是整体最优(高位大，数字一定更大)
  3、实现中，注意处理数字要从高位向低位处理，一般 int 范围从第 $30$ 位开始处理，在循环中更新当前节点 $o$

• 代码实现

  #include <bits/stdc++.h>
  using namespace std;
  
  const int N = 2e5 + 10;
  int a[N];
  
  struct Node
  {
          int val;    // 点权
          int son[2]; // 左右子节点
  } t[N << 5];        // 01Trie
  int idx;            // 内存池
  
  // 插入新的值，动态开点
  void insert(int x)
  {
      int o = 0;  // 从节点 0 开始
      t[o].val++; // 点权 val++
  
      // 从二进制高位向低位
      for (int i = 30; i >= 0; i--)
      {
          int y = x >> i & 1; // 取出 x 的第 i 位
  
          // 引用，看节点 o 的 son[y] 是否存在，如果不存在，就动态开点
          int &u = t[o].son[y];
          if (!u)
              u = ++idx;
  
          o = u;      // 向下走
          t[o].val++; // 更新点权，注意一定写在后面，不然叶子是不加的
      }
  }
  
  int getMax(int x)
  {
      int o = 0;
      int res = 0;
  
      for (int i = 30; i >= 0; i--)
      {
          int y = x >> i & 1;
  
          int u = t[o].son[y], v = t[o].son[!y]; // 取出相反的两条边
          // u 是小点，v 是大点，如果 v 存在就尽可能走 v
          if (v)
          {
              o = v;           // 走相反的 v，异或后该位为 1
              res |= (1 << i); // 更新 res
          }
          else
              o = u; // 只能走 u，异或后该位为 0
      }
  
      return res;
  }
  
  void solve()
  {
      int n;
      cin >> n;
      for (int i = 1; i <= n; i++)
          cin >> a[i];
  
      for (int i = 1; i <= n; i++)
          insert(a[i]);
  
      int ans = 0;
      for (int i = 1; i <= n; i++)
          ans = max(ans, getMax(a[i]));
      cout << ans;
  }
  
  int main()
  {
      ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      int T = 1;
      // cin >> T;
      while (T--)
          solve();
      return 0;
  }

---

01Trie-第 k 小异或对

---

• 第 k 小异或对

  1、第 k 小异或对：给定数组长度 $n$ 和询问次数 $q$ ($n,q \leq 2 \times 10^5$) ，给出数组 $a[]$。对于每次询问，输入 $t\ x\ k$，输出 $a_1 \oplus x, a_2 \oplus x, …, a_t \oplus x$ 中第 $k$ 小的值
  2、判断第 $k$ 小的思路与权值线段树的思路相似：从起点开始，假设要判断的 $x$ 对应位二进制为 $y$，向下走时，选择与 $y$ 相同的边异或后的结果是更小的，与 $y$ 不同的边异或后的结果是更大的。令相同的边的子节点点权为 $val$，要找第 $k$ 小：如果 $val \geq k$，说明前 $k$ 小的结果都在这条边，应向小的这边查找第 $k$ 小；否则向大的一边走，排除掉另一边的小的，找第 $k - val$ 小。边走边记录选择的边
  3、另一个问题是，询问的是区间 $[1, t]$ 的 01Trie 树，对于单个这样的前缀区间可以处理到 $a_t$ 入树就对 $[1, t]$ 的 01Trie 树进行查找，但该例中，如果先询问 $[1, 30]$ 后询问 $[1, 10]$，此时的 01Trie 已经处理了 $[1, 30]$，不能回头处理 $[1, 10]$ 的情况 (删除回退会使复杂度过高)。所以，应当提前记录所有询问使询问离线，按 $t$ 升序的顺序处理，记录 $id$ 并根据 $id$ 输出答案

• 代码实现

  #include <bits/stdc++.h>
  using namespace std;
  
  const int N = 2e5 + 10;
  int a[N];
  
  struct Node
  {
          int val;    // 点权
          int son[2]; // 左右子节点
  } t[N << 5];        // 01Trie
  int idx;            // 内存池
  
  // 存储询问
  struct Q
  {
          int id;      // 询问的编号
          int t, x, k; // 询问的内容
  };
  vector<Q> que; // 离线记录询问
  int ans[N];    // 离线保存答案
  
  // 插入新的值，动态开点
  void insert(int x)
  {
      int o = 0;  // 从节点 0 开始
      t[o].val++; // 点权 val++
  
      // 从二进制高位向低位
      for (int i = 30; i >= 0; i--)
      {
          int y = x >> i & 1; // 取出 x 的第 i 位
  
          // 引用，看节点 o 的 son[y] 是否存在，如果不存在，就动态开点
          int &u = t[o].son[y];
          if (!u)
              u = ++idx;
  
          o = u;      // 向下走
          t[o].val++; // 更新点权，注意一定写在后面，不然叶子是不加的
      }
  }
  
  int getVal(int x, int k)
  {
      int o = 0;
      int res = 0;
  
      for (int i = 30; i >= 0; i--)
      {
          int y = x >> i & 1;
  
          int u = t[o].son[y], v = t[o].son[!y]; // 取出相反的两条边
          // u 点是小点， v 点是大点，判断小点存不存在、有没有 k 个，有的话就走 v
          if (u && t[u].val >= k)
              o = u; // 走 u，不需要更新 res
          else
          {
              o = v;                   // 走 v
              k -= (u ? t[u].val : 0); // 去除另一条路的小点(如果有的话)
              res |= (1 << i);         // 需要更新 res
          }
      }
  
      return res;
  }
  
  void solve()
  {
      int n, q;
      cin >> n >> q;
      for (int i = 1; i <= n; i++)
          cin >> a[i];
  
      // 记录所有询问，使询问离线
      for (int i = 1; i <= q; i++)
      {
          int t, x, k;
          cin >> t >> x >> k;
          que.push_back({i, t, x, k});
      }
      // 按 t 升序排列询问
      sort(que.begin(), que.end(), [](const Q &u, const Q &v) { return u.t < v.t; });
  
      int now = 0; // 记录此时 Trie 树更新到了哪个元素
      // 遍历询问
      for (auto &qe : que)
      {
          // 继续更新 Trie 树
          while (now < qe.t)
              insert(a[++now]);
  
          // 此时 Trie 存的就是当前 [1, t] 的信息
          ans[qe.id] = getVal(qe.x, qe.k); // 记录答案
      }
  
      for (int i = 1; i <= q; i++)
          cout << ans[i] << '\n';
  }
  
  int main()
  {
      ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      int T = 1;
      // cin >> T;
      while (T--)
          solve();
      return 0;
  }

---

页底评论

---