如何优化异或和满足(X+1)=(X^1)的子数组计数O(n³)算法

1 简化判断条件 #

我们先拆解等式(X + 1) == (X ^ 1)的含义：

• 对任意整数来说，X ^ 1的作用是翻转X二进制的最低位
• 当X的最低位为0时：X + 1就是把最低位从0改成1，和X ^ 1的结果完全一致
• 当X的最低位为1时：X + 1会触发进位（最低位变0，次低位加1），而X ^1只会把最低位变0，不会修改更高位，二者结果必然不等

结论：满足条件的X等价于二进制最低位为0，也就是X是偶数。我们的问题直接转化为：统计数组中所有异或和为偶数的子数组数量。

2 前缀异或优化统计逻辑 #

子数组的异或和可以通过前缀异或规则快速计算，不需要枚举所有子数组：

• 定义pre_xor[0] = 0，pre_xor[k]为数组前k个元素的异或和（也就是arr[0] ^ arr[1] ^ ... ^ arr[k-1]）
• 任意子数组arr[i...j]的异或和 = pre_xor[j+1] ^ pre_xor[i]

我们需要这个异或和的最低位为0，根据异或运算规则，两个数异或结果最低位为0等价于两个数的最低位相同。因此我们只需要统计前缀异或数组中：

• 最低位为0的元素个数cnt0
• 最低位为1的元素个数cnt1
  从相同最低位的元素中任选两个，就能对应一个符合条件的子数组，总数量为：
  总数量 = cnt0 * (cnt0 - 1) / 2 + cnt1 * (cnt1 - 1) / 2

3 优化后的代码实现 #

优化后时间复杂度为O(n)，空间复杂度为O(1)，可以支持百万级以上的数组规模计算，同时修正了你原代码中变量名错误的问题：

def count_valid_subarrays(arr):
    cnt0 = 1  # pre_xor[0]的最低位是0，初始计数
    cnt1 = 0
    current_pre_xor = 0
    for num in arr:
        current_pre_xor ^= num
        # 仅取当前前缀异或的最低位判断即可
        last_bit = current_pre_xor & 1
        if last_bit == 0:
            cnt0 += 1
        else:
            cnt1 += 1
    # 计算组合数得到总数量
    return cnt0 * (cnt0 - 1) // 2 + cnt1 * (cnt1 - 1) // 2

arr = [3, 5, 2, 4, 6]
print(count_valid_subarrays(arr))

内容的提问来源于stack exchange，提问作者Joshy Joy