可持久化字典树 详解

😊 | Powered By HeartFireY | Persistent Trie

📕 | 需要的前导知识：字典树(Trie)、可持久化数据结构理论(Persistent Data Structure Theory)

一、可持久化字典树 简介

首先让我们来回顾一下字典树的相关内容：Tire 字典树 详解

字典树是一种利用边权映射到字符集，将字符串保存到一棵树上的数据结构，在查询公共前缀、字符串排序、词频统计方面有着十分优秀的性质。

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

在字典树的拓展部分学习过程中，我们提到了一种特殊的字典树：0-1 Trie，而在可持久化字典树中，大部分题目都是以0-1 Trie的形式出现的。

0-1 Trie 是建立在字典树基础上，专门用于维护异或和(支持修改、删除、重新插入、全局加一)的数据结构。在维护异或和的时候，我们需要从低位到高位建立0-1 Trie。

二、可持久化字典树 详解

我们要对一个长度为 的数组

1. 在数组的末尾添加一个数，数组的长度自增。
2. 给出查询区间和一个值，要求找到一个，求当时，最大。

我们发现，求区间异或和实际上是一个繁琐的操作。由于异或操作满足可减性，因此我们考虑用前缀和进行维护，则有：

然后我们只需要对进行维护，就能很方便的查询到区间异或值。实际上，我们将问题转化为：已知，求，使取得最大值。

我们可以延续可持久化线段树的思路，考虑每次的查询都查询整个区间。我们只需把这个区间建一棵 Trie 树，将这个区间中的每个树都加入这棵 Trie 中，查询的时候，尽量往与当前位不相同的地方跳。

查询区间，只需要利用前缀和和差分的思想，用两棵前缀 Trie 树（也就是按顺序添加数的两个历史版本）相减即为该区间的线段树。再利用动态开点的思想，不添加没有计算过的点，以减少空间占用。

struct trie_persistent{
    int cnt;
    int ch[maxn * 24][2], sum[maxn * 24];

    inline int insert(int x, int val){
        int o, y; o = y = ++cnt;
        for(int i = 23; i >= 0; i++){
            ch[y][0] = ch[x][0];
            ch[y][1] = ch[x][1];
            sum[y] = sum[x] + 1;            //更新位置计数
            int tmp = (val & (1 << i)) >> i;
            //新建节点
            x = ch[x][tmp];
            ch[y][tmp] = ++cnt;
            y = ch[y][tmp];
        }
        sum[y] = sum[x] + 1;
        return o;
    }

    inline int query(int l, int r, int val){
        int ans = 0;
        for(int i = 23; i >= 0; i--){
            int c = (val & (1 << i)) >> i;
            if(sum[ch[r][c ^ 1]] - sum[ch[l][c ^ 1]]){
                ans = ans + (1 << i);
                r = ch[r][c ^ 1];
                l = ch[l][c ^ 1];
            }
            else{
                r = ch[r][c];
                l = ch[l][c];
            }
        }
        return ans;
    }
}      

struct Trie_Persistent{
    const static int LetterSize = 5; // 字符集大小
    const static int TrieSize = 20 * ( 1e5 + 50); // 可能的所有节点总数量
    int tot; // 节点总数
    //节点类型
    struct node{
        int ptr[LetterSize]; // trie_node_ptr[]
        int cnt[LetterSize]; // 维护字符集数目
    }tree[TrieSize];
    // 获取字符集哈希编号 ， 必须在 [0 , LetterSize) 之内
    inline int GetLetterIdx(int c){return c - 'a';}
    // 插入字符串 str , 上一个副本是 f
    int insert(const char * str ,int f){
        int len = strlen( str );
        int res = tot++; // 建立虚拟根结点
        tree[res] = tree[f]; // 初始化
        int cur = res; // 当前指针
        for(int i = 0 ; i < len ; ++ i){
            int idx = GetLetterIdx( str[i] ); // 获取字符编号
            int p = tot ++ ;  // 创建下一个虚拟节点
            tree[cur].cnt[idx] ++ ;
            tree[cur].ptr[idx] = p;
            f = tree[f].ptr[idx]; // 上一个副本的指针更新
            tree[p] = tree[f];  // updata information;
            cur = tree[cur].ptr[idx]; // updata ptr
        }
        return res;
    }
    // 在 [l ,r] 副本中查找字符串str
    // 参数带入( str , root[l-1] , root[r])
    int find(const char * str , int l ,int r){
        int len = strlen(str);
        for(int i = 0 ; i < len ; ++ i){
            int idx = GetLetterIdx ( str[i] ); // 获取字符Hash
            int cnt = tree[r].cnt[idx] - tree[l].cnt[idx];
            if(!cnt) return 0;
            l = tree[l].ptr[idx];
            r = tree[r].ptr[idx];
        }
        return 1;
    }
    //初始化函数
    void init(){ 
        tot = 1;
        for(int i = 0 ; i < LetterSize ; ++ i) tree[0].ptr[i] = 0 , tree[0].cnt[i] = 0;
    } 
}trie;