419
правок
Изменения
→Любой отрезок в виде дизъюнктивных объединений O(\log N) отрезков
Вспомним, что <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 .. 2^n</tex>. Оставшуюся часть можно разбить на 2 поддерева, т.е. отрезок <tex>(1 .. n)</tex> разбивается на подотрезки <tex>(1 .. n/2)</tex>, <tex>(n/2+1 .. n)</tex>. В итоге получается структура обычного дерева отрезков, для которого известно указанное выше утверждение.
Стоит отметить, чтоподдерево для <tex>(n/2+1..n)</tex> получается "перевернутым" из-за того, что встречное дерево, по сути, идет от <tex>n-1</tex> до <tex>1</tex> в обратном порядке.
== Свойства ==
