algorithm - 所有子数组的异或之和

Question

在执行the approach described below我不明白这两个循环是如何考虑测试用例的哪一部分的，我的意思是这两个循环是如何覆盖所有可能性的。请帮忙

问题链接xor subbarray

// loop to calculate initial 
// value of c_odd 
for (int j = 0; j < n; j++) { 
    if ((arr[j] & (1 << i)) > 0) 
        odd = (!odd); 
    if (odd) 
        c_odd++; 
}

还有这个

for (int j = 0; j < n; j++) { 
    sum += (mul * c_odd); 

    if ((arr[j] & (1 << i)) > 0) 
        c_odd = (n - j - c_odd); 
} 

极客对极客的描述:

最佳解决方案:为了更好地理解，我们假设一个元素的任何位由变量“i”表示，变量“sum”用于存储最终总和。

这里的想法是，我们将尝试找出设置了第 i 个位的 XOR 值的数量。让我们假设，有“Si”个子数组的第 i 个位被设置。对于第i位，sum可以更新为sum += (2i * S) 。

那么，问题是如何实现上面的想法呢？

我们会将任务分解为多个步骤。在每一步，我们都将尝试找出设置了第 i 个位的 XOR 值的数量。 现在，我们将把每个步骤分解为子步骤。在每个子步骤中，我们将尝试找到从索引“j”(其中 j 在 0 到 n – 1 之间变化)开始的子数组的数量，其中第 i 个位设置在异或值中。因为，要设置第 i 个位，子数组的奇数个元素应该设置第 i 个位。 对于所有位，在变量 c_odd 中，我们将存储从 j = 0 开始的子数组数量的计数，其中第 i 位设置为奇数个元素。然后，我们将遍历数组的所有元素，在需要时更新 c_odd 的值。如果我们到达第 i 个位设置的元素“j”，我们会将 c_odd 更新为 c_odd = (n – j – c_odd)。这是因为，由于我们遇到了一个设置位，第 i 个位设置为偶数个元素的子数组数将切换为第 i 个位设置为奇数个元素的子数组数。

Answer 1

这是一个很好的例子，说明如果对程序进行更仔细的描述性表述，本可以使其更容易理解，也更正确。

我们正在分别查看每一位。

让我们考虑第一个循环:它正在计算从索引 0 开始的子数组中当前位集的奇数个数。 (看起来很清楚这个计数是如何实现的，但请随意询问。)

现在，在第二个循环中，我们可以使用此信息(并更新它)作为所有从我们当前开始(而不是从索引 0 开始)并在任何地方结束的子数组稍后。假设初始计数为 2，并且 n = 10，当前位设置在数组中索引 4 和 6 处的元素上。

现在，在每次迭代中，我们都在标记我们正在计数的子数组的左边界/下边界。我们已经知道有 2 个子数组从索引 0 开始并“稍后某处”结束。但是由于在索引 4 之前没有设置此位的实例，我们可以说此计数对于下界 1、2、3 和 4 也是正确的:有 2 个子数组计数从这些索引开始并“稍后某处结束”。 "

当我们到达索引 4 时，魔法就发生了，我们需要更新我们的计数。如果到现在为止，有 2 个子数组的位 i 设置为奇数，从这里开始到“稍后”结束，则有 10 - here - 2 子数组有 even 位 i 的计数从这里开始并“稍后”结束 (A[4..4], A[4..5], ... A[4.. 9] 但不包括 A[4..4] 和 A[4..5]，它们只有一个 i 位计数设置)。

当我们到达索引 4 时，我们重新计算 子数组的计数，其中 i 的奇数位设置从此处开始并在“稍后某处”结束 作为 n - j - current_odd_count 因为我们传递了一个设置位的实例，所以我们可以将之前计数为偶数的所有子数组翻转到我们的新度量。