Изменения

Будем строить дерево Фенвика исходя из его описания. Можно заметить, что <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>a_i</tex> элемент не учитывался в предыдущих суммах, поэтому мы его прибавляем к <tex>T_i</tex>. <tex>a_{i-1}</tex> содержится только в <tex>T_{i-1}</tex>, поэтому прибавим <tex>T_{i-1}</tex>. Так как <tex>T_{i-1}</tex> может состоять из нескольких элементов из <tex>A</tex>, то мы пропустим все такие <tex>T_j</tex>, которые содержат элементы из <tex>T_{i-1}</tex>. Мы знаем, что <tex>T_j</tex> содержит <tex>a_j</tex>, поэтому можно пропустить все такие <tex>T_j</tex>, где <tex>j</tex> входит в диапазон от <tex>F(i - 1)</tex> до <tex>i - 2</tex> (индексы элементов <tex>T_{i-1}</tex>).