Память дерева сегментов

O (4 * N) = O (2 * N) = O (N), потому что O-обозначение абстрагирует постоянные факторы.

обозначение Big O в Википедии

Итак, что вы подразумеваете под «использовать ровно 2 * N-1 памяти»? Du вы имеете в виду 2 * N-1 байт? Если вы имеете в виду O (2 * N-1), то это то же самое, что и O (4 * N), O (2 * N) и O (N).

Согласно обозначению Big O, O(4*N) = O(2*N-1 ) = О(N). Любая стандартная реализация дерева сегментов использует линейную память.

Что касается вашего вопроса, рассмотрите массив a[0...n-1] в качестве входных данных. Рассмотрим n = 10. Когда вы строите дерево сегментов, оно будет выглядеть примерно так:

Количество узлов, используемых для построения = 2*n - 1 = 19. Таким образом, теоретически требуется только 19 узлов!

Но мы реализуем дерево сегментов, используя структуру данных array. Здесь каждый узел будет соответствовать некоторому индексу в array. В дереве сегментов для узла с индексом x индекс левого дочернего элемента = 2*x, индекс правого дочернего элемента = 2*x+1.

Итак, если я начну с массива с одним индексом, индекс [0, 9] = 1, [5] = 24, [6] = 25. Итак, в этом случае вам как минимум нужен индекс до 25. В худшем случае вам понадобится индекс 31 в случае полностью выросшего дерева сегментов (n=16).

Таким образом, мы поддерживаем array размером 2*(next power of 2 >= n)

Большинство людей знакомы с реализацией безопасной 4N выделенной памяти, которая является верхней границей для построения дерева сегментов на массиве размером N или версии ООП. Чтобы узнать об этом, прочитайте здесь. Это очень хороший источник, содержащий много информации о деревьях сегментов.

Теперь перейдем к использованию памяти 2N. Посмотрите здесь, здесь, а также:

Реализация с эффективным использованием памяти (из здесь)

Большинство людей используют реализацию из предыдущего раздела. Если вы посмотрите на массив t, то увидите, что он соответствует нумерации узлов дерева в порядке обхода BFS (обход по уровню). Используя этот обход, дочерними элементами вершины v являются 2v и 2v+1 соответственно. Однако, если n не является степенью двойки, этот метод пропустит некоторые индексы и оставит некоторые части массива t неиспользованными. Потребление памяти ограничено 4n, даже несмотря на то, что дерево сегментов массива из n элементов требует только 2n−1 вершин. Однако его можно уменьшить. Перенумеруем вершины дерева в порядке обхода эйлерова тура (pre-order traversal) и запишем все эти вершины рядом друг с другом.

Возьмем вершину с номером v, и пусть она отвечает за отрезок [l,r], и пусть mid=l+r2. Очевидно, что левый потомок будет иметь индекс v+1. Левый потомок отвечает за отрезок [l,mid], т.е. всего в левом дочернем поддереве будет 2∗(mid−l+1)−1 вершин. Таким образом, мы можем вычислить индекс правого потомка v. Индекс будет v+2∗(mid-l+1). Такой нумерацией мы добиваемся уменьшения необходимой памяти до 2n.

Вы можете динамически добавлять узлы в дерево. Тогда узлы, которые вы не используете, просто не будут существовать и не будут тратить память.