algorithm - 使用 BIT 或 Fenwick 树的范围异或求和

Question

对于给定的整数数组，我们必须通过XORed 和来计算给定范围[L, R] 内的XORed 和我的意思是 Σ(Arr[i]^p) 其中 i:[L,R] 和 p 是一些数字。这可以很容易地完成，同时计算 XORed 总和，直到数组中从数组开头开始的每个 i-th 元素。现在问题发生在 p 变化非常频繁的时候。在这种情况下，重新计算 XORed 和直到每个 i-th 元素似乎不是理想的解决方案。我想这可以使用 fenwick tree 或 BIT 来完成。但我不知道如何继续使用 fenwick 树或 BIT。任何帮助，将不胜感激。

Answer 1

我们可以独立解决每个位的问题。

假设我们要计算第 k 位对答案的贡献。如果在p中设置，则答案是该位值为零的范围内元素的数量(否则，它是一样的，但对于该位等于一的元素) .

如何有效地统计此类元素的数量？我们可以为每一位构建一个前缀和数组。这样，我们就可以在恒定时间内获得某个范围内具有或不具有给定位的元素的数量。