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

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Встречное дерево Фенвикадерево Фенвика, в котором над каждым столбцом идет столбец такой же высоты, вычисляемый по формуле [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]

И если оригинальное дерево выглядело подобным образом:

По горизонтали - содержимое массива T,
по вертикали - содержимое массива A

То встречное дерево Фенвика выглядит вот так: