419
правок
Изменения
Нет описания правки
== Любой отрезок в виде дизъюнктивных объединений отрезков ==
Докажем, что можно представить любой отрезок в виде дизъюнктивных объединений <tex>O(\log N)</tex> отрезков, взятых из прямого и встречного дерева Фенвика.
Представим встречное дерево Фенвика <tex>2^n</tex> на <tex>2^n</tex> и посмотрим на него, как на дерево отрезков.
В нем существует отрезок длины 1..<tex>2^n</tex>. Оставшуюся часть можно разбить на 2 поддерева, т.е. отрезок <tex>(1.. То есть n)</tex> разбивается на подотрезки <tex>(1..n/2)</tex>, <tex>(n/2+1..n)</tex>. В итоге получается структура обычного дерева отрезков, для которого известно указанное выше утверждение. Стоит отметить, что
== Свойства ==
