I have following problem : given an integer array (maximum size 50000) i have to find the maximum X such that,
X = a[p] ^ a[p+1] ^ ... ... ^ a[q] for some p,q (p<=q)
Also i have to find the minimum value of X.
I have tried this process ,
sum[i] = a[0] ^ a[1] ^ ... ... ^ a[i] for some i .
i pre-calculated it in O(n) and
then the value of X for some p,q(p<=q) is ,
X = sum[q] ^ sum[p-1]
MaxAns = Max of X for every pair of p,q (p<=q)
MinAns = Min of X for every pair of p,q (p<=q)
But this process is O(n^2).
How can i do that without O(n^2) algorithm , something more efficient ?