可持久化字典树 详解

😊 | 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。

二、可持久化字典树 详解

我们要对一个长度为 n n n 的数组 a a a 维护以下操作：

1. 在数组的末尾添加一个数 x x x，数组的长度 n n n 自增 1 1 1。
2. 给出查询区间 [ l , r ] [l,r] [l,r] 和一个值 k k k，要求找到一个 p p p，求当 l ≤ p ≤ r l\le p\le r l≤p≤r 时， k ⊕ ⨁ i = p n a i k \oplus \bigoplus^{n}_{i=p} a_i k⊕⨁i=pn​ai​最大。

我们发现，求区间异或和实际上是一个繁琐的操作。由于异或操作 ⊕ \oplus ⊕满足可减性，因此我们考虑用前缀和进行维护，则有： a [ p ]   x o r   a [ p + 1 ]   x o r   . . .   x o r   a [ n ]   x o r   x = s [ p − 1 ]   x o r   s [ n ]   x o r   x a[p]\ xor\ a[p + 1]\ xor\ ...\ xor\ a[n]\ xor\ x = s[p - 1] \ xor\ s[n]\ xor\ x a[p] xor a[p+1] xor ... xor a[n] xor x=s[p−1] xor s[n] xor x 然后我们只需要对 s [ ] s[] s[]进行维护，就能很方便的查询到区间异或值。实际上，我们将问题转化为：已知 v a l = s [ n ]   x o r   x val = s[n] \ xor\ x val=s[n] xor x，求 p ∈ [ l − 1 , r − 1 ] p \in [l - 1, r - 1] p∈[l−1,r−1]，使 s [ p ]   x o r   v a l s[p] \ xor\ val s[p] xor val取得最大值。

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

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

下面放一个可持久化0-1Trie的板子：

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;
            //新建节点
            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;
            if(sum[ch[r][c ^ 1]] - sum[ch[l][c ^ 1]]){
                ans = ans + (1