可持久化数据结构小结

可持久化数据结构

可持久化

首先需要介绍可持久化的概念。可持久化就是，保存下来的每一次变化，所影响的那些节点。干说会比较抽象，所以我们以两道题目为例子，来展示可持久化的作用和含义。

可持久化tire树

可以用一张图来展示，可持久化tire树的操作。

当我们，插入一个新节点时，直接从该节点指向除了要插入的下一个点，外的其他再上一个版本上连接在该点上的点。

例如，我们在插入第二个单词时，先把根节点直接复制，接着连接在上一个版本的根节点上的除了r外的有c，则直接从根节点，连一条边指向上一个版本的c，接着正常的连接r。接着递归r，看是否r上在上个版本中是否与出了要连接的a外的其他点，这里的话，可以看出r是一个全新的节点，所以不存在这些情况。就直接连接a即可，接着递归a，也是一样的操作。

接下来，我们以一道题目为例

最大异或和

对这题，而言，我们通过分析，可以知道，如果我们想知道x在[l.r]中，找到的能满足最大异或和的p，设sx为异或前缀和，则

\[s_p \bigoplus s_{p+1} \bigoplus ... \bigoplus s_n \bigoplus x=s_{p-1} \bigoplus s_n \bigoplus x

因此，我们的问题转化为，在[l,r]区间中找到s(p-1)使得该式子最大。

插入问题，好解决，如同我们介绍的一样解决即可。

而查询时，因为，我们限制了[l,r]，因此，我们枚举r版本的树时，需要限制，我们递归的子树中最大的下标要

大于等于

#include<bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10,M = 25*N;
int s[N],n,m;
int tr[M][2],max_id[M],idx;
int root[N];

void insert(int i,int k,int p,int q)
{
    if(k<0)
    {
        max_id[q]=i;
        return;
    }
    int v = s[i]>>k&1;
    if(p) tr[q][v^1]=tr[p][v^1];
    tr[q][v]=++idx;
    insert(i,k-1,tr[p][v],tr[q][v]);
    max_id[q]=max(max_id[tr[q][v]],max_id[tr[q][v^1]]);
}

int query(int u,int C,int l)
{
    int p = u;
    
    for(int i=23;i>=0;i--)
    {
        int v = C>>i&1;
        if(max_id[tr[p][v^1]]>=l) p=tr[p][v^1];
        else p = tr[p][v];
    }
    
    return C^s[max_id[p]];
}

int main()
{
    scanf("%d%d",&n,&m);
    max_id[0]=-1;
    root[0]=++idx;
    insert(0,23,0,root[0]);
    
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        root[i]=++idx;
        s[i]=s[i-1]^x;
        insert(i,23,root[i-1],root[i]);
    }
    
    char op[2];
    int l,r,x;
    for(int i=0;i<m;i++)
    {
        scanf("%s",op);
        if(*op=='A')
        {
            scanf("%d",&x);
            n++;
            root[n]=++idx;
            s[n]=s[n-1]^x;
            insert(n,23,root[n-1],root[n]);
        }
        else
        {
            scanf("%d%d%d",&l,&r,&x);
            printf("%d\n",query(root[r-1],s[n]^x,l-1));
        }
    }
    return 0;
}

可持久化线段树(主席树)

可持久化线段树，在操作上，与tire有一些不同，看图比较好理解。

我们的每一个新版本，都只是创建出来了改变的那一部分，然后将其，再替换回去。

所以每一版本的线段树都是和上一版本的结构完全相同的。

同时与一般的线段树不太相同，它其中维护的是，左右节点的指针，而不是左右边界。

同时

难以进行区间修改

可持久化数据结构小结