61
правка
Изменения
→Дерево Фенвика
====Дерево Фенвика====
{{main|Дерево Фенвика}}
'''Дерево Фенвика''' (англ. ''Binary indexed tree'') {{---}} структура данных, которая может выполнять следующие операции:
* изменять значение любого элемента в массиве,
* выполнять некоторую [[Ассоциативная_операция |ассоциативную]], [[Абелева_группа |коммутативную]], [[Группа |обратимую операцию]] <tex> \circ </tex> на отрезке <tex> [i, j] </tex>.
Данная структура требует <tex> O(n) </tex> памяти, а выполнение каждой операции происходит за <tex> O(\log n) </tex> .
Функция, позволяющая делать операции вставки и изменения элемента за <tex> O(\log n) </tex>, задается следующей формулой <tex> F(i) = (i \And (i + 1)) </tex>.
Пусть дан массив <tex> A = [a_0, a_1, ... , a_{n - 1}]</tex>.
Деревом Фенвика называется массив <tex> T </tex> из <tex> n </tex> элементов: <tex> T_i = \sum\limits_{k = F(i)}^{i} a_k</tex>, где <tex> i = 0 .. n - 1 </tex> и <tex> F(i) </tex> — функция, которую мы определили ранее.
==См. также==
