可持久化Trie总结

刚写了几篇Trie的题解，感觉Trie树还是很优美的。

到网上找了找，还没有发现可持久化Trie的教程。于是扒了几篇代码学习了一下。

其实一直沉迷ls地下城

看完了也知道为什么没有教程了，因为其实实质上就是一个动态开点的Trie。

前置姿势：主席树。

从一个例题看吧

Description

给定一个非负整数序列 {a}，初始长度为 N。
有 M个操作，有以下两种操作类型：

1 、A x：添加操作，表示在序列末尾添加一个数 x，序列的长度 N+1。
2 、Q l r x：询问操作，你需要找到一个位置 p，满足 l<=p<=r，使得：

a[p] xor a[p+1] xor … xor a[N] xor x 最大，输出最大是多少。

Input

第一行包含两个整数 N ，M，含义如问题描述所示。
第二行包含 N个非负整数，表示初始的序列 A 。

接下来 M行，每行描述一个操作，格式如题面所述。

Output

假设询问操作有 T个，则输出应该有 T行，每行一个整数表示询问的答案。

Sample Input

5 5

2 6 4 3 6

A 1

Q 3 5 4

A 4

Q 5 7 0

Q 3 6 6

对于测试点 1-2，N,M<=5 。

对于测试点 3-7，N,M<=80000 。

对于测试点 8-10，N,M<=300000 。

其中测试点 1, 3, 5, 7, 9保证没有修改操作。

对于 100% 的数据， 0<=a[i]<=10^7。

Sample Output

4

5

6

首先把式子拆成前缀和的形式，大概就是$sum[p-1]\ xor \ sum[n] \ xor \ x$，其中$sum[n] \ xor \ x$是个定值，那么也就是把这个定值在l-r的区间内求异或的最大值。

要从一个区间中提取信息而且不修改，可以想到前缀和的思想。

这样就用主席树的思想，对于每个串都新开一个根节点，串里的节点存一下从根节点到这个点所形成的串有多少个和它一样的。

这样询问的时候就是r的串所在节点的值减去l的对于节点的值，看看是不是大于0。大于0就往下走，小于0就走另一边。

为了满足最大，当然是要走不一样的更优一些。

#include <cstdio>
#include <algorithm>
#define N 600010
using namespace std;
int val[N*35],ch[N*35][2],root[N],n,m,sums,l,r,sz,x,cnt;
char s[10];
void insert(int &now,int x,int dep)
{
    val[++sz]=val[now]+1,ch[sz][0]=ch[now][0],ch[sz][1]=ch[now][1],now=sz;
    if (dep==-1) return;
    if ((x>>dep)&1)
        insert(ch[now][1],x,dep-1);
    else
        insert(ch[now][0],x,dep-1);
}
int query(int l,int r,int x,int dep)
{
    if (dep==-1)
        return 0;
    int k=(x>>dep)&1;
    if (val[ch[r][k^1]]-val[ch[l][k^1]]>0)
        return (query(ch[l][k^1],ch[r][k^1],x,dep-1)|(1<<dep));
    else
        return query(ch[l][k],ch[r][k],x,dep-1);
}
main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d",&x),sums^=x,cnt++,
        root[i]=root[i-1],insert(root[i],sums,31);
    for (int i=1;i<=m;i++)
    {
        scanf("%s",s);
        if (s[0]=='A')
            scanf("%d",&x),cnt++,sums^=x,
            root[cnt]=root[cnt-1],insert(root[cnt],sums,31);
        else
        {
            scanf("%d%d%d",&l,&r,&x);
            l=max(0,l-1),r=max(0,r-1);
            if (!l)
                printf("%d\n",max(query(root[l-1],root[r],sums^x,31),sums^x));
            else
                printf("%d\n",query(root[l-1],root[r],sums^x,31));
        }
    }
}

其实做了几个题发现可持久化trie主要的应用就是求下区间和某数异或值最大的数，或者某个串放到一个串区间里面匹配前缀。感觉还是比较容易看出来的。

也就是前面几篇，泥萌自己翻吧。