Диапазон XORed сумма с использованием дерева 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, ответ - это число элементов в диапазоне со значением этого бита, равным нулю (в противном случае это то же самое, но для элементов с этим битом, равным единице).

Как эффективно подсчитать количество таких элементов? Мы можем построить массив сумм префиксов для каждого бита. Таким образом, мы получаем количество элементов с заданным битом или без него в диапазоне за постоянное время.