256. 最大异或和 - AcWing题库
核心代码是：
if(p)tr[q][t ^ 1] = tr[p][t ^ 1];
if(!tr[q][t])tr[q][t] = ++ idx;
p = tr[p][t], q = tr[q][t];将当前版本与上一版本比较，除当前修改外，其余直接继承上一版本
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
typedef long long ll;const int N = 600010, M = N * 25;int n, m;
int s[N];
int tr[M][2], max_id[M];
int root[M], idx;void insert(int i, int p, int q)
{max_id[q] = i;for(int bt = 24; bt >= 0; bt --){int t = s[i] >> bt & 1;if(p)tr[q][t ^ 1] = tr[p][t ^ 1];if(!tr[q][t])tr[q][t] = ++ idx;p = tr[p][t], q = tr[q][t];max_id[q] = i;}
}int query(int l, int r, int x)
{int p = root[r], ans = 0;for(int bt = 24; bt >= 0; bt --){int t = x >> bt & 1;if(tr[p][t ^ 1] && max_id[tr[p][t ^ 1]] >= l){p = tr[p][t ^ 1];ans += (1 << bt);}else p = tr[p][t];}return s[max_id[p]] ^ x;
}int main()
{IOScin >> n >> m;for(int i = 1; i <= n; i ++){cin >> s[i];s[i] ^= s[i - 1];}root[0] = ++ idx;insert(0, 0, root[0]);//先初始化root[0] for(int i = 1; i <= n; i ++){root[i] = ++ idx; insert(i, root[i - 1], root[i]);}while(m --){char op;cin >> op;if(op == 'A'){int x;cin >> x;s[++ n] = x;s[n] ^= s[n - 1];root[n] = ++ idx;insert(n, root[n - 1], root[n]); }else{int l, r, x;cin >> l >> r >> x;x ^= s[n];cout << query(l - 1, r - 1, x) << endl;}}return 0;
}
