对于给定的整数数组，我们必须计算给定范围内的XORed和[L, R]，我所说的XORed和我的意思是Σ(Arr[i]^p)其中i:[L,R]和p是某个数字。这可以很容易地完成，同时计算数组中每个i-th元素从数组开头开始的XORed和。现在，当p更改非常频繁时，就会出现问题。在这种情况下，重新计算XORed总和直到每个i-th元素似乎不是一个理想的解决方案。我想这可以使用fenwick tree或BIT来完成。但是我无法弄清楚如何处理fenwick树或BIT.任何帮助将不胜感激。
我们可以独立解决每个位的问题。
假设我们要计算第 k 位对答案的贡献。如果它设置为 p ，答案是该位值等于零的范围内元素的数量(否则，这是一回事，但对于该位等于 1 的元素(。
如何有效地计算此类元素的数量？我们可以为每个位构建一个前缀总和数组。这样，我们就可以在恒定时间内获得在一定范围内有或没有给定位的元素的数量。