272
правки
Изменения
Нет описания правки
{{Определение
| definition =
'''Дерево Фе́нвика (Binary indexed tree)''' - структура данных, требующая <tex> O(n) </tex> памяти и позволяющая эффективно (за <tex> O(log n) </tex>)
# изменять значение любого элемента в массиве;
Пусть дан массив <tex> A </tex> из <tex> n </tex> элементов: <tex> a_i, i = \overline{0, n} </tex>.<br/>
Деревом Фенвика будем называть массив <tex> T </tex> из <tex> n </tex> элементов: <tex> T_i = \sum\limits_{k = F(i)}^{i} a_k, i = \overline{0, n} </tex>, где <tex> F(i) </tex> - некоторая функция.
От выбора функции зависит время работы операций над деревом. Рассмотрим функцию, позволяющую делать обе операции за время <tex> O(log(n)) </tex>.
[[Файл:Bit.jpg|thumb|300px|Содержимое массива T]]
Обозначим <tex> G_i = sum(i) = \sum\limits_{k = 0}^{i} a_k </tex>. Тогда <tex> sum(i, j) = \sum\limits_{k = i}^{j} a_k = G_j - G_{i - 1} </tex>.
{{Утверждение
|statement= <tex> a_i </tex> входит в сумму для <tex> f_k </tex>, если <tex> \exists j: k = i \vee (1 \cdots 1) j </tex> раз.
|proof=
}}
Приведем код функции <tex> sum(i) </tex> на C++:
<code>
