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>.