Quartz 5

0-1字典树

2 min read

定义

0-1字典树

0-1字典树（0-1 Trie）是一中特殊的字典树，用来表示二进制串，其中每个节点最多有0和1两个子节点。
利用其结构可以高效的求得一个数与树中的数的最大异或值。

删除

对于删除，我们当然不能把该数二进制位的所有节点删除，因为这些节点可能也被其他数所使用。所以需要加一个数组，表示有多少个数使用了节点。插入时使各位+1，删除时只需要各位-1，说明该节点存在。

实现

constexpr int N = 1e6;  
constexpr int BITS = 30;  
int trie[N * BITS][2];
int cnt[N * BITS];
int total = 1;  
  
void insert(int x)  
{  
    int u = 1;    
	cnt[u]++; // 每个都经过根节点
    for (int i = BITS; i >= 0; i--)  
    {  
       int bit = (x >> i) & 1;  
       if (trie[u][bit] == 0)  
          trie[u][bit] = ++total;  
       u = trie[u][bit];
       cnt[u]++;
    }  
} 
 
void remove(int x)  
{  
    int u = 1;  
    cnt[u]--;  
    for (int i = BITS; i >= 0; i--)  
    {  
       int bit = (x >> i) & 1;  
       u = trie[u][bit];  
       cnt[u]--;  
    }  
}
  
int query_max_xor(int x)  
{  
    int res = 0;  
    int u = 1;  
    for (int i = BITS; i >= 0; i--)  
    {  
       int bit = (x >> i) & 1;  
       if (trie[u][bit ^ 1] && cnt[trie[u][bit ^ 1]] > 0) // 优先走不同的位  
       {  
          res |= (1 << i);  
          u = trie[u][bit ^ 1];  
       }  
       else
          u = trie[u][bit];  
    }  
    return res;  
}

题目

最大异或节点

Backlinks