Как память массива дерева сегментов 2 * 2 ^ (ceil (log (n))) - 1?

Ответ 1

Что здесь происходит, если у вас есть массив из n элементов, тогда дерево сегментов будет иметь лист node для каждой из этих n записей. Таким образом, мы имеем (n) листовые узлы, а также (n-1) внутренние узлы.

Общее количество узлов = n + (n-1) = 2n-1 Теперь мы знаем его полное двоичное дерево и, следовательно, высота: ceil (Log2 (n)) +1

Итого №. узлов = 2 ^ 0 + 2 ^ 1 + 2 ^ 2 +... + 2 ^ ceil (Log2 (n))//которая является геометрической прогрессией, где 2 ^ я обозначает число узлов на уровне i.

Формула суммирования G.P. = a * (r ^ size - 1)/(r-1) где а = 2 ^ 0

Итого №. узлов = 1 * (2 ^ (ceil (Log2 (n)) + 1) -1)/(2-1)

= 2 * [2 ^ ceil (Log2 (n))] -1 (вам нужно пространство в массиве для каждого из внутренних, а также листовых узлов, которые являются этим числом в количестве), таким образом, это массив размер.

= O (4 * n) приблизительно...

Вы также можете так думать, это дерево сегментов:

    10
   /  \
  3    7
 /\    /\
1  2  3  4

Если выше вы - сегментное дерево, тогда массив массива сегментов будет: 10,3,7,1,2,3,4, то есть 0-й элемент будет хранить сумму 1-й и 2-й записей, 1-я запись будет хранить сумма 3, 4 и 2 будет хранить сумму 5-й и 6-й записи!

Кроме того, лучшее объяснение: если размер массива n равен 2, то мы имеем ровно n-1 внутренние узлы, суммируя до 2n-1. Но не всегда мы имеем n как мощность 2, поэтому нам нужна наименьшая степень n, которая больше, чем n. Это означает, что

int s=1;
for(; s<n; s<<=1);

Вы можете увидеть мой ответ здесь

Ответ 2

Как ни странно, я читал из того же источника, что и вопрос, когда я это понял. Я постараюсь ответить на все мои вопросы.

Давайте начнем с основной разницы в представлениях деревьев (только в контексте):

• Почти сценарий "Худший случай". Этот не полностью сбалансированный, и не очень весело перемещаться. Зачем? Потому что с разными входами могут генерироваться разные деревья, и, следовательно, время, затрачиваемое на траверс, не очень предсказуемо.

• Наш сценарий "Лучший случай". Этот полностью сбалансированный или полный, и всегда будет проходить предсказуемое количество времени. Более того, это дерево также лучше "взломано".

Теперь вернемся к нашему вопросу. [Обратитесь к первому изображению] Мы знаем, что для каждого массива n-input (числа зеленым цветом) будут n-1 внутренние узлы (цифры в синем). Поэтому должен быть выделен максимум 2n-1 node.

Но код здесь делает что-то наоборот. Почему и как?

• Что вы ожидаете: Вы ожидаете, что памяти, выделенной для узлов 2n-1, должно быть достаточно. Другими словами, это должно быть сделано:

  int *st = new int[2*n - 1];
  

  Предполагая, что остальная часть кода работает хорошо, это не очень хорошая идея. Это потому, что оно создает наше несбалансированное дерево, как в нашем первом случае. Такое дерево нелегко перемещаться и легко применять к решению проблем.

• Что действительно происходит: Мы добавляем/добавляем дополнительную память с значениями null или 0. Мы делаем это:

  int x = (int)(ceil(log2(n))); //Height of segment tree
  int max_size = 2*(int)pow(2, x) - 1; //Maximum size of segment tree
  int *st = new int[max_size];
  

  То есть мы выделяем достаточно места для создания сбалансированного полного дерева. Такое дерево легко перемещается (используя некоторые специальные модификации) и может быть применено к проблемам напрямую.

Как мы выделили достаточно памяти для case 2? Вот как:

• Мы знаем, что в нашем сбалансированном сегменте дерева есть как минимум три компонента:

  • n из нашего входного массива.
  • n-1, которые обязательно требуются.
  • Дополнительное пространство, которое нам нужно выделить для нашего дополнения.

• Мы также знаем, что сбалансированное дерево с листьями k будет иметь:

• Объединяя два, мы получаем желаемый результат:

  int x = (int)(ceil(log2(n))); //Height of segment tree
  int max_size = 2*(int)pow(2, x) - 1; //Maximum size of segment tree
  int *st = new int[max_size];
  

Trivia! Повышение 2 до уровня x выше, гарантирует, что мы получим ближайшее целое число потолков, которое:

• Больше или равно n (Число элементов в нашем массиве ввода).
• Совершенно и многократно делится на 2, чтобы получить полностью сбалансированное 2-арное (двоичное) дерево.

Ответ 3

Пусть размер входного массива равен n.
Все элементы входного массива будут листовыми узлами в дереве сегментов, поэтому число листовых узлов = n
Поскольку дерево сегментов является полным деревом, поэтому высота дерева сегментов h = ⌈ Log ₂ n ⌉ + 1
Максимальное количество узлов в двоичном дереве с высотой "h" составляет 2 ^h -1

So Количество узлов в дереве сегментов = 2 ^{⌈ Журнал ₂ n ⌉ + 1} -1
Равен до 2 * 2 ^{⌈ Log ₂ n ⌉} -1

Ответ 4

Дерево сегментов будет полным двоичным деревом, где все листья будут обозначать элемент в вашем входном массиве. И как упоминается здесь

Число узлов n в полном двоичном дереве, находится в наименее n = 2h + 1 и не более n = 2 ^ {h + 1} - 1, где h - высота дерева. И h = log_2n. Note - log_2n indicates log base 2

Вот код python для определения максимального количества узлов в дереве сегментов -

from math import pow, log, ceil
def initialize_seg_tree(input_arr):
        n = len(input_arr)
        height = ceil(log(n, 2))  

        # max_nodes = 2^(h+1) - 1, where h = log(n) // base 2
        seg_tree_size = int(pow(2, height + 1) - 1)
        seg_tree_arr = empty_1d_array(seg_tree_size)
        return seg_tree_arr

Ответ 5

вот несколько ссылок.. итеративная реализация для построения дерева сегментов размером 2 * n-1 из массива длины n (любое число) https://www.geeksforgeeks.org/segment-tree-efficient-implementation/ рекурсивная реализация для построения дерева сегментов размером 2 * n-1 из массива длины n (любое число) https://www.hackerearth.com/practice/notes/segment-tree-and-lazy-propagation/#c191521

итеративная реализация для построения дерева сегментов размером менее 4 * n из массива n (любое число) https://codeforces.com/blog/entry/18051