如何理解我们tr[N][N]的含义

Trie树中有个二维数组tr[N][26]，表示当前结点的儿子，如果没有的话，可以等于++idx。Trie树本质上是一颗多叉树，对于字母而言最多有26个子结点。所以这个数组包含了两条信息。比如：tr[1][0]=2表示1结点的一个值为a的子结点为结点2。如果tr[1][0] = 0，则意味着没有值为a子结点。这里的tr[N][26]相当于链表中的ne[N]。

void insert(char str[])
{
    int p = 0; //从根结点开始遍历
    for (int i = 0; str[i]; i ++ )
    {
        int u =str[i] - 'a';
        if (!tr[p][u]) tr[p][u] = ++ idx; //没有该子结点就创建一个
        p =tr[p][u]; //走到p的子结点
    }

    cnt[p] ++;
}

本题完整c++代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int tr[N][26],cnt[N];
int idx;
char str[N];
void insert(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!tr[p][u])tr[p][u]=++idx;
        p=tr[p][u];
    }
    cnt[p]++;
}
int query(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!tr[p][u])return 0;
        p=tr[p][u];
    }
    return cnt[p];
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        char x;
        memset(str,0,sizeof str);
        cin>>x>>str;
        if(x=='Q')cout<<query(str)<<endl;
        if(x=='I')insert(str);
    }
    return 0;
}