Изменения

{{Определение|definition='''Встречное дерево Фенвика''' — [[Дерево Фенвика|дерево Фенвика]]Вспомним, что <tex>h(i)</tex> возвращает количество подряд идущих единиц в котором над каждым столбцом идет конце двоичной записи числа <tex>i</tex>, а каждый столбец такой же высоты, вычисляемый прямого дерева Фенвика вычисляется по формуле <tex>F'(i) = \sum_sum\limits_{j=i- 2^{h(i)} +1}^i a[j]</tex>. <tex>i + 2^{h(i)}</tex> можно считать по равносильной формуле <tex> i \mid (i + 1) </tex>. Рассмотрим, что делают эти формулы с двоичной записью числа <tex>i</tex>. Формула <tex>i + 2^{h(i)}</tex> изменяет последний ноль на единицу. Аналогично работает и <tex> i \mid (i + 1) </tex>.   {| style="background-color:#CCC;margin:0.5px"|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>2^{h(i)}</tex>|style="background-color:#FFF;padding:2px 50px"| <tex> 100 \ldots 0</tex>|-|style="background-color:#EEE;padding:2px 30px"| <tex>i+2^{h(i)}</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>\ldots 111 \ldots 1</tex>|} a   {| style="background-color:#CCC;margin:0.5px"|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>|-|style="background-color:#EEE;padding:2px 30px"| <tex>i \mid (i + 1)</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>\ldots 111 \ldots 1</tex>|}  == Представление отрезка =={{Теорема|statement=Любой отрезок можно представить в виде дизъюнктивных объединений <tex>O(\log N)</tex> отрезков, взятых из прямого и встречного дерева Фенвика.|proof=Представим встречное дерево Фенвика <tex>2^n</tex> на <tex>2^n</tex> и посмотрим на него, как на дерево отрезков. В нем существует отрезок <tex>[1..2^n]</tex>. Оставшуюся часть можно разбить на <tex>2</tex> поддерева, т.е. отрезок <tex>(1..n)</tex> разбивается на подотрезки <tex>(1..\dfrac {n}{2}), (\dfrac{n}{2} + 1..n)</tex>. В итоге получается структура обычного [[jДерево отрезков. Построение|дерева отрезков]], для которого известно указанное выше утверждение. Стоит отметить, что поддерево для <tex>(\dfrac{n}{2} + 1..n)</tex> получается "перевернутым" из-за того, что встречное дерево, по сути, идет от <tex>n - 1</tex>до <tex>1</tex> в обратном порядке.

Вспомним, что * Встречное дерево Фенвика позволяет вычислять значение некоторой операции <tex>h(i)G</tex> возвращает количество единиц в двоичной записи числа на любом отрезке <tex>i[L; R]</tex>, а каждый столбец прямого дерево Фенвика вычисляется по формуле за время <tex>FO(i) = \sum_{j=i-2^{h(ilog N)}+1}^i a[j]</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>a[i] = 0</tex>. Тогда, считая произведение на отрезке <tex>[l, r]</tex> (где <tex>l > i</tex>) легко обобщается как произведение на отрезке <tex>[0, r]</tex>, делённое на произведение на отрезке <tex>[0, l - 1]</tex>, мы получим неопределённое значение <tex>\dfrac{0}{0}</tex>, поэтому нужно использовать встречное дерево Фенвика. С его помощью можно разложить запрос произведения на отрезке на случай многомерных массивов<tex>O(\log N)</tex> дизъюнктных отрезков, операция для которых уже посчитана, получается почти как в дереве отрезков.==См.также==* [[Дерево Фенвика]]

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

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

[[Категория: Дерево Фенвика позволяло вычислять значение операции <tex>G</tex> на отрезке <tex>[L; R]</tex> с помощью формулы включений-исключений и запросов вида <tex>G([0; R])</tex> и <tex>G([0; L])</tex>. Встречное дерево Фенвика позволяет нам сразу обрабатывать запрос вида <tex>G([L; R])</tex>

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