这道题需要处理多次区间异或查询。类似前缀和的思想,但异或运算有其特殊性:异或的逆运算是自身(即 a⊕a=0)。
解题思路:
1. 预处理前缀异或数组 prefix[i] 表示前 i 个数的异或值
2. 对于询问 [l, r],答案为 prefix[r] ⊕ prefix[l-1],因为区间异或 = 前缀异或的异或(自逆性质)
c++代码:
关键点:
1. 异或运算满足:a⊕a=0,a⊕0=a,因此区间异或 = prefix[r]⊕prefix[l-1]
2. 使用 int 即可,因为 a_i≤10^9,异或结果不会超过 2^31-1
3. prefix[0]=0 便于处理 l=1 的情况
4. 时间复杂度 O(n+q),空间复杂度 O(n)
求赞