419
правок
Изменения
Нет описания правки
'''Встречное дерево Фенвика''' — [[Дерево Фенвика|дерево Фенвика]], в котором над каждым столбцом идет столбец такой же высоты, вычисляемый по формуле <tex>F'(i) = \sum_{j=i+1}^{i+2^{h(i)}} a[j]</tex>.
}}
Вспомним, что <tex>h(i)</tex> возвращает количество единиц в двоичной записи числа <tex>i</tex>, а каждый столбец прямого дерево Фенвика вычисляется по формуле <tex>F(i) = \sum_{j=i-2^{h(i)}+1}^i a[j]</tex>
== Свойства ==
[[Файл:Originalbit.png|thumb|Прямое дерево Фенвика]]
[[Файл:Vstbit.png|thumb|Встречное дерево Фенвика]]
Встречное дерево Фенвика - это структура данных, дерево на массиве, обладающее следующими свойствами:
== Применение ==
Дерево Фенвика позволяло вычислять значение операции <tex>G</tex> на отрезке <tex>[L; R]</tex> с помощью формулы включений-исключений и запросов вида <tex>G([0; R])</tex> и <tex>G([0; L])</tex>. Встречное дерево Фенвика позволяет нам сразу обрабатывать запрос вида <tex>G([L; R])</tex>
== Ссылки ==
[http://e-maxx.ru/algo/fenwick_tree Дерево Фенвика]
