可持久化資料結構小結

可持久化資料結構

可持久化

首先需要介紹可持久化的概念。可持久化就是，儲存下來的每一次變化，所影響的那些節點。幹說會比較抽象，是以我們以兩道題目為例子，來展示可持久化的作用和含義。

可持久化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有一些不同，看圖比較好了解。

我們的每一個新版本，都隻是建立出來了改變的那一部分，然後将其，再替換回去。

是以每一版本的線段樹都是和上一版本的結構完全相同的。

同時與一般的線段樹不太相同，它其中維護的是，左右節點的指針，而不是左右邊界。

同時

難以進行區間修改

可持久化資料結構小結