Изменения
Нет описания правки
Впервые описано Питером Фенвиком в 1994 году.
Пусть дан массив <tex> A </tex> из <tex> n </tex> элементов: <tex> a_i, i = \overline{0, n- 1} </tex>.<br/>Деревом Фенвика будем называть массив <tex> T </tex> из <tex> n </tex> элементов: <tex> T_i = \sum\limits_{k = F(i)}^{i} a_k, i = \overline{0, n- 1} </tex>, где <tex> F(i) </tex> - некоторая функция.
От выбора функции зависит время работы операций над деревом. Рассмотрим функцию, позволяющую делать обе операции за время <tex> O(\log n) </tex>.
Необходимо изменить элементы дерева <tex>T_{i}</tex>, для которых верно неравенство <tex>F(i) \leq k \leq i</tex> .
|proof=
<tex> T_i =\sum\limits_{k = F(i)}^{i} a_k , i = \overline{0, n- 1} \Rightarrow</tex> необходимо менять те <tex>i</tex>, для которых <tex>a_{k}</tex> попадает в <tex>T_i \Rightarrow</tex> необходимые <tex> i </tex> удовлетворяют условию <tex>F(i) < \leq k <= \leq i</tex>.
}}
