trie

· · 个人记录

普通 trie

这就是一棵 trie 树，有很多的节点，但是关键字并不在节点上，而是在路径上，这是一个易错点。

一般的运用是开一棵关于字符的 trie 或者是 01trie。

我们可以来看几道题目。

字符串中的 trie

题目大意是给定 n 个句子，句子中有多个单词，给定 m 个询问，每次给定一个单词，查找这个单词在多少个句子出现过。(1\le m\le 10^4,1\le n\le 10^3,1\le len\le 5\times 10^3)

最暴力的想法是对于每一个询问，都暴力跑一遍 n 个字符串。但是这样满打满算的复杂度是 \Theta(len\cdot n\cdot m)。

很明显会超时，考虑使用字典树。

建 n 棵字典树，每一棵字典树用来标记每个句子的单词出现情况。

然后查询的时候就可以通过枚举每一棵字典树快速检索答案。

复杂度是 \Theta(n\cdot m\cdot 20)，20 为每一个单词的最大长度，可过。

那么如何标记每一个单词的出现情况呢？

我们定义一个用来标记节点的数组 final

查询的时候只要看一下 $final$ 有没有值就好了。 贴一下 trie 的代码 ```cpp struct trie{ int nxt[L][26],final[L],idx; void insert(string x){ int s=x.size(),p=0; for(re int i=0;i<s;i++){ int ch=x[i]-'a'; if(!nxt[p][ch]) nxt[p][ch]=++idx; p=nxt[p][ch]; } final[p]=1; } bool query(string x){ int s=x.size(),p=0; for(re int i=0;i<s;i++){ int ch=x[i]-'a'; if(!nxt[p][ch]) return 0; p=nxt[p][ch]; } return final[p]; } }t[N]; ``` * [CF665E](https://www.luogu.com.cn/problem/CF665E) 01trie 根据异或的性质，我们可以通过前缀异或快速求出 $l\sim r$ 的异或和，假设 $s_i$ 表示前 $i$ 个数中的异或和，那么 $s_r\oplus s_{l-1}$ 就是 $\bigoplus_{i=l}^{r} a_i

一个常用的思路，固定住一端，通过求符合条件的另一端达到计数的目的。

很自然的想到固定住 r，通过求符合条件的 l 的数量，就可以求出答案。

现在讲问题转化为如何快速求符合条件的 l 的数量。

考虑建一棵有关 s_i 的 trie，通过检索字典树来进行快速求解。

由于字典树是 01 的形式呈现，不妨把 k 也拆成二进制的形式，从高位到低位枚举。

思考一个小问题，如何判断一个数大于等于 k，如果在高位的二进制中，有一位 k 比这个数小，那么后面的数无论是什么，都是这个数大于 k，当然前提是前面的数都要一样。

接着字典树说，我们假设当前已经找到了第 i 位，数 r 二进制的第 i 位为 c_1，k 的为 c_2，前面的都是相同的。

如果 c_2=0，那么如果字典树中存在与 c_1\oplus 1 的节点，那么肯定接下来的全部都会大于 k，因此答案加上 sz_{nxt_{p,c_1\oplus 1}}，然后检索反方向。

否则的话只能检索 c_1\oplus 1。

最后检索完毕时，因为可以大于等于，所以还要加上 sz_p。

空间该开多大呢？这也是字典树中一个常见的问题，注意到有 n\le 10^6 个数，每个数至多有 31 位，所以开位数乘上数的个数即可。

贴一下 trie 的代码。

struct trie{
    int nxt[N*30][2],sz[N*30],idx;
    void insert(int x){
        int p=0;
        for(int i=30;~i;i--){
            int ch=x>>i&1;
            if(!nxt[p][ch]) nxt[p][ch]=++idx;
            p=nxt[p][ch],sz[p]++;
        }
    }
    int query(int x){
        int p=0,res=0;
        for(int i=30;~i;i--){
            int ch=x>>i&1,ck=k>>i&1;
            if(ck) p=nxt[p][ch^1];
            else res+=sz[nxt[p][ch^1]],p=nxt[p][ch];
            if(!sz[p]) return res;
        }
        return res+sz[p];
    }
}T;

trie 的合并

这个没有什么好讲的，跟其它的形式差不多。

int merge(int x,int y){
    if(!x || !y) return x+y;
    sz[x]+=sz[y],nxt[x][0]=merge(nxt[x][0],nxt[y][0]),nxt[x][1]=merge(nxt[x][1],nxt[y][1]);
    return x;
}

trie 的全局加1

在二进制下，权值加 1，实际上就是交换了左右的儿子，但是有一点很特殊，但是 1 会进位，所以仍然需要递归处理 nxt[p][0]

void addall(int p){
    swap(nxt[p][0],nxt[p][1]);
    if(nxt[o][0]) addall(nxt[p][0]);
}

可持久化 trie

可持久化 trie 是一种常用的东西，它可以很方便的记录历史值，并更新，它的主要原理是：对于每一次修改，只会修改一部分，其它的可以继承前面的。下面以一道例题展开讲述。

题目所求可以转化位 s_{p-1}\oplus s_n\oplus x

而 s_n\oplus x 是一个常数。

因此我们需要找到最大的 s_{p-1},l-1\le p\le r-1

我们可以转化为前缀形式，即通过两棵字典树来计算 [l-1,r-1] 中的字典树的样子。

那么即用 R_{r-1}-R_{l-2} 来算当中 0,1 的个数。

但是发现空间不够开，所以可以考虑可持久化，每次的修改都是一条链。

贴一下字典树的代码

struct trie{
    int idx,nxt[30000005][2],sz[30000005];
    void insert(int x,int y,int z){
        for(re int i=28;~i;i--){
            int ch=z>>i&1;
            if(ch){
                if(!nxt[x][1]) nxt[x][1]=++idx;
                nxt[x][0]=nxt[y][0],x=nxt[x][1],y=nxt[y][1]; 
            }
            else{
                if(!nxt[x][0]) nxt[x][0]=++idx;
                nxt[x][1]=nxt[y][1],x=nxt[x][0],y=nxt[y][0]; 
            }
            sz[x]=sz[y]+1;
        }
    }
    int query(int x,int y,int z){
        int res=0;
        for(re int i=28;~i;i--){
            int ch=z>>i&1;
            if(sz[nxt[x][!ch]]-sz[nxt[y][!ch]]) res+=(1<<i),x=nxt[x][!ch],y=nxt[y][!ch];
            else x=nxt[x][ch],y=nxt[y][ch];
        }
        return res;
    }
}T;
int main(){
    for(re int i=1;i<=n;i++) s[i]=qr()^s[i-1],rt[i]=++T.idx,T.insert(rt[i],rt[i-1],s[i]);
    while(m--){
        char op;
        int l,r,x;
        cin>>op;
        if(op=='A') n++,rt[n]=++T.idx,s[n]=s[n-1]^qr(),T.insert(rt[n],rt[n-1],s[n]);
        else{
            l=qr()-1,r=qr()-1,x=qr();
            if(!l) qw(max(s[n]^x,T.query(rt[r],rt[0],s[n]^x)));
            else qw(T.query(rt[r],rt[l-1],s[n]^x));
            putchar('\n');
        }
    }
    return 0;
}