Изменения

Вспомним, что <tex>h(i)</tex> возвращает количество единиц в двоичной записи числа <tex>i</tex>, а каждый столбец прямого дерево дерева Фенвика вычисляется по формуле <tex>F(i) = \sum_{j=i-2^{h(i)}+1}^i a[j]</tex>

1) позволяет вычислять значение некоторой обратимой операции <tex>G</tex> на любом отрезке <tex>[L; R]</tex> за время <tex>O(\log N)</tex>;

Дерево Встречное дерево Фенвика позволяло вычислять значение применяется, когда нужно посчитать некоторую операцию на структуре без использования обратного элемента по этой операции <tex>G</tex> . Например, перед нами стоит задача посчитать произведение матриц, не считая обратных. С помощью встречного дерева Фенвика можно разложить запрос произведения на отрезке на <tex>[L; R]</tex> с помощью формулы включений-исключений и запросов вида <tex>G([0; R])</tex> и <tex>GO([0; L]\log N)</tex>дизъюнктных отрезков, операция для которых уже посчитана, получается почти как в дереве отрезков. Встречное дерево Фенвика позволяет нам сразу обрабатывать запрос вида <tex>G([L; R])</tex>