Встречное дерево Фенвика — различия между версиями
Proshev (обсуждение | вклад) (→Свойства) |
Proshev (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
}} | }} | ||
| − | Вспомним, что <tex>h(i)</tex> возвращает количество единиц в двоичной записи числа <tex>i</tex>, а каждый столбец прямого | + | Вспомним, что <tex>h(i)</tex> возвращает количество единиц в двоичной записи числа <tex>i</tex>, а каждый столбец прямого дерева Фенвика вычисляется по формуле <tex>F(i) = \sum_{j=i-2^{h(i)}+1}^i a[j]</tex> |
== Свойства == | == Свойства == | ||
| Строка 15: | Строка 15: | ||
Встречное дерево Фенвика - это структура данных, дерево на массиве, обладающее следующими свойствами: | Встречное дерево Фенвика - это структура данных, дерево на массиве, обладающее следующими свойствами: | ||
| − | 1) позволяет вычислять значение некоторой | + | 1) позволяет вычислять значение некоторой операции <tex>G</tex> на любом отрезке <tex>[L; R]</tex> за время <tex>O(\log N)</tex>; |
2) позволяет изменять значение любого элемента за <tex>O(\log N)</tex>; | 2) позволяет изменять значение любого элемента за <tex>O(\log N)</tex>; | ||
| Строка 29: | Строка 29: | ||
== Применение == | == Применение == | ||
| − | + | Встречное дерево Фенвика применяется, когда нужно посчитать некоторую операцию на структуре без использования обратного элемента по этой операции. Например, перед нами стоит задача посчитать произведение матриц, не считая обратных. С помощью встречного дерева Фенвика можно разложить запрос произведения на отрезке на <tex>O(\log N)</tex> дизъюнктных отрезков, операция для которых уже посчитана, получается почти как в дереве отрезков. | |
== Ссылки == | == Ссылки == | ||
[http://e-maxx.ru/algo/fenwick_tree Дерево Фенвика] | [http://e-maxx.ru/algo/fenwick_tree Дерево Фенвика] | ||
Версия 06:00, 24 мая 2011
| Определение: |
| Встречное дерево Фенвика — дерево Фенвика, в котором над каждым столбцом идет столбец такой же высоты, вычисляемый по формуле . |
Вспомним, что возвращает количество единиц в двоичной записи числа , а каждый столбец прямого дерева Фенвика вычисляется по формуле
Свойства
Встречное дерево Фенвика - это структура данных, дерево на массиве, обладающее следующими свойствами:
1) позволяет вычислять значение некоторой операции на любом отрезке за время ;
2) позволяет изменять значение любого элемента за ;
3) требует памяти, а точнее, ровно столько же, сколько и массив из элементов;
4) легко обобщается на случай многомерных массивов.
5) позволяет представить любой отрезок в виде дизъюнктивных объединений отрезков, взятых из прямого и встречного дерева Фенвика.
Применение
Встречное дерево Фенвика применяется, когда нужно посчитать некоторую операцию на структуре без использования обратного элемента по этой операции. Например, перед нами стоит задача посчитать произведение матриц, не считая обратных. С помощью встречного дерева Фенвика можно разложить запрос произведения на отрезке на дизъюнктных отрезков, операция для которых уже посчитана, получается почти как в дереве отрезков.
