Изменения

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

== Любой отрезок Вспомним, что <tex>h(i)</tex> возвращает количество подряд идущих единиц в виде дизъюнктивных объединений отрезков конце двоичной записи числа <tex>i</tex>, а каждый столбец прямого дерева Фенвика вычисляется по формуле <tex>F(i) =\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..2^n</tex>. Оставшуюся часть можно разбить на 2 поддерева, т.е. отрезок |-|style="background-color:#EEE;padding:2px 30px"| <tex>2^{h(1..ni)}</tex> разбивается на подотрезки |style="background-color:#FFF;padding:2px 50px"| <tex>(1..n100 \ldots 0</tex>|-|style="background-color:#EEE;padding:2px 30px"| <tex>i + 2^{h(i)}</tex>, |style="background-color:#FFF;padding:2px 30px"| <tex>(n/2+\ldots 111 \ldots 1..n)</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 /tex> [L; R]<br /tex>в виде дизъюнктивных объединений отрезков, взятых из прямого и встречного дерева Фенвика.

Встречное дерево Фенвика применяется, когда нужно посчитать некоторую операцию на структуре без использования обратного элемента по этой операции. Например, перед нами стоит задача посчитать произведение матриц. Используя дерева Фенвика, мы можем столкнуться с такой ситуацией: элемент <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> дизъюнктных отрезков, операция для которых уже посчитана, получается почти как в дереве отрезков.==См. также==* [[Дерево Фенвика]] * [[Дерево отрезков. Построение |Дерево отрезков]] == Источники информации == * [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 Дерево ФенвикаСтруктуры данных]]