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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 6: Строка 6:
 
Вспомним, что <tex>h(i)</tex> возвращает количество единиц в двоичной записи числа <tex>i</tex>, а каждый столбец прямого дерева Фенвика вычисляется по формуле <tex>F(i) = \sum\limits_{j=i-2^{h(i)}+1}^i a[j]</tex>
 
Вспомним, что <tex>h(i)</tex> возвращает количество единиц в двоичной записи числа <tex>i</tex>, а каждый столбец прямого дерева Фенвика вычисляется по формуле <tex>F(i) = \sum\limits_{j=i-2^{h(i)}+1}^i a[j]</tex>
  
== Любой отрезок в виде дизъюнктивных объединений отрезков ==
+
== Представление отрезка ==
 
[[Файл:Originalbit.png|thumb|Прямое дерево Фенвика]]
 
[[Файл:Originalbit.png|thumb|Прямое дерево Фенвика]]
 
[[Файл:Vstbit.png|thumb|Встречное дерево Фенвика]]
 
[[Файл:Vstbit.png|thumb|Встречное дерево Фенвика]]
Строка 31: Строка 31:
 
== Применение ==
 
== Применение ==
  
Встречное дерево Фенвика применяется, когда нужно посчитать некоторую операцию на структуре без использования обратного элемента по этой операции. Например, перед нами стоит задача посчитать произведение, не считая обратных. С помощью встречного дерева Фенвика можно разложить запрос произведения на отрезке на <tex>O(\log N)</tex> дизъюнктных отрезков, операция для которых уже посчитана, получается почти как в дереве отрезков.
+
Встречное дерево Фенвика применяется, когда нужно посчитать некоторую операцию на структуре без использования обратного элемента по этой операции. Например, перед нами стоит задача посчитать сумму матриц, не считая обратных. С помощью встречного дерева Фенвика можно разложить запрос суммы на отрезке на <tex>O(\log N)</tex> дизъюнктных отрезков, операция для которых уже посчитана, получается почти как в дереве отрезков.
 
==См. также==
 
==См. также==
 
* [[Дерево Фенвика]]
 
* [[Дерево Фенвика]]
Строка 38: Строка 38:
  
 
== Источники информации ==  
 
== Источники информации ==  
* [http://en.wikipedia.org/wiki/Fenwick_tree Wikipedia — Fenwick_tree Fenwick tree]
+
* [http://en.wikipedia.org/wiki/Fenwick_tree Wikipedia — Fenwick tree]
 
* [http://e-maxx.ru/algo/fenwick_tree Maximal:: algo:: Дерево Фенвика]
 
* [http://e-maxx.ru/algo/fenwick_tree Maximal:: algo:: Дерево Фенвика]
  

Версия 23:18, 3 июня 2015

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


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

Представление отрезка

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

Докажем, что можно представить любой отрезок в виде дизъюнктивных объединений [math]O(\log N)[/math] отрезков, взятых из прямого и встречного дерева Фенвика.

Представим встречное дерево Фенвика [math]2^n[/math] на [math]2^n[/math] и посмотрим на него, как на дерево отрезков.

В нем существует отрезок [math][1..2^n][/math]. Оставшуюся часть можно разбить на 2 поддерева, т.е. отрезок [math](1..n)[/math] разбивается на подотрезки [math](1..n/2)[/math], [math](n/2+1..n)[/math]. В итоге получается структура обычного дерева отрезков, для которого известно указанное выше утверждение.

Стоит отметить, что поддерево для [math](n/2+1..n)[/math] получается "перевернутым" из-за того, что встречное дерево, по сути, идет от [math]n-1[/math] до [math]1[/math] в обратном порядке.

Свойства

  • Встречное дерево Фенвика позволяет вычислять значение некоторой операции [math]G[/math] на любом отрезке [math][L; R][/math] за время [math]O(\log N)[/math];
  • Такое дерево позволяет изменять значение любого элемента за [math]O(\log N)[/math];
  • Встречное дерево Фенвика требует [math]O (N)[/math] памяти, а точнее, ровно столько же, сколько и массив из [math]2N[/math] элементов;
  • Данная структура данных легко обобщается на случай многомерных массивов.
  • Такое дерево Фенвика позволяет представить любой отрезок [math][L; R][/math] в виде дизъюнктивных объединений отрезков, взятых из прямого и встречного дерева Фенвика.

Применение

Встречное дерево Фенвика применяется, когда нужно посчитать некоторую операцию на структуре без использования обратного элемента по этой операции. Например, перед нами стоит задача посчитать сумму матриц, не считая обратных. С помощью встречного дерева Фенвика можно разложить запрос суммы на отрезке на [math]O(\log N)[/math] дизъюнктных отрезков, операция для которых уже посчитана, получается почти как в дереве отрезков.

См. также

Источники информации