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

Ссылка: http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/. Это цитируемый текст:

Начнем с отрезка arr [0. . . п-1]. И каждый раз мы делим текущий сегмент на две половины (если он еще не стал сегментом длины 1), а затем вызываем одну и ту же процедуру на обеих половинах, и для каждого такого сегмента мы сохраняем сумму в соответствующем узле. Будут заполнены все уровни построенного дерева сегментов, кроме последнего уровня. Кроме того, дерево будет полным двоичным деревом, потому что мы всегда делим сегменты на две половины на каждом уровне. Поскольку построенное дерево всегда является полным двоичным деревом с n листьями, будет n-1 внутренних узлов. Таким образом, общее количество узлов будет 2n - 1. Высота дерева сегментов будет ceil [log (n)]. Поскольку дерево представлено с использованием массива и необходимо поддерживать связь между родительским и дочерним индексами, размер памяти, выделенной для дерева сегментов, будет $\ (2 * 2 ^ {\ left \ lceil \ log _ {2} n \ right \ rceil} -1 \)$ .

Каким образом выделяется память (последняя строка в приведенном выше параграфе)? Как родительский и дочерний индексы хранятся в коде, если он правильный? Пожалуйста, объясните причину этого. Если это неверно, то каково правильное значение?

dauntless 12.02.2015 источник

Ответы (6)

arrow_upward
37
arrow_downward

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

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

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

Формула суммирования Г. = a * (r ^ size - 1) / (r-1), где a = 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, т.е. 0-й элемент будет хранить сумму 1-й и 2-й записи, 1-я запись будет хранить сумму 3-й, 4-й и 2-й будут хранить сумму 5-го и 6-го входа !!

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

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

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

user3004790 13.02.2015

comment

Нет противоречия? Как и вначале, было упомянуто, что общее количество нет. узлов равно 2 * (n-1). Далее говорится, что общее количество узлов нет. узлов составляет 2 * 2 ceil (Log2 (n)) -1 (я понял объяснение этого). Но разве мы не выделяем дополнительную память, рассматривая 2 * 2 ceil (Log2 (n)) -1, когда n не является степенью 2. Правильно ли предположить, что для дерева сегментов требуется размер массива 2 * n-1 для всех? n, поскольку 2 * n-1 - это общее количество. узлов для полного двоичного дерева, и это то, что требуется в дереве сегментов. Это правильно? Если нет, то какова цель выделения 2 * 2 ceil (Log2 (n)) -1. - dauntless; 15.02.2015

comment

в последней строке, я думаю, у вас опечатка. это должно быть так, что нам в основном нужна наименьшая степень 2 (не n), которая больше n - shshnk; 17.08.2016

arrow_upward
22
arrow_downward

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

Начнем с основного различия в представлениях деревьев (только в контексте):

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

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

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

Ожидаемые результаты. Предполагается, что памяти, выделенной для узлов 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];

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

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

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

n numbers from our input array.

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];

Интересный факт! Возведение 2 в степень x выше гарантирует, что мы получим ближайшее целое число потолка:

Больше или равно n (количество элементов в нашем входном массиве).

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

Quirk 21.02.2015

comment

ознакомьтесь с leetcode.com/problems/range-sum-query -mutable / solution / и найдите 1. Build segment tree., он не использует заполнение. Он использует только массив 2 * n для представления двоичного дерева. (он как-то всегда превращал его в полноценное дерево) И это кажется правильным. Но это нигде не объясняется. - Weishi Z; 21.09.2017

comment

@WeishiZeng Такое дерево имеет очень неинтуитивные свойства. Предполагается, что элементы входного массива станут листьями, а родительский элемент каждого узла должен быть суммой двух его дочерних значений. Но ни то, ни другое не обязательно так, если n не является степенью двойки (скажем, если n = 5). - mic; 17.06.2020

comment

@mic Если n = 5, элементы входного массива все еще остаются листьями, но некоторые из них не находятся на нижнем уровне. В частности, arr[0:2] находятся на последнем 2-м уровне, а arr[3:4] - на нижнем уровне. Неявное дерево будет [15 10 5 9 1 2 3 4 5]. Это не имеет значения, потому что у нас все еще есть tree[i] = tree[2i] + tree[2i+1] (на основе 1). - Zhiyong; 30.06.2021

arrow_upward
6
arrow_downward

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

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

vijay yadav    09.08.2017

arrow_upward
2
arrow_downward

Как определить требуемый размер массива дерева сегментов?

Дерево сегментов - это полное двоичное дерево. Но мы представляем его в виде массива. Помните, что для представления любого двоичного дерева высоты h в виде массива потребуется пространство, эквивалентное идеальному двоичному дереву высоты h.

[ Maximum possible Height of a Binary Tree with n nodes] (h) = Ceil[ Log_2 (n+1) ] - 1 [ No. of nodes in a Perfect Binary Tree of height h] (n) = 2 ^ (h+1) - 1

Данный массив будет представлять собой листья дерева сегментов. Так. размер данного массива будет no. листьев.

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

Пример:

