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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 7 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Встречное дерево Фенвика''' — [[Дерево Фенвика|дерево Фенвика]], в котором над каждым столбцом идет столбец такой же высоты, вычисляемый по формуле <tex>F'(i) = \sum\limits_{j=i+1}^{i+2^{h(i)}} a[j]</tex>.
+
'''Встречное дерево Фенвика''' (англ. ''counter tree Fenwick'') — [[Дерево Фенвика|дерево Фенвика]], в котором над каждым столбцом идет столбец такой же высоты, вычисляемый по формуле <tex>F'(i) = \sum\limits_{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\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>.
 +
 
 +
<tex>i + 2^{h(i)}</tex> можно считать по равносильной формуле <tex> i  \mid  (i + 1) </tex>. Рассмотрим, что делают эти формулы с двоичной записью числа <tex>i</tex>. Формула <tex>i + 2^{h(i)}</tex> изменяет последний ноль на единицу. Аналогично работает и <tex> i  \mid  (i + 1) </tex>.
  
Докажем, что можно представить любой отрезок в виде дизъюнктивных объединений <tex>O(\log N)</tex> отрезков, взятых из прямого и встречного дерева Фенвика.
 
  
Представим встречное дерево Фенвика <tex>2^n</tex> на <tex>2^n</tex> и посмотрим на него, как на дерево отрезков.
 
  
В нем существует отрезок длины <tex>1..2^n</tex>. Оставшуюся часть можно разбить на 2 поддерева, т.е. отрезок <tex>(1..n)</tex> разбивается на подотрезки <tex>(1..n/2)</tex>, <tex>(n/2+1..n)</tex>. В итоге получается структура обычного [[Дерево отрезков. Построение|дерева отрезков]], для которого известно указанное выше утверждение.
+
{| style="background-color:#CCC;margin:0.5px"
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>i</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\ldots 011 \ldots 1</tex>
 +
|-
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>2^{h(i)}</tex>
 +
|style="background-color:#FFF;padding:2px 50px"| <tex> 100 \ldots 0</tex>
 +
|-
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>i + 2^{h(i)}</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\ldots 111 \ldots 1</tex>
 +
|}
  
Стоит отметить, что поддерево для <tex>(n/2+1..n)</tex> получается "перевернутым" из-за того, что встречное дерево, по сути, идет от <tex>n-1</tex> до <tex>1</tex> в обратном порядке.
 
  
== Свойства ==
 
  
[[Файл:Originalbit.png|thumb|left|Прямое дерево Фенвика]]
+
{| style="background-color:#CCC;margin:0.5px"
[[Файл:Vstbit.png|thumb|Встречное дерево Фенвика]]
+
|style="background-color:#EEE;padding:2px 30px"| <tex>i</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\ldots 011 \ldots 1</tex>
 +
|-
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>i + 1</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\ldots 100 \ldots 0</tex>
 +
|-
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>i  \mid  (i + 1)</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\ldots 111 \ldots 1</tex>
 +
|}
  
  
 +
== Представление отрезка ==
 +
{{Теорема
 +
|statement=Любой отрезок можно представить в виде дизъюнктивных объединений <tex>O(\log N)</tex> отрезков, взятых из прямого и встречного дерева Фенвика.
 +
|proof=
 +
Представим встречное дерево Фенвика <tex>2^n</tex> на <tex>2^n</tex> и посмотрим на него, как на дерево отрезков.
  
Встречное дерево Фенвика - это структура данных, дерево на массиве, обладающее следующими свойствами:
+
В нем существует отрезок <tex>[1..2^n]</tex>. Оставшуюся часть можно разбить на <tex>2</tex> поддерева, т.е. отрезок <tex>(1..n)</tex> разбивается на подотрезки <tex>(1..\dfrac {n}{2}), (\dfrac{n}{2} + 1..n)</tex>. В итоге получается структура обычного [[Дерево отрезков. Построение|дерева отрезков]], для которого известно указанное выше утверждение.
  
1) позволяет вычислять значение некоторой операции <tex>G</tex> на любом отрезке <tex>[L; R]</tex> за время <tex>O(\log N)</tex>;
+
Стоит отметить, что поддерево для <tex>(\dfrac{n}{2} + 1..n)</tex> получается "перевернутым" из-за того, что встречное дерево, по сути, идет от <tex>n - 1</tex> до <tex>1</tex> в обратном порядке.
 +
}}
 +
== Свойства ==
  
2) позволяет изменять значение любого элемента за <tex>O(\log N)</tex>;
+
* Встречное дерево Фенвика позволяет вычислять значение некоторой операции <tex>G</tex> на любом отрезке <tex>[L; R]</tex> за время <tex>O(\log N)</tex>;
  
3) требует <tex>O (N)</tex> памяти, а точнее, ровно столько же, сколько и массив из <tex>2N</tex> элементов;
+
* Такое дерево позволяет изменять значение любого элемента за <tex>O(\log N)</tex>;
  
4) легко обобщается на случай многомерных массивов.
+
* Встречное дерево Фенвика требует <tex>O (N)</tex> памяти, а точнее, ровно столько же, сколько и массив из <tex>2N</tex> элементов;
  
5) позволяет представить любой отрезок <tex>[L; R]</tex> в виде дизъюнктивных объединений отрезков, взятых из прямого и встречного дерева Фенвика.
+
* Данная структура данных легко обобщается на случай многомерных массивов.
  
<br /> <br />
+
* Такое дерево Фенвика позволяет представить любой отрезок <tex>[L; R]</tex> в виде дизъюнктивных объединений отрезков, взятых из прямого и встречного дерева Фенвика.
  
 
== Применение ==
 
== Применение ==
  
Встречное дерево Фенвика применяется, когда нужно посчитать некоторую операцию на структуре без использования обратного элемента по этой операции. Например, перед нами стоит задача посчитать произведение матриц, не считая обратных. С помощью встречного дерева Фенвика можно разложить запрос произведения на отрезке на <tex>O(\log N)</tex> дизъюнктных отрезков, операция для которых уже посчитана, получается почти как в дереве отрезков.
+
Встречное дерево Фенвика применяется, когда нужно посчитать некоторую операцию на структуре без использования обратного элемента по этой операции. Например, перед нами стоит задача посчитать произведение. Используя дерева Фенвика, мы можем столкнуться с такой ситуацией: элемент <tex>a[i] = 0</tex>. Тогда, считая произведение на отрезке <tex>[l, r]</tex> (где <tex>l > i</tex>) как произведение на отрезке <tex>[0, r]</tex>, делённое на произведение на отрезке <tex>[0, l - 1]</tex>, мы получим неопределённое значение <tex>\dfrac{0}{0}</tex>, поэтому нужно использовать встречное дерево Фенвика. С его помощью можно разложить запрос произведения на отрезке на <tex>O(\log N)</tex> дизъюнктных отрезков, операция для которых уже посчитана, получается почти как в дереве отрезков.
 +
==См. также==
 +
* [[Дерево Фенвика]]
 +
 
 +
* [[Дерево отрезков. Построение |Дерево отрезков]]
 +
 
 +
== Источники информации ==
 +
* [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 Дерево Фенвика]
 

Текущая версия на 19:22, 4 сентября 2022

Определение:
Встречное дерево Фенвика (англ. 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]i + 2^{h(i)}[/math] можно считать по равносильной формуле [math] i \mid (i + 1) [/math]. Рассмотрим, что делают эти формулы с двоичной записью числа [math]i[/math]. Формула [math]i + 2^{h(i)}[/math] изменяет последний ноль на единицу. Аналогично работает и [math] i \mid (i + 1) [/math].


[math]i[/math] [math]\ldots 011 \ldots 1[/math]
[math]2^{h(i)}[/math] [math] 100 \ldots 0[/math]
[math]i + 2^{h(i)}[/math] [math]\ldots 111 \ldots 1[/math]


[math]i[/math] [math]\ldots 011 \ldots 1[/math]
[math]i + 1[/math] [math]\ldots 100 \ldots 0[/math]
[math]i \mid (i + 1)[/math] [math]\ldots 111 \ldots 1[/math]


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

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

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

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

Стоит отметить, что поддерево для [math](\dfrac{n}{2} + 1..n)[/math] получается "перевернутым" из-за того, что встречное дерево, по сути, идет от [math]n - 1[/math] до [math]1[/math] в обратном порядке.
[math]\triangleleft[/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]a[i] = 0[/math]. Тогда, считая произведение на отрезке [math][l, r][/math] (где [math]l \gt i[/math]) как произведение на отрезке [math][0, r][/math], делённое на произведение на отрезке [math][0, l - 1][/math], мы получим неопределённое значение [math]\dfrac{0}{0}[/math], поэтому нужно использовать встречное дерево Фенвика. С его помощью можно разложить запрос произведения на отрезке на [math]O(\log N)[/math] дизъюнктных отрезков, операция для которых уже посчитана, получается почти как в дереве отрезков.

См. также

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