Изменения

Нам надо научиться быстро изменять частичные суммы в зависимости от того, как изменяются элементы. Рассмотрим как изменять величину <tex>a_{k}</tex> на величину <tex>d</tex>. Тогда нам надо изменить элементы дерева <tex>T_{i}</tex>, для которых верно неравенство <tex>F(i) < k < i</tex>. Все <tex>i</tex> мы можем получить следующим образом : <tex>i_{next} = i_{prev} | (i_{prev} + 1) </tex>, Где под | понимают побитовое ИЛИ. Для того, чтобы понять, что эта последовательность верна, достаточно посмотреть на картинкутаблицу. {| border="1"|<tex>i_{prev}</tex>|<tex>\cdots 011 \cdots 1)</tex>|-|<tex>i_{prev} + 1</tex>|<tex>\cdots 100 \cdots 0)</tex>|-|<tex>i_{next}</tex>|<tex>\cdots 111 \cdots 1)</tex>|}