146
правок
Изменения
Нет описания правки
Вспомним, что <tex>h(i)</tex> возвращает количество единиц в двоичной записи числа <tex>i</tex>, а каждый столбец прямого дерева Фенвика вычисляется по формуле <tex>F(i) = \sum\limits_{j=i-2^{h(i)}+1}^i a[j]</tex>
== Любой отрезок в виде дизъюнктивных объединений отрезков Представление отрезка ==
[[Файл:Originalbit.png|thumb|Прямое дерево Фенвика]]
[[Файл:Vstbit.png|thumb|Встречное дерево Фенвика]]
== Применение ==
Встречное дерево Фенвика применяется, когда нужно посчитать некоторую операцию на структуре без использования обратного элемента по этой операции. Например, перед нами стоит задача посчитать произведениесумму матриц, не считая обратных. С помощью встречного дерева Фенвика можно разложить запрос произведения суммы на отрезке на <tex>O(\log N)</tex> дизъюнктных отрезков, операция для которых уже посчитана, получается почти как в дереве отрезков.
==См. также==
* [[Дерево Фенвика]]
== Источники информации ==
* [http://en.wikipedia.org/wiki/Fenwick_tree Wikipedia — Fenwick_tree Fenwick tree]
* [http://e-maxx.ru/algo/fenwick_tree Maximal:: algo:: Дерево Фенвика]
