HackerEarth: Xor in Sequence (TRIE)

HackerEarth: Xor in Sequence (TRIE)
///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;
///==========CONSTANTS=============///
///  Digit     0123456789012345678 ///
#define MX     100005
#define inf    1000000010
#define MD     1000000000LL
#define eps    1e-9
///===============================///
 
struct data {
    int cnt,nxt[2];
    data() {
        cnt=nxt[0]=nxt[1]=0;
    }
};
data T[MX*22];
int nw;
void Ins(int x) {
    int p=0;
    T[p].cnt++;
    for(int i=30; i>=0; i--) {
        bool k=(x&(1<<i));
        if(T[p].nxt[k]==0) {
            T[p].nxt[k]=++nw;
            T[nw]=data();
        }
        p=T[p].nxt[k];
        T[p].cnt++;
    }
}
 
ll Qry(int n,int k) {
    int p=0;
    ll sm=0;
    for(int i=30; i>=0; i--) {
        bool x=(n&(1<<i));
        bool y=(k&(1<<i));
        if(!y) p=T[p].nxt[x];
        else {
            int nx=T[p].nxt[x];
            if(nx)sm+=T[ nx ].cnt;
            p=T[p].nxt[!x];
        }
        if(!p)break;
    }
    return sm;
}
 
int n,ar[MX+2];
ll Solve(int k) {
    ///How many subarray whose xorsum is less than k;
    CLR(T);
    nw=0;
    T[0]=data();
    int Cumxr=0;
    Ins(0);
    ll sm=0;
    for(int i=1; i<=n; i++) {
        Cumxr^=ar[i];
        sm+=Qry(Cumxr,k);
        if(i!=n)Ins(Cumxr);
    }
    return sm;
}
int main() {
    int tc,cs=1,i,j,k,q;
    S(tc);
    while(tc--) {
        S(n);
        fr(i,1,n)S(ar[i]);
        S(q);
        while(q--) {
            int l,r;
            S2(l,r);
            ll ans=Solve(r+1)-Solve(l);
            printf("%lld\n",ans);
        }
    }
    return 0;
}