Изменения

Нам надо научиться быстро изменять частичные суммы в зависимости от того, как изменяются элементы. Рассмотрим как изменять величину <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>, Где под | понимают побитовое ИЛИ. Для того, чтобы понять, что эта последовательность верна, достаточно посмотреть на картинку.