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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
'''Встречное дерево Фенвика''' — [[Дерево Фенвика|дерево Фенвика]], в котором над каждым столбцом идет столбец такой же высоты, вычисляемый по формуле <tex>F'(i) = \sum_{j=i+1}^{i+2^{h(i)}} a[j]</tex>.
 
'''Встречное дерево Фенвика''' — [[Дерево Фенвика|дерево Фенвика]], в котором над каждым столбцом идет столбец такой же высоты, вычисляемый по формуле <tex>F'(i) = \sum_{j=i+1}^{i+2^{h(i)}} a[j]</tex>.
 
}}
 
}}
 
[[Файл:Originalbit.png|thumb|Прямое дерево Фенвика]]
 
[[Файл:Vstbit.png|thumb|Встречное дерево Фенвика]]
 
  
 
Вспомним, что <tex>h(i)</tex> возвращает количество единиц в двоичной записи числа <tex>i</tex>, а каждый столбец прямого дерево Фенвика вычисляется по формуле <tex>F(i) = \sum_{j=i-2^{h(i)}+1}^i a[j]</tex>
 
Вспомним, что <tex>h(i)</tex> возвращает количество единиц в двоичной записи числа <tex>i</tex>, а каждый столбец прямого дерево Фенвика вычисляется по формуле <tex>F(i) = \sum_{j=i-2^{h(i)}+1}^i a[j]</tex>
  
 
== Свойства ==
 
== Свойства ==
 +
 +
[[Файл:Originalbit.png|thumb|Прямое дерево Фенвика]]
 +
[[Файл:Vstbit.png|thumb|Встречное дерево Фенвика]]
  
 
Встречное дерево Фенвика - это структура данных, дерево на массиве, обладающее следующими свойствами:
 
Встречное дерево Фенвика - это структура данных, дерево на массиве, обладающее следующими свойствами:
Строка 25: Строка 25:
 
== Применение ==
 
== Применение ==
  
Дерево Фенвика позволяло вычислять значение операции <tex>G</tex> на отрезке <tex>[L; R]</tex> с помощью формулы включений-исключений и запросов <tex>G([0; R])</tex> и <tex>G([0; L])</tex>. Встречное дерево Фенвика позволяет нам сразу обрабатывать запрос вида <tex>G([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 Дерево Фенвика]
 
[http://e-maxx.ru/algo/fenwick_tree Дерево Фенвика]

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

Ссылки

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