'''Встречное дерево Фенвика''' (англ. ''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>|} {| 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>|}
== Представление отрезка ==
[[Файл:Originalbit.png|thumb|Прямое дерево Фенвика]]{{Теорема[[Файл:Vstbit.png|thumb|Встречное дерево Фенвика]]Докажем, что 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})</tex>, <tex>(\dfrac{n}{2} + 1..n)</tex>. В итоге получается структура обычного [[Дерево отрезков. Построение|дерева отрезков]], для которого известно указанное выше утверждение.
Стоит отметить, что поддерево для <tex>(\dfrac{n}{2} + 1..n)</tex> получается "перевернутым" из-за того, что встречное дерево, по сути, идет от <tex>n - 1</tex> до <tex>1</tex> в обратном порядке.
}}
== Свойства ==
