Автор задачи и разработчик: Владимир Рябчун
Для решения этой задачи удобно рассматривать массив длины $$$2^k$$$, для этого исходный массив можно дополнить до ближайшей степени двойки нулями в конце.
Ответ на запрос суммы будем выполнять так: для каждого бита нужно посчитать, в каком количестве слагаемых этот бит равен единице. Пусть таких слагаемых $$$c_d$$$. Тогда ответом будет $$$\sum_{d = 0}^{15} 2^d \cdot c_d$$$. Опишем вычисление величин $$$c_d$$$.
Будем решать задачу отдельно для каждого бита. Для бита $$$d$$$ весь массив разобьётся на отрезки длины $$$2^d$$$, на которых у индексов в массиве этот бит будет постоянным (так, третий бит равен $$$0$$$ для индексов с $$$0$$$ по $$$7$$$, равен $$$1$$$ для индексов с $$$8$$$ по $$$15$$$, и так далее).
Заметим, что $$$c_d$$$ состоит из количества элементов массива $$$a_i$$$, имеющих $$$1$$$ в $$$d$$$-м бите, стоящих на позиции $$$i$$$, имеющей $$$0$$$ в $$$d$$$-м бите, и наоборот. Если рассматривать только $$$d$$$-й бит, у нас имеется массив из $$$0$$$ и $$$1$$$, в котором некоторые элементы нужно рассматривать инвертированными (если в индексе $$$i$$$ стоит $$$1$$$ в $$$d$$$-м бите), а некоторые — нет (если в индексе стоит $$$0$$$). Воспользуемся свойствами двоичной записи натуральных чисел, а именно:
Тогда построим дерево отрезков на сумму (считать будем количество единиц на отрезке), но не будем опускаться ниже $$$d$$$-го слоя, сделаем вершины, соответствующие отрезкам длины $$$2^d$$$, листьями. А в каждом из этих листьев построим отдельное дерево отрезков, позволяющее быстро выполнять операции изменения (битовые операции для каждого конкретного бита транслируются в присвоение или инверсию).
Запросы к внешнему дереву отрезков посещают $$$\mathcal{O}(1)$$$ листьев, в каждом из которых выполнится запрос за $$$\mathcal{O}(\log{N})$$$ действий, поэтому асимптотика любого запроса для фиксированного бита будет $$$\mathcal{O}(\log{N})$$$.
Итоговая асимптотика будет $$$\mathcal{O}(\log{N} \cdot \log{M})$$$, где $$$M$$$ — максимальное значение элементов в массиве.