数据字典字典树的作用及存储子节点+1（2）

Trie（字典树）

字典树是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串）。

其优点是：使用字符串的公共前缀减少了查询时间，最大限度地减少了不必要的字符串比较，查询效率高于哈希树。

[En]

Its advantage is: use the common prefix of the string to reduce the query time, minimize the unnecessary string comparison, and the query efficiency is higher than the hash tree.

——百度 · 百科

理解son[] []：存储子节点的位置，最多26条分支

son[0] [u] 这个的含义就是根节点它的孩子u结点的下标，跟单链表里的next指针其实是一样的。

但不同的是，我们的单一链表只有一个子级，那就是链。

[En]

But the difference is that our single linked list has only one child, which is a chain.

但是我们的Trie是后面可能有26个孩子(因为英文字母只有26个)，即有26种路径可以选的单链表。

理解idx:

idx：同链表数据字典，表示当前要插入的节点是哪一个，每创建一个节点idx+1（idx 当前用到了哪个下标初值为0 即为空节点也是根节点）

acwing：Trie统计字符串

维护一个字符串集合，支持两种操作：

I x 向集合中插入一个字符串 xx；Q x 询问一个字符串在集合中出现了多少次。

共有 NN 个操作，输入的字符串总长度不超过 105105，字符串仅包含小写英文字母。

输入格式

第一行包含整数 NN，表示操作数。

接下来 NN 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。

输出格式

对于每个询问指令 Q x，都要输出一个整数作为结果，表示 xx 在集合中出现的次数。

每个结果占一行。

数据范围

1≤N≤2∗1041≤N≤2∗104

输入样例：

I abc

Q abc

Q ab

I ab

Q ab

输出样例：

#includeusing namespace std;const int N = 1e5 + 10;// son[N][26] 存储子节点的位置，最多26条分支// cnt[] 存储以某节点为结尾的字符串的个数（同时起到标记作用）// idx：同链表，表示当前要插入的节点是哪一个，每创建一个节点idx+1（idx 当前用到了哪个下标 初值为0 即为空节点 也是根节点）int son[N][26], cnt[N], idx;char str[N];void insert(char *str){    int p = 0; // p是从根节点开始遍历的    for(int i = 0; str[i]; i++) // 字符串以'/0'结尾    {        int u = str[i] - 'a'; // 将字符映射为数字（字典树）0~25        if(son[p][u] == 0) son[p][u] = ++idx; // 如果该元素还没有创建则创建节点        p = son[p][u]; // 指针p移动    }    // 插入完之后p指向了该字符串的最后一个元素（节点）    cnt[p] ++; // 结束时的标记，也是记录以此节点结束的字符串个数}int query(char *str){    int p = 0; // 查询也是从根节点开始的    for(int i = 0; str[i]; i++)    {        int u = str[i] - 'a';        if(son[p][u] == 0) return 0; // 树中未找到该元素，则表明无此串        p = son[p][u]; // 找到则p移动    }    // 最后都存在（找到）返回该串出现的次数    return cnt[p];}int main(){    int n;    cin>>n;    while(n --)    {        string opt;        cin>> opt >> str;        if(opt == "I") insert(str);        else cout<< query(str) << endl;    }    return 0;}

acwing：最大异域对

在给定的 NN 个整数 A1，A2……ANA1，A2……AN 中选出两个进行 xorxor（异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数 NN。

第二行输入 NN 个整数 A1A1～ANAN。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤1051≤N≤105,

0≤Ai

字典树不光可以用来存储字符，还可能存储整数！

1、 son数组定义是二维数组，son[ n ] [ m ]我在初学Trie树的时候很难理解，可以先理解它的第二维度，只有两种状态0/1，是因为这一位表示的是某个数字的的某一位是0 / 1，而第一维的大小是我们用的十位二进制表示下一共有多少位数，在本题中，数字一共有N个数字，N是小于10^5的，一个数在int下是32位，则我们需要至少3200000的一维坐标，而p = son[n] [0] / p = son[n] [1]其实存的值就是他的两个子节点的一维坐标的值。

那么x >> i & 1 其实就是我想知道x的二进制表示中的第i位(二进制位从第0位开始表示第0位 – 第 31 位)，本题的题目范围到2^31那么就是i从30 – 0。

2、构建逻辑其实相对简单，就是将数的二进制表示插入到son数组中数据字典，如果没有那么就将他的值附上++idx即可

3、查询的时候为了异或大小最大，那么就应该从根节点开始遍历最高位开始尽量让异或结果为1，因此在遍历查询数字的时候，尽量找与它自己不相同的数。取到第i位的时候第i位的值为u，查看son[u] [!s]（不同方向上）是否存在，如果存在那么将res = (res