字典树

  1. struct Trie {
  2.     static constexpr int N = 1000010, M = 26;
  3.     int tot;
  4.     int tr[N][M];
  5.     int ends[N], prefix[N];
  6.     void clear() {
  7.         for(int i = 0; i <= tot; i++) memset(tr[i], 0, sizeof(tr[i]));
  8.         for(int i = 0; i <= tot; i++) ends[i] = prefix[i] = 0;
  9.         tot = 0; ends[p] = 0;
  10.     }
  11.     Trie() { tot = 0; }
  12.     void insert(string &s) {
  13.         int p = 0;
  14.         for(auto &ch : s) {
  15.             int c = ch - 'a';
  16.             if(tr[p][c] == 0) tr[p][c] = ++tot;
  17.             p = tr[p][c];
  18.             prefix[p] ++;
  19.         }
  20.         ends[p] ++;
  21.     }
  22. }tr;

01 字典树

  1. struct Trie {
  2.     static constexpr int N = 600005, M = 2;
  3.     int tot;
  4.     int tr[N][M];
  5.     int ends[N], prefix[N];
  6.     void clear() {
  7.         for(int i = 0; i <= tot; i++) memset(tr[i], 0, sizeof(tr[i]));
  8.         for(int i = 0; i <= tot; i++) ends[i] = prefix[i] = 0;
  9.         tot = 0;
  10.     }
  11.     Trie() { tot = 0; }
  12.     void insert(int x) {
  13.         int p = 0;
  14.         for(int i = 30; i >= 0; i--) {
  15.             int c = x >> i & 1;
  16.             if(tr[p][c] == 0) tr[p][c] = ++tot;
  17.             p = tr[p][c];
  18.             prefix[p] ++;
  19.         }
  20.     }
  21.     int ask(int x) {
  22.         int p = 0, rs = 0;
  23.         for(int i = 30; i >= 0; i--) {
  24.             int c = x >> i & 1;
  25.             if (tr[p][c ^ 1]) {
  26.                 p = tr[p][c ^ 1];
  27.                 rs |= 1 << i;
  28.             } else if(tr[p][c]) {
  29.                 p = tr[p][c];
  30.             } else {
  31.                 return 0;
  32.             }
  33.         }
  34.         return rs;
  35.     }
  36. }tr;