可持久化字典树

可持久化线段树也是一个经典的可持久化数据结构，多用于$01trie$

前置知识：字典树，最大异或和求法

---

1.例题及解决

这个题目“最大异或和”其实你做过最长异或路径就可以很快的想到要用字典树

记录一下前缀异或和$pre_i$数组，将题目中的式子化简一下就可以将我们的目标转移到一个更好思考的方向上

题目中式子其实就是求一个$p\in [l-1,r-1]$，使$x\oplus pre_n\oplus pre_p$的最大

于是我们就可以把$x\oplus pre_n$丢到$[l-1,r-1]$表示的字典树上去求最大异或路径

而我们实现可持久化$trie$的方式也很简单，记录一个$val$数组表示该点的出现次数，查询时相减就可以知道这位是否能为$1$了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair< int,int >
#define QAQ return ;
#define QWQ return 0;
#define TAT return

const int N=6e5+10, bit=31;

struct Trie
{
    int cnt;
    int rt[N], trie[N*bit][2], val[N*bit];
    //分别表示不同版本的trie的根，字典树与点出现次数 
    
    void insert( int p,int u,int x )//插入操作 
	{
		for( int i=bit;i>=0;i-- )
		{
			val[p]=val[u]+1;//在原基础上修改，该位的出现次数增加 
			if( x&( 1<<i ) )
			{
				if( !trie[p][1] ) trie[p][1]=++cnt;
				trie[p][0]=trie[u][0];//另一方沿用上次的节点 
				p=trie[p][1];
				u=trie[u][1];
			}
			else
			{
				if( !trie[p][0] ) trie[p][0]=++cnt;
				trie[p][1]=trie[u][1]; //意义同上
				p=trie[p][0];
				u=trie[u][0];
			}
		}
		val[p]=val[u]+1;
	}

	int query( int p,int u,int x )
	{
		int ans=0;
		for( int i=bit;i>=0;i-- )
		{
			int t=( 1&( x>>i ) );//得到本位期望走向的位置 
			if( val[trie[p][!t]]-val[trie[u][!t]] ) ans+=( 1<<i ), p=trie[p][!t], u=trie[u][!t];//可以在目前的极高位得到一个1，选择这条路径 
			else                                    p=trie[p][t], u=trie[u][t];//只能选择贡献为0的分支 
		}
		return ans;
	}
    
}tr;

int pre[N];//记录前缀异或和 

int main()
{
//    freopen( "txt.in","r",stdin );
	ios::sync_with_stdio( false );
    cin.tie( nullptr ), cout.tie( nullptr );
    int n, m;
    cin>>n>>m;
    tr.rt[0]=++tr.cnt, tr.insert( tr.rt[0],0,0 );
    for( int i=1, x;i<=n;i++ ) cin>>x, pre[i]=pre[i-1]^x;
    for( int i=1;i<=n;i++ ) tr.rt[i]=++tr.cnt, tr.insert( tr.rt[i],tr.rt[i-1],pre[i] );//从根节点开始新建一颗trie 
    for( int i=1, l, r, x;i<=m;i++ )
    {
    	char op;
    	cin>>op;
    	if( op == 'A' )//增加新的数的思路与上面相同 
    	{
    		n++;
    		cin>>x;
    		pre[n]=pre[n-1]^x;
    		tr.rt[n]=++tr.cnt;
			tr.insert( tr.rt[n],tr.rt[n-1],pre[n] );
		}
		if( op == 'Q' )//查询区间最优解 
		{
			cin>>l>>r>>x;
			l--, r--;
			if( l == 0 ) cout<<max( pre[n]^x,tr.query( tr.rt[r],tr.rt[0],pre[n]^x ) )<<"\n";//避免遗忘全选的情况(选择点1)
			else         cout<<tr.query( tr.rt[r],tr.rt[l-1],pre[n]^x )<<"\n";
		}
	}
    QWQ
}

---

2.复杂度

空间复杂度与时间复杂度都是$O(nlogn)$级别的