字典树
查询/插入O(|s|)

int son[N][26],cnt[N],idx;//son存储树中每个结点的子节点,cnt存储以该节点为结尾的单词数量

void insert(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int q=str[i]-'a';
        if(!son[p][q])
        {
            son[p][q]=++idx;
        }
        p=son[p][q];
    }
    cnt[p]++;
}

int query(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int q=str[i]-'a';
        if(!son[p][q])
        {
            return 0;
        }
        p=son[p][q];
    }
    return cnt[p];
}

可持久化字典树
查询/插入O(|s|)
例题
给定一个非负整数序列 a，初始长度为 N。
有 M 个操作，有以下两种操作类型：
1.A x：添加操作，表示在序列末尾添加一个数 x，序列的长度 N 增大 1。
2.Q l r x：询问操作，你需要找到一个位置 p，满足 l≤p≤r，使得：a[p] xor a[p+1] xor … xor a[N] xor x 最大，输出这个最大值。

int s[N];                //前缀和
int tr[M][2], max_id[M]; //M为树深度+1
int root[N], idx;        //[1, i]区间的字典树的根节点

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 root, int C, int L)
{
    int p = root;
    for (int i = 23; ~i; 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]];
}

int main()
{
    std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
    cin >> n >> m;
    max_id[0] = -1;            //初始化
    root[0] = ++idx;           //初始化
    insert(0, 23, 0, root[0]); //初始化
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        s[i] = s[i - 1] ^ x;
        root[i] = ++idx;
        insert(i, 23, root[i - 1], root[i]);
    }
    while (m--)
    {
        char op;
        cin >> op;
        if (op == 'A')
        {
            n++;
            int x;
            cin >> x;
            s[n] = s[n - 1] ^ x;
            root[n] = ++idx;
            insert(n, 23, root[n - 1], root[n]);
        }
        else
        {
            int l, r, x;
            cin >> l >> r >> x;
            cout << query(root[r - 1], s[n] ^ x, l - 1) << endl;
        }
    }
    return 0;
}