Persistent Trie

Introduction

A persistent Trie is built similarly to a persistent segment tree: each version modifies only the nodes that are added or whose values change, while retaining every unchanged node. Edges are connected to the previous version, so traversing the root of every version yields a complete Trie containing all the information of that version.

Most persistent Trie problems use a 01-Trie.

Process

The requested value may look troublesome. Using the usual treatment of prefix XORs, let $s_x=\bigoplus_{i=1}^x a_i$. The expression becomes $s_{p-1}\oplus s_n\oplus k$. Since $s_n \oplus k$ is fixed during a query, the query becomes finding the maximum XOR with the fixed value ($s_n\oplus k$) among the interval $[l-1,r-1]$.

Following the idea of a persistent segment tree, consider querying the entire interval each time. We only need to build one Trie for the interval, insert every value in the interval into it, and, during a query, move toward the branch whose current bit differs from the corresponding bit of the query value whenever possible.

To obtain the Trie for a query interval, use prefix sums and the idea of differences: subtracting two prefix Tries (two historical versions obtained by adding values in order) gives the Trie of that interval. Dynamic node allocation avoids creating nodes that are never needed and reduces memory usage.

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
constexpr int MAXN = 600010;
int n, q, a[MAXN], s[MAXN], l, r, x;
char op;

struct Trie {
  int cnt, rt[MAXN], ch[MAXN * 33][2], val[MAXN * 33];

  void insert(int o, int lst, int v) {
    for (int i = 28; i >= 0; i--) {
      val[o] = val[lst] + 1;  // Update based on the previous version
      if ((v & (1 << i)) == 0) {
        if (!ch[o][0]) ch[o][0] = ++cnt;
        ch[o][1] = ch[lst][1];
        o = ch[o][0];
        lst = ch[lst][0];
      } else {
        if (!ch[o][1]) ch[o][1] = ++cnt;
        ch[o][0] = ch[lst][0];
        o = ch[o][1];
        lst = ch[lst][1];
      }
    }
    val[o] = val[lst] + 1;
  }

  int query(int o1, int o2, int v) {
    int ret = 0;
    for (int i = 28; i >= 0; i--) {
      int t = ((v & (1 << i)) ? 1 : 0);
      if (val[ch[o1][!t]] - val[ch[o2][!t]])
        ret += (1 << i), o1 = ch[o1][!t],
                         o2 = ch[o2][!t];  // Move toward the different branch whenever possible
      else
        o1 = ch[o1][t], o2 = ch[o2][t];
    }
    return ret;
  }
} st;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) cin >> a[i], s[i] = s[i - 1] ^ a[i];
  for (int i = 1; i <= n; i++)
    st.rt[i] = ++st.cnt, st.insert(st.rt[i], st.rt[i - 1], s[i]);
  while (q--) {
    cin >> op;
    if (op == 'A') {
      n++;
      cin >> a[n];
      s[n] = s[n - 1] ^ a[n];
      st.rt[n] = ++st.cnt;
      st.insert(st.rt[n], st.rt[n - 1], s[n]);
    }
    if (op == 'Q') {
      cin >> l >> r >> x;
      l--;
      r--;
      if (l == 0)
        cout << max(s[n] ^ x, st.query(st.rt[r], st.rt[0], s[n] ^ x)) << '\n';
      else
        cout << st.query(st.rt[r], st.rt[l - 1], s[n] ^ x) << '\n';
    }
  }
  return 0;
}