Изменения

'''Встречное дерево Фенвика''' (англ. ''counter tree Fenwick'') — [[Дерево Фенвика|дерево Фенвика]], в котором над каждым столбцом идет столбец такой же высоты, вычисляемый по формуле <tex>F'(i) = \sum_sum\limits_{j=i+1}^{i+2^{h(i)}} a[j]</tex>.

Вспомним, что {| style="background-color:#CCC;margin:0.5px"|style="background-color:#EEE;padding:2px 30px"| <tex>h(i)</tex> возвращает количество единиц в двоичной записи числа |style="background-color:#FFF;padding:2px 30px"| <tex>i\ldots 011 \ldots 1</tex>, а каждый столбец прямого дерева Фенвика вычисляется по формуле |-|style="background-color:#EEE;padding:2px 30px"| <tex>F(i) + 1</tex>|style= "background-color:#FFF;padding:2px 30px"| <tex>\sum_{jldots 100 \ldots 0</tex>|-|style="background-color:#EEE;padding:2px 30px"| <tex>i-2^{h \mid (i+ 1)}+</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>\ldots 111 \ldots 1}^i a[j]</tex>|}

В нем существует отрезок длины <tex>[1..<tex>2^n]</tex>. Оставшуюся часть можно разбить на <tex>2 </tex> поддерева, т.е. отрезок <tex>(1. То есть .n)</tex> разбивается на подотрезки <tex>(1..\dfrac {n}{2}), (\dfrac{n}{2} + 1..n)</tex>. В итоге получается структура обычного [[Дерево отрезков. Построение|дерева отрезков]], для которого известно указанное выше утверждение.

[[Файл:Originalbit.png|thumb|left|Прямое * Встречное дерево Фенвика]][позволяет вычислять значение некоторой операции <tex>G</tex> на любом отрезке <tex>[Файл:Vstbit.png|thumb|Встречное дерево Фенвика]L; R]</tex> за время <tex>O(\log N)</tex>;

Встречное дерево Фенвика - это * Данная структура данных, дерево легко обобщается на массиве, обладающее следующими свойствами:случай многомерных массивов.

1) * Такое дерево Фенвика позволяет вычислять значение некоторой операции <tex>G</tex> на любом отрезке представить любой отрезок <tex>[L; R]</tex> за время <tex>O(\log N)</tex>;в виде дизъюнктивных объединений отрезков, взятых из прямого и встречного дерева Фенвика.

3) требует Встречное дерево Фенвика применяется, когда нужно посчитать некоторую операцию на структуре без использования обратного элемента по этой операции. Например, перед нами стоит задача посчитать произведение. Используя дерева Фенвика, мы можем столкнуться с такой ситуацией: элемент <tex>a[i] = 0</tex>. Тогда, считая произведение на отрезке <tex>[l, r]</tex>O (Nгде <tex>l > i</tex>)как произведение на отрезке <tex>[0, r]</tex> памяти, а точнееделённое на произведение на отрезке <tex>[0, l - 1]</tex>, ровно столько жемы получим неопределённое значение <tex>\dfrac{0}{0}</tex>, сколько и массив из поэтому нужно использовать встречное дерево Фенвика. С его помощью можно разложить запрос произведения на отрезке на <tex>2NO(\log N)</tex> элементов;дизъюнктных отрезков, операция для которых уже посчитана, получается почти как в дереве отрезков.==См. также==* [[Дерево Фенвика]]

4) легко обобщается на случай многомерных массивов* [[Дерево отрезков.Построение |Дерево отрезков]]

5) позволяет представить любой отрезок <tex>== Источники информации == * [L; Rhttp://en.wikipedia.org/wiki/Fenwick_tree Wikipedia — Fenwick tree]<* [http:/tex> в виде дизъюнктивных объединений отрезков, взятых из прямого и встречного дерева /e-maxx.ru/algo/fenwick_tree Maximal:: algo:: Дерево Фенвика.]

<br /> <br /> == Применение ==[[Категория: Дискретная математика и алгоритмы]]

Встречное дерево [[Категория: Дерево Фенвика применяется, когда нужно посчитать некоторую операцию на структуре без использования обратного элемента по этой операции. Например, перед нами стоит задача посчитать произведение матриц, не считая обратных. С помощью встречного дерева Фенвика можно разложить запрос произведения на отрезке на <tex>O(\log N)</tex> дизъюнктных отрезков, операция для которых уже посчитана, получается почти как в дереве отрезков.]]

== Ссылки == [http[Категория://e-maxx.ru/algo/fenwick_tree Дерево ФенвикаСтруктуры данных]]