可以发现，如果裸着建，不仅要消耗很多的时间，更是要消耗很多的空间。考虑以i为根的字典树和以（i-1）为跟的字典树的异同。 可以发现，在当前以i为根的字典树上减去a[i]，就是（i-1）的字典树了。所以，我们可以将除了a[i]之外的结点都连到（i-1）的树上。 当然，i-1的树也是从i-2的树上引用过来的。 这样之后，会出现一个问题。比如，a[i-1]的值与a[i]的值相同，那么我们到底要不要跟新呢？还是直接将root[i]全部指向root[i-1]？ 还是之前的做法。除了a[i]的值，其他的值全部引用前面的，将a[i]跟新root[i]。 这样做完之后，可以发现，如果不加以区分，root[i]和root[i-1]的树一模一样，直接做差之后不就没有了。可是事实上，在【i，i】这给区间内，有一个数的值为a[i]。 所以我们用一个sum数组加以区别，也就是说，如果当前的root的结点是引用前面的，那么sum不变。否则（就是a[i]跟新的部分），sum[root[i]]=sum[[root[i-1]]+1。a[i]这个数的每个位置都是之前的+1。。
void insert(int x , int last,int &now) { now = ++ cnt ; int p = now ; for(int i = 30 ;i >= 0 ;i --) { int id = (x >> i) & 1 ; num[p] = num[last] + 1 ; son[p][id] = ++ cnt ; son[p][id ^ 1] = son[last][id ^ 1] ; p = son[p][id] , last = son[last][id] ; } num[p] = num[last] + 1; }这样我们在判断区间的时候，就可以拿sum[root[r]]-sum[root[l-1]]。如果大于0，说明在root[l-1]之后，被跟新过，所以可以取。如果sum值相同，代表root[r]中的那部分是直接引用的root[l-1]中的那部分，这个区间内没有跟新过，所以无法取 查询的时候贪心的走就行了，
int ask(int x , int l , int r ) { int ans = 0 ; for(int i = 30 ;i >= 0 ;i --) { int id = (x >> i) & 1 ; if(num[son[r][id ^ 1] ]- num[son[l][id ^ 1]]> 0) ans += 1 << i , l = son[l][id ^ 1] , r = son[r][id ^ 1] ; else l = son[l][id] , r = son[r][id] ; } return ans ; }最大异或和
#include <bits/stdc++.h> using namespace std ; #pragma GCC optimize(3 , "Ofast" , "inline") const int N = 3e5 + 10 ; int num[N << 6] , son[N << 6][2] ; int n , m , a[N << 6] , rt[N << 6]; int cnt ; void insert(int x , int last,int &now) { now = ++ cnt ; int p = now ; for(int i = 30 ;i >= 0 ;i --) { int id = (x >> i) & 1 ; num[p] = num[last] + 1 ; son[p][id] = ++ cnt ; son[p][id ^ 1] = son[last][id ^ 1] ; p = son[p][id] , last = son[last][id] ; } num[p] = num[last] + 1; } int ask(int x , int l , int r ) { int ans = 0 ; for(int i = 30 ;i >= 0 ;i --) { int id = (x >> i) & 1 ; if(num[son[r][id ^ 1] ]- num[son[l][id ^ 1]]> 0) ans += 1 << i , l = son[l][id ^ 1] , r = son[r][id ^ 1] ; else l = son[l][id] , r = son[r][id] ; } return ans ; } int main() { int n , m , x , l , r ; scanf("%d%d" ,&n , &m) ; for(int i = 1; i <= n ;i ++) { scanf("%d" , &x) ; a[i] = a[i - 1] ^ x ; insert(a[i] , rt[i - 1] , rt[i]) ; } char str[5] ; for(int i = 1 ;i <= m ;i ++) { scanf("%s" , str) ; if(str[0] == 'A') { scanf("%d" , &x) ; a[n + 1] = a[n] ^ x ; n ++ ; insert(a[n] , rt[n - 1] , rt[n]) ; } else { scanf("%d%d%d" , &l , &r , &x) ; l -- , r -- ; if(l == 0) printf("%d\n" , max(ask(x ^ a[n] , 0, rt[r]) , x ^ a[n])) ; else printf("%d\n" , ask(x ^ a[n] , rt[l - 1] , rt[r])) ; } } return 0 ; }