可持久化trie树

· · 算法·理论

正常的 trie 树能解决一些字符串问题，0/1 trie 能解决最大异或和问题。但是如果每次询问是针对一个区间的，那么普通 trie 就不好做了，此时就需要可持久化 trie 树。

类似可持久化线段树，对于每个版本新建一个 root （相当于每个前缀建），在插入时该继承的继承，改修该的修改。和普通 trie 一样，tr_{p,u} 表示 p 号节点连向字符为 u 的点的编号。那么每次插入的流程如下：

  1. 新建当前字符串的根节点 p，并记 pre 表示上一个字符串的根节点。
  2. 若当前字符为 u，那么给 u 新开一个节点 tr_{p,u}=++cnt。
  3. 同时还要继承 pre 的其他字符，也就是对于一个字符 ch \ne u，tr_{p,ch}=tr_{pre,ch}，相当于直接连过去。
  4. 接着让 p=tr_{p,u},pre=tr_{pre,u}，向下建树，重复 1,2,3，直到建完。

举个例子：若当前要插入这些字符串：\texttt{cat,cup,soup,cut}。（黑色点为根节点）

第一次： 第二次： 第三次： 第四次：

这样，一棵 trie 就建好了，从第 i 个 root 出发，我们能访问到 1 \sim i 的所有字符串，这就把问题解决一半了。只需沿用可持久化线段树的思想，前缀相减即可。

具体来说，我们需要引入一个 last 数组来表示每个点是第几次被插入的，如果在遍历过程中发现有个点的 last < l 了，那么他就不在我们的询问范围内，就可以直接返回了。如下图，红色数字就是每个节点的 last 值：

例如我们要访问区间 [2,3]，则应从 root_3 进入，访问 last\ge 2 的点，下图红色点和边可以被访问：

code

以 0/1 trie 为例。

插入：

void insert(int pre,int p,int i,int k){//pre上一个数字的root，p当前数字的root，i是第几次插入的，k是这个数字要拆分的二进制位数
    if(k<0){
        last[p]=i;//建完了，返回
        return;
    }
    int u=(num[i]>>k)&1;
    if(pre)tr[p][u^1]=tr[pre][u^1];//继承上一个的字符
    tr[p][u]=++cnt;
    insert(tr[pre][u],tr[p][u],i,k-1);//递归新建节点
    last[p]=max(last[tr[p][0]],last[tr[p][1]]);//更新last，从子树更新上来，也可以直接赋为i
}

查询（这里返回的是最大值的下标）：

int query(int p,int x,int l,int k){//p当前节点，对于区间[l,r]赋为root[r]，x是要查询的数，l左边界，来判断当前数是否在[l,r]中，k是二进制下第几位
    if(k<0)return last[p];//last 相当于这个数的下标，因为我们是按前缀顺序插入的
    int u=(x>>k)&1;
    if(last[tr[p][u^1]]>=l)return query(tr[p][u^1],x,l,k-1);//在区间[l,r]中就优先走有贡献的位置
    return query(tr[p][u],x,l,k-1);//否则不产生贡献，向下走
}

例题

P4735 最大异或和

板子。先记 s 为 a 的前缀异或和，那么询问的式子就可以转化为求一个 p \in [l-1,r-1]，使得 x \oplus s_n \oplus s_p 最大。x\oplus s_n 是已知的，那么就只需要用可持久化 trie 在 [l-1,r-1] 中查找一个 s_p 让他们异或起来值最大就行了。

注意：最好一开始 insert 一个 0，因为很多题都是前缀和查询，会涉及到 l-1=0 的情况，不管他就 gg 了。

P5283 [十二省联考 2019] 异或粽子

还是用 s 表示前缀异或和，那么我们就要求前 k 大的 s_r \oplus s_{l-1}。先不考虑前 k 大的限制，思考最大怎么做。一个想法是固定右端点，求出对于这个右端点最大的是什么。这样再在每个右端点中取 \max 就得到答案了。

再回头看题，前 k 大，每一对都是两个数 s_i,s_j 异或在一起，不难想到这道题。我们可以沿用此题的思路，把每个 r 对应的最大的点的信息放入一个堆中。具体信息有：当前的右端点、和右端点异或起来的最大值所在位置、这个最大值所在位置的区间范围（一个左端点一个右端点）、当前最大值是什么。有了这些，我们就每次拿出最大的那个元素，并把答案累加。然后设当前最大值位于 pos，右端点位于 rx，pos所在区间为 [l,r]，因为不能有重复区间，因此在 [l,pos-1] 中找一个和 rx 最大的位置，再在 [pos+1,r] 中找一个，把他们放入堆中，重复 k 次就行了。