Xor sum

字典树需要开的空间等于节点数，而不是需要插入的数的数量，搞错经常会wa、TLE

前言：
因为区间异或和不具有单调性，所以很难找到高效的算法去找到一个区间满足区间异或和不小于 且长度最短。区间问题的一个老套路是通过前缀和转化为两个点的问题，而且位运算有点难度的题都会涉及二进制，因为后面需要用到搜索，可以联想到字典树。

思路：

原数组转化为前缀和
我们可以枚举区间右端点，然后找到最近的一个下标满足，那么这个合法区间就是
我们可以按的二进制位去找下标：
假设的第位是，的第位是，在字典树中当前遍历到的节点是，字典树下一个需要访问的值是

如果，那么，如果此时，也就是说这个二进制位可以凑出，如果沿着节点继续搜，那么不管怎么搜都凑得到不小于的数
如果，那么
如果，也就是说不管取哪一个(第位已经确定)，这个二进制位都不能凑出，就凑不到不小于的数，就没必要接着搜了

搜索完后把插入到字典树，同时把遍历的点标记，标记的值为，表示最近一次遍历这个节点的数的下标

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7,maxm=3e6+10;
int f[maxn],top,n,k,pw[35];
int tir[maxm][2],pos[maxm];
bool s[35];
inline void add(int p) {
    int root=0;
    for(int i=30,id;i>=0;i--) {
        id=(f[p]&pw[i])!=0;
        if(tir[root][id]==0) {
            tir[root][id]=++top;
            tir[top][0]=tir[top][1]=0;
        }
        root=tir[root][id];
        pos[root]=p;
    }
}
inline int find(int p) {
    int root=0,res=-1;
    for(int i=30,id;i>=0;i--){
        id=(f[p]&pw[i])!=0;
        if(s[i]==0) {
            if(tir[root][id^1]) res=max(res,pos[tir[root][id^1]]);
        }
        else id^=1;
        if(tir[root][id]==0) return res;
        root=tir[root][id];
    }
    return max(res,pos[root]);
}
int main() {
    pw[0]=1;
    for(int i=1;i<=30;++i) pw[i]=pw[i-1]<<1;
    int T;
    scanf("%d",&T);
    while(T--) {
        int have=0;
        top=0;
        scanf("%d%d",&n,&k);
        for(int i=0;i<=30;++i) s[i]=(k&pw[i])!=0;
        for(int i=1;i<=n;++i) {
            scanf("%d",&f[i]);
            if(f[i]>=k&&!have) have=i;
            f[i]=f[i-1]^f[i];
        }
        if(have) {
            cout<<have<<' '<<have<<'\n';
            continue;
        }
        int l=-1,r=maxn,tmp;
        tir[0][0]=tir[0][1]=0; pos[0]=-1;
        add(0);
        for(int i=1;i<=n;++i) {
            tmp=find(i);
            if(~tmp&&(i-tmp)<(r-l)) 
                r=i,l=tmp;
            add(i);
        }
        if(~l) printf("%d %d\n",l+1,r);
        else printf("-1\n");
    }
    return 0;
}