首先，异或有一个重要的性质：$a⊕b⊕b=a$ 因为 b 的二进制位一定与自己一样，根据异或的定义，得出 $b⊕b=0$，进而推出这个式子。

有了这个式子，区间异或和就可以像前缀和一样处理了。

我们可以求出每一项的前缀异或和，记作 $q_i​$ ，根据上面那条性质，可以仿照前缀和的形式写出区间 [l,r] 的异或和（记作 $S_{l,r}$​ ）的 O(1) 求法式子：（下标均从 1 开始）$S_{l,r​} =p_r​ ⊕p_{l−1}$ ​ 所以，我们用这个式子来求解每个区间的异或和，可以把每个子段的异或和的和转变为下面式子：（这里 p 0​ 默认取 0 值，因为还需要查询类似 [1,i] 这种区间的值）i=1∑n​ j=0∑i−1​ pi​ ⊕p j​ 但这个做法的复杂度是 O(n 2 )，不够通过本题的数据范围，所以我们还需要在这个基础上继续优化。

在这个式子中，我们可以观察到，对于每一对 i,j 不相等的有序数对 (i,j)，p i​ ,p j​ 都恰好只互相异或了一次。所以，问题又转化为了 n 个数，其中两两异或的求和。

这个时候会发现推式子已经到达尽头了，再怎么推也不会得到新的结论。必须从其他方面考虑问题，比如异或运算的计算原理的方面。可以考虑把每个数按二进制拆分，在每一位上统计该位的贡献。由于最后是两两异或的求和，所以二进制拆分后打乱不会影响结果。

由于异或的运算法则是如果同位数字不同，那么运算结果的这一位为 1。我们知道，只有二进制位为 1 对最终的结果（加和）有贡献，所以我们可以统计二进制结果为 1 的情况。

对于每一个 p i​ ，我们将其按位拆分，并将结果存入计数数组 w i,j​ 中。其中 i 表示第 i 个二进制位，j 表示这一位上为 j（只能为 0 或 1），w i,j 表示在所有数中，第 i 个二进制位上为 j 的有 w i,j​ 个。

由于这些数中必定两两异或，所以可以直接用乘法原理，求出该位最终为 1 的个数，最后乘上该位的权值就可以了。所以最后的答案为：（公式中 i 的范围上界到 20 是因为题目中说 A i​ ≤2 20 ，最多只有 21 个二进制位）i=0∑20​ w i,0​ ×w i,1​ ×2 i

时间复杂度 O(n)，可以通过本题。