可持久化Trie树整理

@zryabc  January 30, 2019

前言

Trie树(字典树)是一种比较简单的数据结构,一般人yy一下也能想到。

具体而言,路径用$pa[maxnode][sigmasize]$来表示。如果对于英文字母来说,就是$pa[M][26]$,这种情况下整棵树就是一棵不满的26叉树。

使用时往往也需要在节点上同时维护信息。

插入代码

void Insert(char *s,int v){
    int u=0,len=strlen(s);
      for(int i=0;i<n;i++){
           int op=s[i]-'a';
          if(!pa[u][op]){
            memset(pa[tt+1],0,sizeof(pa[tt+1]));
              val[tt+1]=0;
             pa[u][op]=++tt;
        }
          u=pa[u][op];
          val[u]=v;
    }
}

下面可持久化一下就好了,原理并不复杂。

void Insert(int od,int rt,int num,int id){
    cnt[rt]=cnt[od]+1;
    for(int i=16;i>=0;i--){
        int op=(num>>i&1);
        pa[rt][op]=++tt;
        pa[rt][!op]=pa[od][!op];
        rt=pa[rt][op];
        od=pa[od][op];
        cnt[rt]=cnt[od]+1;
        val[rt]=id;
    }
}

添加新评论