Изменения

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

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

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

* Встречное дерево Фенвика - это структура данныхтребует <tex>O (N)</tex> памяти, дерево на массивеа точнее, ровно столько же, обладающее следующими свойствами:сколько и массив из <tex>2N</tex> элементов;

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

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

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

5) позволяет представить любой отрезок <tex>* [L; R]</tex> в виде дизъюнктивных объединений [Дерево отрезков, взятых из прямого и встречного дерева Фенвика.Построение |Дерево отрезков]]

<br == Источники информации == * [http:/> <br />en.wikipedia.org/wiki/Fenwick_tree Wikipedia — Fenwick_tree Fenwick tree]* [http://e-maxx.ru/algo/fenwick_tree Maximal:: algo:: Дерево Фенвика]

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

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