146
правок
Изменения
Нет описания правки
{{Определение
|definition=
'''Встречное дерево Фенвика''' (англ. ''counter tree Fenwick'') — [[Дерево Фенвика|дерево Фенвика]], в котором над каждым столбцом идет столбец такой же высоты, вычисляемый по формуле <tex>F'(i) = \sum_sum\limits_{j=i+1}^{i+2^{h(i)}} a[j]</tex>.
}}
[[Файл:Originalbit.png|thumb|Прямое дерево Фенвика]]
[[Файл:Vstbit.png|thumb|Встречное дерево Фенвика]]
Вспомним, что <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</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>
|}
{| 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>. В итоге получается структура обычного [[Дерево отрезков. Построение|дерева отрезков]], для которого известно указанное выше утверждение.
Стоит отметить, что поддерево для <tex>(\dfrac{n}{2} + 1..n)</tex> получается "перевернутым" из-за того, что встречное дерево, по сути, идет от <tex>n - 1</tex> до <tex>1</tex> в обратном порядке.
}}
== Свойства ==
* Встречное дерево Фенвика - это структура данныхтребует <tex>O (N)</tex> памяти, дерево на массивеа точнее, ровно столько же, обладающее следующими свойствами:сколько и массив из <tex>2N</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>