Изменения
Нет описания правки
{{Определение
|definition=
'''Дерево Фе́нвика (Binary indexed tree)''' - структура данных, требующая <tex> O(n) </tex> памяти и позволяющая эффективно (за <tex> O(\log n) </tex>)
# изменять значение любого элемента в массиве;
# выполнять некоторую ассоциативную, коммутативную, обратимую операцию <tex> G </tex> на отрезке <tex> [i, j] </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>.
{{УтверждениеЛемма|statement='''Лемма.''' <tex> a_i </tex> входит в сумму для <tex> t_k </tex>, если <tex> \exists j: k = i | \cdots(1 \cdots 2^j - 1) j </tex> раз.
}}
Для доказательства леммы рассмотрим битовую запись следующих чисел: <tex> k - 2^{h(k) + 1} \leq i \leq k </tex>
