Изменения

{{Определение

|definition=

# изменять значение любого элемента в массиве;

# выполнять некоторую ассоциативную, коммутативную, обратимую операцию <tex> G </tex> на отрезке <tex> [i, j] </tex>.

Все <tex>i</tex> мы можем получить следующим образом : <tex>i_{next} = i_{prev} | (i_{prev} + 1) </tex>, Где под | понимают побитовое ИЛИ. Следующим элементом в последовательности будет элемент, у которого первый с конца ноль превратится в единицу. Можно заметить, что если к исходному элементу прибавить единицу, то необходимый ноль обратится в единицу, но при этом все следующие единицы обнулятся. Чтобы обратно их превратить в единицы, применим операцию побитового ИЛИ. Таким образом все нули в конце превратятся в единицы и мы получим нужный элемент. Для того, чтобы понять, что эта последовательность верна, достаточно посмотреть на таблицу.

|-

|-

|}

Для доказательства леммы рассмотрим битовую запись следующих чисел: <tex> k - 2^{h(k)} + 1 \leq i \leq k </tex>

|-

|-

|}

=== Реализация ===