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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 4: Строка 4:
 
}}
 
}}
  
[[Файл:Originalbit.png|thumb|300px|Оригинальное дерево Фенвика]]
+
[[Файл:Originalbit.png|thumb|300px|Прямое дерево Фенвика]]
 
[[Файл:Vstbit.png|thumb|300px|Встречное дерево Фенвика]]
 
[[Файл:Vstbit.png|thumb|300px|Встречное дерево Фенвика]]
  
Вспомним, что <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>
 +
 
 +
С помощью встречного дерева Фенвика можно представить любой отрезок от i до j в виде дизъюнктивных объединений отрезков, взятых из прямого и встречного дерева Фенвика.

Версия 05:47, 2 мая 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]

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