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

Определение:

Встречное дерево Фенвика — дерево Фенвика, в котором над каждым столбцом идет столбец такой же высоты, вычисляемый по формуле [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 в виде дизъюнктивных объединений отрезков, взятых из прямого и встречного дерева Фенвика.