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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
[[Файл:Originalbit.png|thumb|Прямое дерево Фенвика]]
 +
[[Файл:Vstbit.png|thumb|Встречное дерево Фенвика]]
 +
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Строка 7: Строка 10:
  
 
== Свойства ==
 
== Свойства ==
 
[[Файл:Originalbit.png|thumb|Прямое дерево Фенвика]]
 
[[Файл:Vstbit.png|thumb|Встречное дерево Фенвика]]
 
  
 
Встречное дерево Фенвика - это структура данных, дерево на массиве, обладающее следующими свойствами:
 
Встречное дерево Фенвика - это структура данных, дерево на массиве, обладающее следующими свойствами:

Версия 04:03, 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]

Ссылки

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