[数据结构与算法]可持久化trie树

https://blog.csdn.net/weixin_43959739/article/details/84922554

详情可以看这一篇，或者李煜东老师的书p253.

下面来介绍一下本人理解的 建立可持久化trie树的过程。

1.创建新版本的时候什么时候和之前版本的节点发生关系?

私以为，不妨以下图为例，具体来说，就是将当前版本与之前版本都从根节点出发，将当前版本该节点出发没有，之前版本有的一些信息进行连接，很好理解，因为最新版本相当于目前所有版本的总和

因此之前的信息就通过这种方式维护即可，那么问题来了，对于当前节点，那些都有的信息应该怎么进行处理呢？答案是，将之前版本与目前同时向下遍历，重复上述连接信息操作，便可以得到一颗信息完全的可持久化字典树了。（不妨自己画一下试试）。

3.对于最大异或和这题，注意s[0]需要insert 个 0，因为这样才能求出 l = 1, r = n 时候的最值。

2.该开辟多少空间

对于数位题，由于范围一般是 1e6左右，因此，开N * 24或者其他，可以保证空间需求。

3.时间问题

开辟的时间复杂度是总长度的线性函数。

4.对于空节点idx为什么要赋为-1

5.对持久化trie的每个节点额外维护一个信息version，表示其所属的持久化版本，显然一个节点的version等于其子节点中最大的版本号（因为子节点要么是连向之前的版本，要么创建了该节点后再创建子节点）。

AcWing 256. 最大异或和 - AcWing

’

例题

最大异或和

#include<bits/stdc++.h>
using namespace std;
const int N =600010;
int trie[N * 24][2],lastest[N * 24];//latest记录节点归属问题
int s[N],root[N],n,m,tot;
void  insert(int i , int k , int p ,int q)
{
    if(k < 0)//超过了遍历范围
    {
        lastest[q] = i;
        return ;
    }
    int c = s[i] >> k & 1;    //获取当前位
    if(p) trie[q][c^1] = trie[p][c^1];
    trie[q][c] = ++tot;
    insert(i,k-1,trie[p][c],trie[q][c]);
    lastest[q] = max(lastest[trie[q][0]],lastest[trie[q][1]]);
}

int ask(int now,int val,int k,int limit)
{
    if(k < 0 ) return s[lastest[now]] ^ val;
    int c = val >> k & 1;
    if(lastest[trie[now][c^1]] >= limit) 
        return ask(trie[now][c^1],val,k - 1,limit ); //按位查询
   else if(lastest[trie[now][c]] >= limit) return ask(trie[now][c],val,k - 1,limit ); //按位查询
   return 0;
}


int main()
{
    cin >> n >> m;
    lastest[0] = -1;
    root[0] = ++tot;
    insert(0,23,0,root[0]);
    int x;
    for(int i = 1 ;  i <= n ; i++)
    {
        cin >> x;
        s[i] = s[i - 1]^ x;
        root[i] = ++tot;
        insert(i, 23 , root[i - 1],root[i]);
    }
    
   // for(int i = 0;  i <= 100 ; i ++) cout <<lastest[i]<<" ";
    char op,y;
    for(int i = 1 ; i <= m  ; i++)
    {
        cin >> op;
        if(op == 'A')
        {
            cin >> x;
            root[++n] = ++tot;
            s[n] = s[n - 1] ^ x;
            insert(n, 23 , root[n - 1],root[n]);
        }
        else if(op =='Q')
        {
            int l,r;
            cin >> l >> r >> x;
            printf("%d\n",ask(root[r - 1], x^s[n], 23, l - 1));
            if(n == 0) cout <<"az";
        }
        
    }
   // for(int i = 1;  i <= 100 ; i ++) cout <<lastest[i]<<" ";
    
    
 
    
}