146
правок
Изменения
Нет описания правки
Эту функцию можно вычислять по другой формуле: <tex> F(i) = i - 2^{h(i)} + 1, </tex> где <tex> h(i) </tex> — количество подряд идущих единиц в конце бинарной записи числа <tex> i </tex>. Оба варианта равносильны, так как функция, заданная какой-либо из этих формул, заменяет все подряд идущие единицы в конце числа на нули.
== Запрос изменения элемента ==
i = f(i) - 1
'''return''' result
==Построение дерева==
Будем строить дерево Фенвика исходя из его описания. Можно заметить, что <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>).
Другими словами, представим каждый элемент массива <tex>T</tex> как столбик (см. картинку). К <tex>a_i</tex> элементу прибавляем <tex>T_{i-1}</tex>. Далее прибавляем такой столбик, верхняя граница которого находится на том же уровне, что нижняя граница предыдущего прибавляемого столбика. Прекращаем складывать, когда нижняя граница нового столбика будет равна <tex>F(i)</tex>.
'''function''' init(i)
t[i] = a[i]
j = i - 1
'''while''' j >= F(i)
t[i] += t[j]
j = F(j) - 1
Такое построение будет работать за <tex>O(n \log{n})</tex>.
==Сравнение дерева Фенвика и дерева отрезков==
