Изменения

|proof=Из доказанной выше леммы следует, что первый элемент последовательности само <tex> k </tex>. Для него выполняется равенство, так как <tex> F(i) \leqslant i </tex>. По формуле <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex> мы заменим первый ноль на единицу. Неравенство при этом сохранится, так как <tex>F(i)</tex> осталось прежним или уменьшилось, а <tex> i </tex> увеличилось. <tex> F(i) </tex> не может увеличится, так как функция <tex> F </tex> заменяет последние подряд идущие единицы числа <tex> i </tex> на нули, а по формуле <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex> у нового значения <tex> i </tex> увеличивается количество единиц в конце, что не может привести к увеличению <tex> F(i) </tex>. Можем заметитьПокажем, что если количество единиц почему не стоит рассматривать значения <tex> i </tex>, отличные от тех, которые мы получили по формуле. Рассмотрим такое число <tex> j </tex>, которое больше <tex>k</tex>. Пусть <tex>F(j) \leqslant k </tex>. Уберём у <tex>j</tex> все подряд идущие единицы в конце двоичной записи, столько же цифр уберём в конце не будет совпадать с числа <tex> k </tex>, то формула . Обозначим их как <tex>i_j_{next0} = i_</tex> и <tex>k_{prev0} </tex>. Чтобы выполнялось условие <tex>F(j) \mid (i_leqslant k </tex>, должно выполняться неравенство <tex>j_{0} \leqslant k_{0}</tex>. Но если <tex>j_{0} < k_{prev0} + 1) </tex> нарушит неравенство, потому что либо само то и <tex> i j \leqslant k</tex> будет меньше, чем что противоречит условию <tex>j >k</tex>. Значит, либо <tex> Fj_{0} = k_{0}</tex>. Но тогда <tex>j</tex> возможно получить по формуле <tex>i_{next} = i_{prev} \mid (ii_{prev} + 1) </tex> станет больше. Получили противоречие, следовательно, чем <tex>F(j) > k </tex>. Таким образом, перебраны будут только нужные элементыможно искать по формуле <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex>.}}

Главными преимуществами данной конструкции являются простота реализации и быстрота ответов на запросы за <tex> O(\log{n}) </tex>. Также дерево Фенвика позволяет быстро изменять значения в массиве и находить некоторые функции от элементов занимает столько же памяти, сколько сами элементы массива<tex>A</tex>. Недостатком является то, что при изменении одного элемента исходного массиване все функции, которые могут использоваться в дереве отрезков (например, приходится пересчитывать частичные суммыминимум), а это затратно по времениприменимы к дереву Фенвика.