查找最大/最小连续XOR值

Question

我有以下问题:给定一个整数数组(最大大小50000)我必须找到最大的X,这样,

X = a[p] ^ a[p+1] ^ ... ... ^ a[q] for some p,q (p<=q)

另外,我必须找到X的最小值.

我试过这个过程,

sum[i] = a[0] ^ a[1] ^ ... ... ^ a[i] for some i .

我在O(n)和中预先计算了它

那么某些人的X值p,q(p<=q)是,

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)

但是这个过程是O(n ^ 2).

如果没有O(n ^ 2)算法,我怎么能这样做呢？