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

Question

对于给定的整数数组，我们必须XORed在给定的范围内计算总和[L, R]，XORed总和是指Σ(Arr[i]^p)在哪里i:[L,R]和p是某个数字。这可以在计算从数组开头到数组中XORed每个元素的总和时轻松完成。i-th现在，当p更改非常频繁时，就会出现问题。在这种情况下，重新计算XORed总和直到每个i-th元素似乎都不是理想的解决方案。我想这可以使用fenwick treeor来完成BIT。但我无法弄清楚如何处理fenwicktree 或BIT. 任何帮助，将不胜感激。

Answer 1

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

假设我们要计算k第 - 位对答案的贡献。如果设置为p，则答案是该位的值等于 0 的范围内的元素数（否则，除了该位等于 1 的元素之外，它是相同的）。

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