Изменения

'''Встречное дерево Фенвика''' (англ. ''counter tree Fenwick'') — [[Дерево Фенвика|дерево Фенвика]], в котором над каждым столбцом идет столбец такой же высоты, вычисляемый по формуле <tex>F'(i) = \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 = i \mid (i + 1) </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> в обратном порядке.