python异或高阶应用-前缀异或法

前言

我们在算法中经常会看到前缀和的解法，能够有效地降低算法复杂度。有一个和前缀和非常类似的算法，前缀异或法。

简介

由于异或具有自反性：即任何数异或自身，结果为0。利用这个特性，我们可用于消除影响。

 a ⊕ a = 0

前缀异或的解释：对于 preXOR[i] 表示为前 i 项数的异或值。
假设我们有数组 arr: [1, 2, 3, 4, 5, 6]
前零项的异或值为: 0 = 0
前一项的异或值为: 1 = 1
前二项的异或值为: 1 ⊕ 2 = 3
前三项的异或值为: 1 ⊕ 2 ⊕ 3 = 0
前四项的异或值为: 1 ⊕ 2 ⊕ 3 ⊕ 4 = 4
前五项的异或值为: 1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 5 = 1
前六项的异或值为: 1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 5 ⊕ 6 = 7

因此它的前缀异或数组为 preXOR: [0, 1, 3, 0, 4, 1, 7];

现在假如我们要求第三项到第六项的前异或值，我们正常的思路应该是

3 ⊕ 4 ⊕ 5 ⊕ 6

但是应用前缀异或的思路，不用这么暴力了。因为

3 ⊕ 4 ⊕ 5 ⊕ 6 = (1 ⊕ 2) ⊕ (1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 5 ⊕ 6) = 3 ⊕ 7

这样就可以在O(1)的时间复杂度内求出结果了。

应用

• 1310.子数组异或查询
• 1442.形成两个异或相等数组的三元组数目