146
правок
Изменения
Нет описания правки
modify(i, d)
==Построение дерева==
Будем строить дерево Фенвика исходя из его описания. Можно заметить, что <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>.
Покажем, что если мы прибавили столбик, то <tex>F(i) \leqslant F(j)</tex>, то его нижняя граница не ниже, чем нижняя граница столбика <tex>T_i</tex>. Прибавление столбика возможно при условии <tex>F(i) \leqslant j \leqslant i</tex>. Это значит, что отбросив количество цифр, равное количеству последних единиц у числа <tex> i </tex>, из конца двоичной записи <tex>F(i)</tex>, <tex>j</tex> и <tex> i</tex>, то мы получим равные числа. Тогда <tex>F(j)</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>.
== Запрос получения значения функции на префиксе ==
Пусть существует некоторая бинарная операция <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):
i = f(i) - 1
'''return''' result
==Сравнение дерева Фенвика и дерева отрезков==
