PROBLEM LINK:DIFFICULTY:MEDIUM PREREQUISITE:PROBLEM:Given an array of positive integers and a number K, find the number of subarrays whose XOR is less than K. XOR of subarray is defined as XOR of all elements in it. Each element is less than 10^6. Number of elements less than 10^5. EXPLANATION:Normal O(N^2) solution would time out. Let f(L,R) = XOR of subarray a[L..R], then f(L,R) = f(1,R) XOR f(1,L1). For each index i=1 to N, we can count how many subarrays ending at ith position satisfy the given condition. Now, suppose, that we have a data structure that allows us to perform this two operations: insert some integer into this structure and for given two integers X and K finds the number of elements already in structure whose XOR with X is less than K. Then we can solve the task like this:
Now, about the data structure. It can be implemented as trie (prefix tree), if we consider integers as binary strings of length logA = 20. Then insertion can be done in O(logA) time. But we also need to keep at each node the number of leaves we will encounter if we go to left side from that node and similarly for right. How do we do query(x,k)?
SIMILAR PROBLEM:
This question is marked "community wiki".
asked 07 Feb '14, 03:04

@sp1rs, level'th bit means the level'th most significant bit.
a) we insert 0 in the trie, then we have x=f(1,1) and count how many numbers already present in the trie which when taken xor with x return a number less than K. and then we insert x in the trie. b) then we insert x=f(1,2) count how many numbers already present in the trie which when taken xor with x return a number less than K. and then we insert x in the trie.
What does the point c) help us? it tells us how many of subarrays ( [1,3],[2,3] ) satisfy the given condition. Similarily b) tells us how many of subarrays ( [1,2]) satisfy the condition. answered 11 Feb '14, 09:09

I have two questions  1.) What does it qualitatively mean to go left or right from a node in the trie? It's unclear. 2.) Can you please explain atleast with an example how you compute f(L, R) from the trie? answered 10 Feb '14, 16:15

@darkshadows How the tree is working, do you have any tutorial about the details of the trie used in the problem, I found one of your link broken.:( answered 22 Aug '15, 17:00
