Изменения

Будем строить дерево Фенвика исходя из его описания. Можно заметить, что <tex>T_{i}</tex> можно считать быстрее, чем по формуле <tex> T_i = \sum\limits_{k = F(i)}^{i} a_k</tex>. Мы можем представить <tex>T_{i}</tex> как сумму нескольких элементов дерева с меньшими индексами и <tex>a_i</tex> (например, <tex>T_{7} = a_{7} + T_{6} + T_{5} + T_{3}</tex>). Такая сумма получается следующим образом:представим каждый элемент массива <tex>T</tex> как столбик (см. картинку). К <tex>a_i</tex> элементу прибавляем <tex>T_{i-1}</tex>. Далее прибавляем такой столбик, верхняя граница которого находится на том же уровне, что нижняя граница предыдущего прибавляемого столбика. Прекращаем складывать, когда нижняя граница нового столбика будет равна <tex>F(i)</tex>.

k = F(i) '''while''' j >= kF(i)