Изменения

Нам надо научиться быстро изменять частичные суммы в зависимости от того, как изменяются элементы. Рассмотрим как изменять величину <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>, Где под | понимают побитовое ИЛИ. Следующим элементом в последовательности будет элемент, у которого первый с конца ноль превратится в единицу. Можно заметить, что если к исходному элементу прибавить единицу, то необходимый ноль обратится в единицу, но при этом все следующие единицы обнулятся. Чтобы обратно их превратить в единицы, применим операцию побитового ИЛИ. Таким образом все нули в конце превратятся в единицы и мы получим нужный элемент. Таким образом, мы переберем все нужные i, последовательно превратив все 0 в 1. При этом нужные единицы на конце не меняются, а значит возьмем только нужные числа. Для того, чтобы понять, что эта последовательность верна, достаточно посмотреть на таблицу.