146
правок
Изменения
Нет описания правки
==Построение дерева==
Будем строить дерево Фенвика исходя из его описания. Можно заметить, что <tex>T_{i}</tex> Но можно считать быстрее, чем по формуле если делать set каждого элемента массива <tex> T_i = \sum\limits_{k = F(i)}^{i} a_kA</tex>. Мы можем представить <tex>T_{i}</tex> как сумму нескольких элементов дерева с меньшими индексами и <tex>a_iТогда мы получим время работы </tex> O(например, <tex>T_{7} = a_{7} + T_{6} + T_{5} + T_n \log {3n}</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>\circ</tex>. Чтобы получить значение на отрезке <tex>[i, j]</tex>, нужно провести операцию, обратную к <tex>\circ</tex>, над значениями на отрезках <tex>[0, j]</tex> и <tex>[0, i - 1]</tex>.
Обозначим <tex> G_i = \mathrm sum(i) = \sum\limits_{k = 0}^{i} a_k </tex>. Тогда <tex> \mathrm sum(i, j) = \sum\limits_{k = i}^{j} a_k = G_j - G_{i - 1} </tex>.
=== Реализация ===
Приведем код функции <tex> \mathrm sum(i) </tex>:
'''int''' sum(i):
result = 0t[i]; '''whileif''' f(i ) >= 0 result += t[i] i = sum(f(i) - 1) '''else''' '''return''' result
==Сравнение дерева Фенвика и дерева отрезков==
