2
Я обнаружил, как описано в этой статье on HackerEarth, что дерево отрезков могут быть реализованы с использованием массивов, где дочерние элементы узла, расположенного в массиве индекса п находятся на индексы 2n и 2n + 1.Сегмент требование дерева пространство
Также в нем говорится, что для хранения п элементов в моем дереве сегмента, мне нужно 2n + 1 узлы.
Еще недавно, когда я решил несколько проблем, связанных с деревьями сегментов, иногда мой код дал ошибку времени выполнения, которая была решена, когда я изменил размер массива для хранения дерева сегментов до 4 x (размер массива, который будет храниться в дереве сегментов). Как я могу быть уверенным, что для дерева сегментов требуется 4-мерный массив для n элементов.
Обратите внимание, что «левый ребенок (N) = 2N; система right child (N) = 2N + 1' работает для простого двоичного дерева, но только при запуске с N = 1, а не при N = 0. Вы можете исправить это, так что это работает от N = 0, но это несколько разные формулы (LC (N) = 2N + 1; RC (N) = 2N + 2). Я не понимаю, зачем вам нужно 2N + 1 узлов для хранения дерева с N элементами; N достаточно, если вы можете выделить так, чтобы первый элемент был проиндексирован в 1, и N + 1 является достаточным, если вы выделяете из 0, но используете только 1. Из него не раздувается в 2 раза. _ [... продолжение ...] _ –
_ [... продолжение ...] _ В статье могут быть причины - это хранение диапазонов, и если каждый диапазон занимает две ячейки, вам нужно удвоить; но статья длинная, и ваш вопрос не очень хорошо подходит для SO. Вы должны продемонстрировать, почему вам нужно использовать 4N с некоторым кодом, и мы можем проверить его. Или что-то. –
Это подходит для любого другого форума StackExchange? – brijs