Изменения
Нет описания правки
Пусть дан массив <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>.
<tex> F(i) = i - 2^{h(i) + 1}, </tex> где <tex> h(i) </tex> - количество единиц в конце бинарной записи числа <tex> i </tex>.
{{Лемма
|statement= <tex> a_i </tex> входит в сумму для <tex> t_k </tex>, если <tex> \exists j: k = i | (2^j - 1) </tex> раз.
}}
Для доказательства леммы рассмотрим битовую запись следующих чисел: <tex> k - 2^{h(k) + 1} \leq i \leq k </tex>
