说白了就是高效存储字符串的树，
但是注意，不会那么高效，只是相同路径共享
对于字符串 “abs” 和 “abc”：

它们的共同前缀 “ab” 在前缀树中会共享同一条路径，即从根节点出发，先找到字符 ‘a’，然后是字符 ‘b’。在这条路径上，两个字符串的表示是共用的。
对于字符串 “abs” 和 “bbs”：

它们没有共同的前缀，因此，在前缀树中不会有共享的路径。每个字符串都会根据自己的字符独立构建路径。

比如:
假设我们有以下字符串集合：{“see”, “he”, “hers”, “his”}。

     root(空的啥也没有，本来node的值，至少在第二个方法，都是靠上一个node的son数组下标确定的)
        /             \         
       "h"             "s"
      /  \             /
     "e" "i"        "e"
    /      \        /
   "r" "   "s"    "e"
  /           
 "s"         

这就是前缀树
需要注意，这里的几个变量含义
idx是用来分发地址变量的值的

s[p][u]的值代表下一个连接的元素的p(地址) p(当前元素的地址) u(具体元素对应int编号)
cnt[地址]的值的意思是，有字符串在这里停止。这里就相当于标记了一个字符串存在这里，
没有标记，就搞不清共用路径的字符串存不存在了，所以要标记它的存在。

思考一下整体的层次结构逻辑

只是进入时利用了0作为入口地址，后面真正记录字符串的每个元素都是单独有一个地址，除非字符串共用路径的是同一个地址

能高效利用共同路径的，必须是从开始要一样，中途出去的地方不一样
一开始就出去了就是毫无关联。所以说总结为哪里开始不一样，哪里的以后就相当于永远断开了

这里还关注一下p的更新：

开始的p都是父一级的元素的地址，u是当前元素，s[p][u]先把u元素的地址的值赋好了，才把p更新为u元素的地址的。所以后面cnt[p]++再统计的才是准确的字符串结束地址。

#include<iostream>


using namespace std;

const int N=1e5+10;
int son[N][26],cnt[N],idx;

void insert(string s){
    int p=0;
    //p表示第几层  
    for(int i=0;s[i];i++){
        int u=s[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;//son[][]值为空则代表之前没有这个字符，现在赋值就是表示这里建立了这个字符
        p=son[p][u];
    }
    cnt[p]++;
}

int query(string s){
    int p=0;
    for(int i=0;s[i];i++){
        int u=s[i]-'a';
        if(!son[p][u]) return 0;
        p=son[p][u];
    }
    return cnt[p];
}

int main(){
    int n;
    string op,s;
    cin>>n;
    while(n--){
        cin>>op>>s;
        if(op=="I"){
            insert(s);
        }else{
            cout<<query(s)<<endl;
        }
    }
    return 0;
}

或者像下面这么写
这里用node代替了数组

直接用链表
重点理解node
因为用的连接，所以
自己的地址变量并不需要。因为是链表链在一起的。或者说地址变量就是node本身。
这么说吧，它通过链接，去掉了对地址变量的需要，他自己就是地址

node有两个值，一个计数器用来记录自己是不是某个字符串地结尾，一个是链接下一个字符的node指针数组，就是说该指针数组的值相当于下一个元素的“地址”，而该指针数组下标代表当前自己的元素的值
重点注意，node自己的元素的值自己就记录在这个指针数组的下标，

层次结构还是一样的，开始利用同一个node进入，后面真正记录字符串地只要不是共用路径，都是各自的node

#include<iostream>


using namespace std;



    struct Node {
        int is_end;
        Node *son[26];
        Node() {
            is_end = 0;
            for (int i = 0; i < 26; i ++ )
                son[i] = NULL;
        }
    }*root;



    void insert(string word) {
        auto p = root;
        for (auto c: word) {
            int u = c - 'a';
            if (!p->son[u]) p->son[u] = new Node();
            p = p->son[u];
        }
        p->is_end++;
    }


    int query(string word) {
        auto p = root;
        for (auto c: word) {
            int u = c - 'a';
            if (!p->son[u]) return 0;
            p = p->son[u];
        }
        return p->is_end;
    }

int main(){
    int n;
    string op,s;
    root = new Node();
    cin>>n;
    while(n--){
        cin>>op>>s;
        if(op=="I"){
            insert(s);
        }else{
            cout<<query(s)<<endl;
        }
    }
    return 0;
}

所以第二种写法，单纯去掉了地址变量，而且还把字符串结束统计整合到了node当中。

这里重点关注一个地方（不是说差异，而是说共同要理解的一个地方）
insert的时候，我们首先要意识到p->son[u]的值的意思就是说当前node的下一个
元素值为u的node或者说地址。
if (!p->son[u]) p->son[u] = new Node();这里就是分配了一个地址

p = p->son[u]; 这里什么意思呢，就是说我要进入到下一个node当中
这样就相当于进入到了下一个元素当中，而这个p就是下一个元素的node
或者说叫地址

所以说，懂？p->son[u]的值的意思就是说当前node的下一个
元素值为u的node或者说地址。

算力，都是应应试罢了，就记住第二种node写法。

你思考一下呗，就是你要insert一个string，那怎么办，遍历呗。
把每个字符存在一个node当中，临时地址变量node p永远从一个root节点开始
根据它的一个下标为元素，值为node地址的数组的方式存储字符。先确定你这个字符这个路径
以前走过没，没走过，那就分配一个地址。走过或者没走过都把临时地址变量node p更新为
下一个元素的地址，当然你刚才存的就是下一个元素，所以就算下一个元素和下一个地址的存储，这里存储好了，再把p更新为下一个字符存储做准备而已。如果字符串刚好在这里遍历完了，还能通过这个临时地址变量node p记录一下。

至于查询，操作其实跟插入一摸一样的逻辑。只是处理结果的方式不一样
比如说，没有路径这种情况如果发生，就证明里面没有这个字符串。而能顺利把字符串遍历完
，那就说明存在这个字符串，而且最后的p就是那个字符串尾部的那个node，这时直接查看这个node的
统计值即可。这就是查询。