* Say, if there are 4 leaves in a Binary Tree, then the maximum no. of interior nodes in the Binary Tree will be N-1. So, 3. - Then the total number of nodes in the Binary Tree = No. of interior nodes + No. of leaves. So, 4+3 = 7. - The max possible height of this Binary Tree will be 2. Formula: Maximum possible Height of a Binary Tree (h) = Ceil[ Log_2 (n+1) ] - 1 . - Remember, the total space required in the Segment Tree Array will be nothing but the total no. of nodes of the Perfect Binary Tree at this height. - So, the total no. of nodes of the Perfect Binary Tree at this height is (n) = 7. Formula: No. of nodes in a Perfect Binary Tree (n) = 2 ^ (h+1) - 1. - Thus the Segment Tree Array should also be of the size 7. * But if there is one more leaf, say 5 and remember that this leaf can be anywhere between the beginning of the level till the end of the level. - Then the total number of nodes in the Binary Tree = No. of interior nodes + No. of leaves. So, 5+4 = 9. - The max possible height of this Binary Tree will be 3. Maximum possible Height of a Binary Tree (h) = Ceil[ Log_2 (n+1) ] - 1 . - Remember, the total space required in the Segment Tree Array will be nothing but the total no. of nodes of the Perfect Binary Tree at this height. - So, the total no. of nodes of the Perfect Binary Tree at this height is (n) = 15. Formula: No. of nodes in a Perfect Binary Tree (n) = 2 ^ (h+1) - 1. - Thus the Segment Tree Array should also be of the size 15.

Говоря в целом,

* Say, if there are N leaves in a Binary Tree, then the maximum no. of interior nodes in the Binary Tree will be N-1. - Then the total number of nodes in the Binary Tree = No. of interior nodes + No. of leaves. So, 2N-1. - The max possible height of this Binary Tree will be Ceil[ Log_2 (2N) ] - 1. Formula: Maximum possible Height of a Binary Tree (h) = Ceil[ Log_2 (n+1) ] - 1 . - Remember, the total space required in the Segment Tree Array will be nothing but the total no. of nodes of the Perfect Binary Tree at this height. - So, the total no. of nodes of the Perfect Binary Tree at this height is (n) = 2 ^ (Ceil[ Log_2 (2N) ] ) - 1. Formula: No. of nodes in a Perfect Binary Tree (n) = 2 ^ (h+1) - 1. - Thus the Segment Tree Array should also be of the size 2 ^ (Ceil[ Log_2 (2N) ] ) - 1. - This can also be written as [2*2 ^ (Ceil[ Log_2 (N) ] )] - 1.

Таким образом, Размер массива дерева сегментов = [2 * 2 ^ (Ceil [Log_2 (N)])] - 1

Размер массива дерева сегментов просто 4N (приблизительно).

Пример:

Best Case Scenario: (No. of leaves (N) is a power of 2) Say, the no. of leaves , N is 4. Since N is a power of 2, the Segment tree will be a Perfect Binary Tree. So the total no of nodes will be N+N-1 = 2N-1 = 7 So, the size of the Segment Tree Array = 7. Not the Best Case Scenario: (No. of leaves (N) is not a power of 2) If the no. of leaves , N is 5. Since N is not a power of 2, the Segment Tree will need one more entire level to accommodate the extra 1 leaf, as this leaf can be anywhere from the beginning of the level till the end. We know that in a Perfect binary tree, the no of nodes in every new level, will be equal to No. of all the previous level nodes + 1. Now, total no. of nodes in the segment tree upto the previous power of 2. i.e. 8 is 8+7 = 15 So, the no. of nodes in the new level will be 15+1 = 16 So, the size of the Segment Tree Array = 15 + 16 = 31.

Говоря в целом,

Best Case Scenario: (No. of leaves (N) is a power of 2) Since N is a power of 2, the Segment tree will be a Perfect Binary Tree. So the total no of nodes will be N+N-1 = 2N-1 So, the size of the Segment Tree Array = 2N-1 Not the Best Case Scenario: (No. of leaves (N) is not a power of 2) Since N is not a power of 2, the Segment Tree will need one more entire level to accommodate the extra leaves, as this leaf can be anywhere from the beginning of the level till the end. We know that in a Perfect binary tree, the no of nodes in every new level, will be equal to No. of all the previous level nodes + 1. Now, total no. of nodes in the segment tree upto the previous power of 2 will be 2N-1. So, the no. of nodes in the new level will be 2N-1+1 = 2N So, the size of the Segment Tree Array = 2N + 2N - 1 = 4N - 1 = 4N (approx.)

Таким образом, Размер массива дерева сегментов = 4N (приблизительно)

Vishnu Vivek    15.12.2020

arrow_upward
0
arrow_downward

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

Количество узлов 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

Suyash Soni    25.12.2017

arrow_upward
0
arrow_downward

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

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

Rithik Singh    25.07.2019

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

Ответы (6)

Как определить требуемый размер массива дерева сегментов?

Пример:

Размер массива дерева сегментов просто 4N (приблизительно).

Пример:

Вопросы по теме