Встречное дерево Фенвика — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства)
Строка 22: Строка 22:
  
 
5) позволяет представить любой отрезок <tex>[L; R]</tex> в виде дизъюнктивных объединений отрезков, взятых из прямого и встречного дерева Фенвика.
 
5) позволяет представить любой отрезок <tex>[L; R]</tex> в виде дизъюнктивных объединений отрезков, взятых из прямого и встречного дерева Фенвика.
 +
 +
== Применение ==
 +
 +
Дерево Фенвика позволяло вычислять значение операции <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 Дерево Фенвика]

Версия 03:59, 17 мая 2011

Определение:
Встречное дерево Фенвикадерево Фенвика, в котором над каждым столбцом идет столбец такой же высоты, вычисляемый по формуле [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]

Ссылки

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