### SubXor

Given below c code for subxor spoj

Here I am posting iterative and recursive method to implement Tries.But if you want to understand the problem then follow recursive method.

Here question is based on concept of xor and I have implemented it through Trie .

Here question is based on concept of xor and I have implemented it through Trie .

Basic idea is :-

xor(i,j) means XOR of elements from indexed i to j of an Array

**;**

*XOR(i,j) = XOR(1,i-1)^XOR(1,j)*
This can be proved as

*A^A = 0 & A^0 = A;*
Hence if we XOR the total XOR from 1 to j with total XOR from 1 to i-1 ,it will nullify the effect of XOR(1,i-1) in XOR(1,j) and the remaining XOR will be XOR(i,j);

If you want to study about Tries then CLICK HERE

If you still have problem you can ask me @ raj.nishant360@gmail.com

**Iterative Method to implement add and query function**

#include <bits/stdc++.h> using namespace std; class Node { public: int lCount,rCount; Node *lChild,*rChild; Node() { lCount=rCount=0; lChild=rChild=NULL; } }; void addBit(Node *root,int n) { for(int i=20;i>=0;i--) { int x= (n>>i) & 1; if(x) { root->rCount++; if(root->rChild == NULL) root->rChild = new Node(); root = root->rChild; } else { root->lCount++; if(root->lChild == NULL) root->lChild = new Node(); root = root->lChild; } } } int query(Node *root,int n,int k) { if(root == NULL) return 0; int res = 0; for(int i=20;i>=0;i--) { bool ch1=(k>>i) & 1; bool ch2=(n>>i) & 1; if(ch1) { if(ch2){ res+=root->rCount; if(root->lChild == NULL) return res; root = root->lChild; } else{ res+=root->lCount; if(root->rChild == NULL) return res; root = root->rChild; } } else { if(ch2){ if(root->rChild == NULL) return res; root= root->rChild; } else{ if(root->lChild == NULL) return res; root= root->lChild; } } } return res; } int main() { int t; scanf("%d",&t); while(t--) { int n,k; scanf("%d%d",&n,&k); int temp,temp1,temp2=0; Node *root = new Node(); addBit(root,0); long long total =0; for(int i=0;i<n;i++) { scanf("%d",&temp); temp1= temp2^temp; total+=(long long)query(root,temp1,k); addBit(root , temp1); temp2 = temp1; } printf("%lld\n",total); } return 0; }