Trie

字典树

struct Trie
{
    struct node
    {
        int nex[27];ll pfx,wd;
        void clear(){mem(nex,0);pfx=wd=0;}
    }t[1000000];

    struct memory
    {
        static const int __=1e5+5;
        int idx,trash[__];

        int get()
        {
            if(trash[0])return trash[trash[0]--];
            return ++idx;
        }

        void del(int x){trash[++trash[0]]=x;}

        void clear(){idx=trash[0]=0;}
    }M;

    Trie() {M.clear();t[0].clear();}

    int get_idx(char *s)
    {
        int x=0;
        for(int i=1;s[i];i++)
        {
            int k=s[i]-'a'+1;
            if(!t[x].nex[k])return -1;
            x=t[x].nex[k];
        }
        return x;
    }

    int insert(char *s,ll val,bool prefix=false)
    {
        int x=0;
        for(int i=1;s[i];i++)
        {
            int k=s[i]-'a'+1;
            if(!t[x].nex[k])
            {
                int idx=M.get();
                t[x].nex[k]=idx;
                t[idx].clear();
                t[idx].nex[0]=x;
            }
            x=t[x].nex[k];
            t[x].pfx+=val;
        }
        if(!prefix)t[x].wd+=val;
        return x;
    }

    void erase(char *s,ll val,bool prefix=false)
    {
        int x=0,i;
        for(i=1;s[i];i++)
        {
            x=t[x].nex[s[i]-'a'+1];
            t[x].pfx-=val;
        }
        if(!prefix)t[x].wd-=val;
        for(--i;x && !t[x].pfx;i--)
        {
            M.del(x),x=t[x].nex[0];
            t[x].nex[s[i]-'a'+1]=0;
        }
    }

    ll search(char *s,bool prefix=false)
    {
        int x=0;
        for(int i=1;s[i];i++)
        {
            int k=s[i]-'a'+1;
            if(!t[x].nex[k])return 0;
            x=t[x].nex[k];
        }
        return prefix?t[x].pfx:t[x].wd;
    }

    void update(char *pre,char *now)
    {
        int x=get_idx(pre);
        if(!~x)
        {
            puts("Empty");
            return;
        }
        int y=get_idx(now);
        if(~y)
        {
            puts("Conflict");
            return;
        }
        node p=t[x];
        erase(pre,p.pfx,true);
        int z=insert(now,p.pfx,true);
        t[z].wd=p.wd;
        for(int i=1;i<=26;i++)
        {
            t[z].nex[i]=p.nex[i];
            if(p.nex[i])t[p.nex[i]].nex[0]=z;
        }
    }

    void clear(){M.clear();t[0].clear();}
}T;

01字典树

struct Trie
{
    struct node
    {
        int nex[2],num;
        void clear() {mem(nex,0),num=0;}
    }t[10000000];

    Trie() {t[0].clear();}

    void insert(int x,int val)
    {
        int y=0;
        for(int i=1<<30;i;i>>=1)
        {
            int k=(x&i)?1:0;
            if(!t[y].nex[k])
                t[y].nex[k]=M.get();
            y=t[y].nex[k];
            t[y].num+=val;
        }
    }

    int get_max(int x)
    {
        int y=0,ans=0;
        for(int i=1<<30;i;i>>=1)
        {
            int k=(x&i)?1:0;
            if(t[t[y].nex[!k]].num)
                y=t[y].nex[!k],ans|=i;
            else y=t[y].nex[k];
        }
        return ans;
    }
}T;