Trie

作者: fo0Old | 来源:发表于2017-10-07 13:11 被阅读0次

    字典树

    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;
    

    相关文章

      网友评论

          本文标题:Trie

          本文链接:https://www.haomeiwen.com/subject/ccrjyxtx.html