419
правок
Изменения
→Любой отрезок в виде дизъюнктивных объединений отрезков, взятых из прямого и встречного дерева Фенвика
Вспомним, что <tex>h(i)</tex> возвращает количество единиц в двоичной записи числа <tex>i</tex>, а каждый столбец прямого дерева Фенвика вычисляется по формуле <tex>F(i) = \sum_{j=i-2^{h(i)}+1}^i a[j]</tex>
== Любой отрезок в виде дизъюнктивных объединений отрезков== Представим встречное дерево Фенвика <tex>2^n</tex> на <tex>2^n</tex> и посмотрим на него, взятых из прямого и встречного как на дерево отрезков. В нем существует отрезок длины 1..<tex>2^n</tex>. Оставшуюся часть можно разбить на 2 поддерева. То есть получается структура обычного дерева Фенвика ==отрезков, для которого известно указанное выше утверждение.
== Свойства ==
