可持久化01Trie

例题：

解释：

首先这里要求连续异或，所以存储前缀异或和数组。首先的话，我们只考虑前r个版本的Trie，所以以root[r]为根节点的Trie就是1到r位置数。但是，还有一个l左端点，所以我们对于每一个节点来说，额外存储一下max_id，表示的就是以当前节点为子树的最大的i。那这个有什么用呢？

这里我们都是动态开点，也就是假设当前我们的数是1，所以我们要向下遍历找到一个0，由于我们是有限制条件的，所以对于每一个节点，加入他的0的这个儿子的max_id大于我们的限制条件，也就是这个子树里面存在一个s{i]，它的下标大于或等于我们的限制条件，所以我们就可以往0这个方向走。

动态开点思路：对于每一个s[i]我们都去开这个数的01串，也就是一个链子，刚开始是我们的根节点，也就是我们的版本（第几版）。假设当前数是（二进制：101010），我们先开了一个根节点（第几版），于是我们继续开一个1这个节点，如果它的上一个版本中的根节点有0这个儿子，那么我们就让上一个版本的0这个儿子指向当前的根节点（也就是直接拷贝）。然后继续开点，开0这个节点，只要遇到不同的，就直接拷贝，如果上一个版本存在当前的链子的前半部分，我们也是必须开的，只有不同的我们才会去复制。

那么这样执行下来，就会存下每一个版本的Trie，也就是我们的可持久化Trie，那么这到底有什么用呢？下面就用上面这个例题来介绍它的用处！

由于当前是由区间限制的，不像一组数据中找两个数他们的异或值最大，没有区间限制的话，用我们的Trie就可以了。首先如果我们只考虑1到r这个条件的话，那么直接从第r个版本的Trie开始找一个数就可以了。然后在考虑数必须大于等于l这个条件，由于我们存储了max_id，也就是下一个节点的max_id，只要大于等于限制条件，就可以遍历这个节点。假设max_id是3，限制条件是2，表示的是这个字数有一个数它的下标是3，所以就可以遍历这个节点，反之，就不可以遍历，因为每一个节点它的下标大于限制条件，都是l前面的数，所以就不能遍历。

所以，直接上代码：

#include 
#include 
#include 
 
using namespace std;
 
const int N = 600010,M = N*25;
int n, m;
int tr[M][2], idx;
int root[N];
int s[N];
int max_id[M];
 
void insert(int i, int k, int p, int q)
{
	if (k < 0)
	{
		max_id[q] = i;
		return ;
	}
	int u = s[i] >> k & 1;
	if (p)tr[q][u^1] = tr[p][u^1];
	tr[q][u] = ++idx;
	insert(i, k - 1, tr[p][u], tr[q][u]);
	max_id[q] = max(max_id[tr[q][0]],max_id[tr[q][1]]);
}
 
int query(int root, int limit, int c)
{
	int p = root;
	for (int i = 23; i >= 0; i--)
	{
		int u = c >> i & 1;
		if (max_id[tr[p][!u]] >= limit && tr[p][!u])p = tr[p][!u];
		else p = tr[p][u];
	}
	return c ^ s[max_id[p]];
}
 
int main()
{
	cin >> n >> m;
 
	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;
	while (m--)
	{
		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], l - 1, s[n] ^ x));
		}
	}
 
}