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