Изменения

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

[[Файл{| style="background-color:#CCC;margin:Originalbit0.png5px"|style="background-color:#EEE;padding:2px 30px"| <tex>i</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>\ldots 011 \ldots 1</tex>|-|style="background-color:#EEE;padding:2px 30px"| <tex>i + 1</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>\ldots 100 \ldots 0</tex>|thumb-|leftstyle="background-color:#EEE;padding:2px 30px"|Прямое дерево Фенвика]]<tex>i \mid (i + 1)</tex>[[Файл|style="background-color:#FFF;padding:Vstbit.png2px 30px"|thumb<tex>\ldots 111 \ldots 1</tex>|Встречное дерево Фенвика]]}

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

1) позволяет вычислять значение некоторой обратимой операции Стоит отметить, что поддерево для <tex>G(\dfrac{n}{2} + 1..n)</tex> на любом отрезке получается "перевернутым" из-за того, что встречное дерево, по сути, идет от <tex>[L; R]n - 1</tex> за время до <tex>O(\log N)1</tex>;в обратном порядке.}}== Свойства ==

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

3) требует * Такое дерево позволяет изменять значение любого элемента за <tex>O (\log N)</tex> памяти, а точнее, ровно столько же, сколько и массив из <tex>2N</tex> элементов;

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

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

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

Дерево Встречное дерево Фенвика позволяло вычислять значение применяется, когда нужно посчитать некоторую операцию на структуре без использования обратного элемента по этой операции . Например, перед нами стоит задача посчитать произведение. Используя дерева Фенвика, мы можем столкнуться с такой ситуацией: элемент <tex>Ga[i] = 0</tex> . Тогда, считая произведение на отрезке <tex>[L; Rl, r]</tex> с помощью формулы включений-исключений и запросов вида (где <tex>l > i</tex>) как произведение на отрезке <tex>G([0; R, r])</tex> и , делённое на произведение на отрезке <tex>G([0; L, l - 1])</tex>. Встречное , мы получим неопределённое значение <tex>\dfrac{0}{0}</tex>, поэтому нужно использовать встречное дерево Фенвика позволяет нам сразу обрабатывать . С его помощью можно разложить запрос вида произведения на отрезке на <tex>GO([L; R]\log N)</tex>дизъюнктных отрезков, операция для которых уже посчитана, получается почти как в дереве отрезков.==См. также==* [[Дерево Фенвика]] * [[Дерево отрезков. Построение |Дерево отрезков]] == Источники информации == * [http://en.wikipedia.org/wiki/Fenwick_tree Wikipedia — Fenwick tree]* [http://e-maxx.ru/algo/fenwick_tree Maximal:: algo:: Дерево Фенвика] [[Категория: Дискретная математика и алгоритмы]] [[Категория: Дерево Фенвика]]

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