字典数tried

字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

字符串统计：
模板：

int son[N][26];//存储节点，的下一个节点的下标。
int idx;
int cnt[N];//存储有几个以该节点为结尾的字符串。
void insert(string x)
{
    int p = 0;
    for(int i=0;i<x.length();i++)
    {
        int u = x[i]-'0';
        if(!son[p][u]) son[p][u] = ++idx;//如果节点为空，则新建节点。
        p = son[p][u];
    }
    cnt[p]++;
}
int query(string x)
{
    int p=0;
    for(int i=0;i<x.length();i++)
    {
        int u=x[i]-'0';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
    

最大异或对：
采用贪心的思想，对于一个数，从最高位找与它相反的位。

void insert(int x)
{
    int p =0;
    for(int i=30;i>=0;i--)
    {
        int &s = son[p][(x>>i)&1];//对每一位挨个存储。
        if(!s) s = ++idx;
        p = s;
    }
}
int option(int x)
{
    int res= 0;
    int p =0;
    for(int i=30;i>=0;i--)
    {
        int s = (x>>i)&1;
        if(son[p][!s])//如果存在相反的位，那么就朝相反的位移动。
        {
            res += 1<<i;
            p = son[p][!s];
        }
        else p = son[p][s];
        
    }
    return res;
}