Встречное дерево Фенвика

Определение:

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

Прямое дерево Фенвика

Встречное дерево Фенвика

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

Свойства

Встречное дерево Фенвика - это структура данных, дерево на массиве, обладающее следующими свойствами:

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

2) позволяет изменять значение любого элемента за [math]O(\log N)[/math];

3) требует [math]O (N)[/math] памяти, а точнее, ровно столько же, сколько и массив из [math]2N[/math] элементов;

4) легко обобщается на случай многомерных массивов.

5) позволяет представить любой отрезок [math][L; R][/math] в виде дизъюнктивных объединений отрезков, взятых из прямого и встречного дерева Фенвика.

Применение

Дерево Фенвика позволяло вычислять значение операции [math]G[/math] на отрезке [math][L; R][/math] с помощью формулы включений-исключений и запросов [math]G([0; R])[/math] и [math]G([0; L])[/math]. Встречное дерево Фенвика позволяет нам сразу обрабатывать запрос вида [math]G([L; R])[/math]

Ссылки

Дерево Фенвика