272
правки
Изменения
Нет описания правки
}}
Впервые описано Питером Фенвиком в 1994 году.
Пусть дан массив <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> 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>.
