Сегодня я слушал лекцию о ветвях деревьев (двоичные индексированные деревья), и учитель говорит, что это дерево является обобщением деревьев интервалов и сегментов, но мои реализации этих трех структур данных различны. Действительно ли это утверждение? и почему?Являются ли интервалы, сегменты, ветвящиеся деревья одинаковыми?
Я никогда не слышал binary indexed trees, называемый обобщением чего-либо. Это, конечно, не обобщение interval trees и segment trees. Я предлагаю вам следовать ссылкам, чтобы убедить себя в этом.
, чем это дерево является обобщением интервальных и сегментных деревьев
Если под «это дерево» ваш учитель имел в виду «бинарное дерево» индексированный, то он ошибается.
но мои реализации этих трех структур данных отличаются
Конечно, они разные, ваш учитель никогда не говорил, что они не должны быть. Он просто сказал, что один из них является обобщением другого (что неверно, но все же). В любом случае, реализации должны быть разными.
Что бы иметь такую же реализацию двоичная индексируется дерево и Фенвик дерево, потому что те являются то же самое.
Я видел статью topcoder, и многие запросы в BIT похожи на деревья интервалов. – Luiguis
Они могут быть похожими, но это не значит, что вы можете сказать, что одна структура данных происходит от другой. Узел в дереве интервалов содержит одну половину интервала, который выполняет его родительский узел, а узел в BIT имеет интервал, заданный двоичным представлением числа. – IVlad
Следующая классификация кажется разумной, хотя разные люди обязаны смешивать эти термины.
Фенвик дерево/Binary индексированного дереваlink
Тот, где вы используете один массив и операции на двоичном представлении для хранения префикса суммы (также называемые кумулятивными суммы). Элементы могут быть членами моноида.
Диапазон дереваlink
Семейство деревьев, где каждый узел представляет собой поддиапазон в заданном диапазоне, скажем, [0, N]. Используется для вычисления ассоциативных операций с интервалами.
Interval деревоlink
Деревья, на которых хранятся фактические интервалы. Чаще всего вы берете среднюю точку, сохраняете пересекающиеся интервалы в узле и повторяете процесс для интервалов слева и справа от точки.
Сегмент дереваlink
Подобно дереву диапазона, где листья элементарные интервалы в пространстве, возможно, непрерывного, а не дискретные и высшие узлы объединения элементарных интервалов. Используется для проверки включения точки.
Существует различие между утверждением, что «A является обобщением B» и «A является таким же, как B.» –