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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
 
== Свойства ==
 
== Свойства ==
  
С помощью встречного дерева Фенвика можно представить любой отрезок от i до j в виде дизъюнктивных объединений отрезков, взятых из прямого и встречного дерева Фенвика.
+
Встречное дерево Фенвика - это структура данных, дерево на массиве, обладающее следующими свойствами:
 +
 
 +
1) позволяет вычислять значение некоторой обратимой операции G на любом отрезке [L; R] за время <tex>O(\log N)</tex>;
 +
 
 +
2) позволяет изменять значение любого элемента за <tex>O(\log N)</tex>;
 +
 
 +
3) требует <tex>O (N)</tex> памяти, а точнее, ровно столько же, сколько и массив из N элементов;
 +
 
 +
4) легко обобщается на случай многомерных массивов.
 +
 
 +
5) позволяет представить любой отрезок от i до j в виде дизъюнктивных объединений отрезков, взятых из прямого и встречного дерева Фенвика.

Версия 03:34, 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) позволяет вычислять значение некоторой обратимой операции G на любом отрезке [L; R] за время [math]O(\log N)[/math];

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

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

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

5) позволяет представить любой отрезок от i до j в виде дизъюнктивных объединений отрезков, взятых из прямого и встречного дерева Фенвика.