мне кажется не нужно массив изменять, слишком медленно это.
например такой алгоритм:
какую-то структуру, которая будет запоминать какие последовательности битов инвертированы, при запросе бита - если вхождение в диапазон инвертов было четное - то бит тот же, если не четное - инверсный
да, я тоже к этому склоняюсь.