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