算法►字符串►Trie

(可持久化) Trie 树

字典树

顾名思义，字典树就是支持像字典一样加入和查询字符串的树形数据结构，实现如下：

namespace Trie {
    int Next[N][K], cnt, tag[N];

    void Insert (char *s) {
        int n = strlen(s + 1), now = 0;
        for (int i = 1; i <= n; i++) {
            int c = s[i] - 'a';
            if (!Next[now][c]) Next[now][c] = ++cnt;
            now = Next[now][c];
        }
        tag[now]++;
    }

    int Find (char *s) {
        int n = strlen(s + 1), now = 0;
        for (int i = 1; i <= n; i++) {
            int c = s[i] - 'a';
            if (!Next[now][c]) return false;
            now = Next[now][c];
        }
        return tag[now];
    }
}

0/1 Trie

在很多问题中，字符串仅由 $0$ 和 $1$ 构成，这些问题存在一定的共性。

维护异或极值

考虑如下问题，给定一颗带边权的树，求 $\max\limits_{i,j\in[1,n]} \oplus Path(i,j)$。

由异或的性质，可知 $\oplus Path(i,j)=\oplus Path(root,i)\oplus Path(root,j)$。

所以可以把所有从根开始的路径的异或和表示成一个数字，这样就将问题转化成了求任意两个数字的异或的最大值，可以用 $\rm 0/1~Trie$ 解决。

维护异或和

考虑如下问题，给一些数，维护它们的异或和，支持插入，删除和全局 $+1$。

对于异或和的维护，发现 $sum=\sum_{i=0}^k2^i\times [num_i\equiv 1\pmod 2]$。

其中 $sum$ 表示异或和，$num_i$ 表示所有数中二进制的第 $i$ 位为 $1$ 的数量。这个式子体现在 $\rm 0/1~Trie$ 上就是对于所有以父亲边为 $1$ 的结点为根的子树中有多少个 $\rm Tag$，令 $\rm Tag$ 的数量为 $num$，这些结点的深度为 $k$，它们对答案的贡献即为 $num\%2\times 2^k$。

对于实现全局 $+1$ 操作，从低位到高维建 $\rm 0/1~Trie$，考虑将一个二进制数 $+1$ 的一般操作，即找到从低位到高位的第一个 $0$，将它变成 $1$，数位比它低的 $1$ 全部变成 $0$。 而这个做法体现在 $\rm 0/1~Trie$ 上可以将一个结点的两条指向儿子的出边交换，再递归向交换后的 $0$ 边迭代操作。

$0/1$ Trie 合并

与线段树合并类似，实现如下：

void Merge (int &p, int k) {
    if (!p || !k) { p = p + k; return; }
    tag[p] += tag[k];
    Merge(l[p], l[k]), Merge(r[p], r[k]);
    Push_up();
}

需要注意的是，Trie 树合并和线段树合并一样，只有当每次合并的集合没有交集的时候复杂度才是 $\Theta(n\log n)$ 的。

可持久化 Trie 树

可持久化 Trie 的实现方式和可持久化线段树的方式是相似的，即每次只修改被添加或值被修改的节点，而保留没有被改动的节点，在上一个版本的基础上连边，使最后每个版本的 Trie 树的根遍历所能分离出的 Trie 树都是完整且包含全部信息的。实现如下：

namespace Trie {
    int rt[N << 5], Next[N << 5][2], cnt, tag[N << 5];

    void Build (int &x, int y, int k, int pos) {
    	if (pos < 0) return;
        x = ++cnt;
        if (!pos) tag[x]++;
        tag[x] += tag[y];
        int d = (k & (1 << pos)) != 0;
        Next[x][d ^ 1] = Next[y][d ^ 1];
        Build(Next[x][d], Next[y][d], k, pos - 1);
    }

    int Query (int x, int y, int k, int pos) {
    	if (!x) return 0;
        int d = (k & (1 << pos)) != 0;
        return tag[x] - tag[y] + Query(Next[x][d], Next[y][d], k, pos - 1);
    }
}

经典例题

[LG4735] 最大异或和

可持久化 $0/1$ Trie 模板题。

考虑记所有的前缀和，答案变为统计 $x\oplus sum_n$ 在 $[l-1,r-1]$ 这个区间的 $0/1$ Trie 中的最大异或值。

[CF455B] A Lot of Games

显然直接建立 Trie 树，每次相当于向 Trie 树的子树内走一步，不能走者为负。

考虑设 $f$ 表示是否存在必胜策略，$g$ 表示是否存在必败策略，转移显然。

对 $f_{root}$ 和 $g_{root}$ 分四种情况讨论，每种情况下的答案易得。需要注意的是，如果先手既存在必胜策略又存在必败策略，那他可以故意输以获得下一局的先手，然后在最后一局获得胜利。

[CF888G] Xor-MST

$\rm Trie+Boruvka$。

考虑将所有树插入一个 Trie 中，枚举到某个连通块时将其中所有点从 Tire 中删除，再用连通块中每个结点从 Trie 中查找出最小边权，完成后再将连通块中的点权加回去。

发现一个性质，每次合并的连通块都是 Trie 中某个节点的左右子树，再由 Trie 的性质，我们甚至不需要把 Trie 建出来，只需要将 A 排序，二分 Trie 的左右儿子，再将其中一个儿子的所有结点建 Trie，用另一个儿子中的所有结点在其中查找连通块之间的最小边权即可。

由于每个结点最多被加进 Trie 树 $\log n$ 次，每次复杂度为 $\log W$，所以总时间复杂度为 $\Theta(n\log n\log W)$。