我把大家的疑惑解答写在中间了hh

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 6e5 + 10, M = 25 * N;
int s[N];
int tr[M][2], max_id[M];
int root[N], idx;

/*
可以递归也可以不递归
感觉递归有点繁琐了，不递归更加清晰也能过掉，并且时间快了将近1/3
*/
void insert(int k, int p, int q)// 非递归
{
    max_id[q] = k;
    for(int i = 23; i >= 0; i --)
    {
        int v = s[k] >> i & 1;
        if(p)tr[q][v ^ 1] = tr[p][v ^ 1];
        tr[q][v] = ++ idx;
        max_id[tr[q][v]] = k;
        q = tr[q][v], p = tr[p][v];
    }
}


void insert(int i, int k, int p, int q) // 递归
{
    if(k < 0)
    {
        max_id[q] = i;
        return ;
    }

    int v = s[i] >> k & 1;
    if(p)tr[q][v ^ 1] = tr[p][v ^ 1];
    tr[q][v] = ++ idx;
    insert(i, k - 1, tr[p][v], tr[q][v]);

    max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]);
}

int query(int p, int l, int c)
{
    for(int i = 23; i >= 0; i --)
    {
        int v = c >> i & 1;
        if(max_id[tr[p][v ^ 1]] >= l)p = tr[p][v ^ 1];
        else p = tr[p][v];
    }

    return c ^ s[max_id[p]];
}
/*
已经推出公式  求 s[p] ^ s[n] ^ x 最大值; l - 1 <= p <= r - 1; 即0 <= p <= n - 1;
所以s[0] 也为合法数据 第一个根即为root[0] = ++ idx;为什么不写成 idx ++ 
因为如果是idx ++那么第一个数字为 0, 它就代表的是下面的x，把max_id[0]修改了，与下面的max_id[0] 冲突了。
max_id[x] = y; x为每个tr[n][m] 的值
 y为每一个 x的最大标号（就是这个二进制的01属于第几个数的下标(root[i]的i)）
为什么要把 max_id[0] = -1;因为x 如果为零代表这个点不存在，而且y的最小值可以取到0
所以取小于0的任意整数都行。
*/

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    s[0] = 0;
    max_id[0] = -1;
    root[0] = ++ idx;

    insert(0, 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, root[i - 1], root[i]);
    }

    while(m --)
    {
        char op[2];
        scanf("%s", op);
        if(*op == 'A')
        {
            int x;
            scanf("%d", &x);
            n ++;
            root[n] = ++ idx;
            s[n] = s[n - 1] ^ x;
            insert(n, root[n - 1], root[n]);
        }
        else
        {
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            printf("%d\n", query(root[r - 1], l - 1, s[n] ^ x));
        }
    }
    return 0;
}