Trie

字典树就是把所有单词插入一颗搜索树里。这样可以在线性时间内完成查找和维护信息。

应用有，于是他错误的点名开始了和补退选。

\(code\)：

void insert(char *str)
{
    int len=strlen(str),cur=1;
    for(int i=0;i<len;++i)
    {
        int ch=str[i]-'a';
        if(!trie[cur][ch])
            trie[cur][ch]=++tot;
        cur=trie[cur][ch];
    }
}
int search(char *str)
{
    int len=strlen(str),cur=1;
    for(int i=0;i<len;++i)
    {
        int ch=str[i]-'a';
        cur=trie[cur][ch];
    }
    return ......//一般都有附加信息
}

\(01Tire\)

\(code\)：

void insert(int x)
{
    int p=0;
    for(int i=30;i>=0;--i)
    {
        int ch=(x>>i)&1;
        if(!trie[p][ch]) 
            trie[p][ch]=++tot;
        p=trie[p][ch];
    }
}
int query(int x)
{
    int p=0,sum=0;
    for(int i=30;i>=0;--i)
    {
        int ch=(x>>i)&1;
        if(trie[p][!ch])
        {
            p=trie[p][!ch];
            sum+=1<<i;
        }
        else p=trie[p][ch];
    }
    return sum;
}

可持久化\(Tire\)

\(code\)：

void insert(int x)
{
    int p=root[root_cnt];
    root[++root_cnt]=++tot;
    for(int i=30;i>=0;--i)
    {
        int ch=(x>>i)&1;
        siz[tot]=siz[p]+1;
        trie[tot][ch]=tot+1;
        trie[tot][!ch]=trie[p][!ch];
        p=trie[p][ch];
        tot++;
    }
    siz[tot]=siz[p]+1;
}
int query(int l,int r,int x)
{
    int ls=root[l],rs=root[r],sum=0;
    for(int i=30;i>=0;--i)
    {
        int ch=(x>>i)&1;
        if(siz[trie[rs][!ch]]-siz[trie[ls][!ch]]>0)
            ls=trie[ls][!ch],rs=trie[rs][!ch],sum|=1<<i;
        else
            ls=trie[ls][ch],rs=trie[rs][ch];
    }
    return sum;
}

Trie

原文：https://www.cnblogs.com/lhm-/p/12229437.html