For a given array of integers, we have to calculate `XORed`

sum withing a given range `[L, R]`

, by `XORed`

sum I mean `Σ(Arr[i]^p)`

where `i:[L,R]`

and `p`

is some number. This can be easily done while calculating the `XORed`

sum till every `i-th`

element in array from beginning of the array. Now the problem occures when the `p`

changes very frequently. And recalculating `XORed`

sum till every `i-th`

element does not seems to be an ideal solution in this case. I guess this can be done using `fenwick`

tree or `BIT`

. But I am not able to figure out how to proceed with `fenwick`

tree or `BIT`

. Any help would be appreciated.

It’s the same as using BIT for sum, just replace + with ^ (xor).

Could you provide the problem source? I am not comfortable providing you with an answer otherwise.

2 Likes