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