алгоритм — STL для дерева сегментов в переполнении стека
Есть ли STL для дерева сегментов?
В конкурентном программировании на кодирование дерева сегментов уходит много времени. Интересно, есть ли STL для этого, чтобы можно было сэкономить много времени.
Решение
Я предполагаю, что под «сегментным деревом» вы на самом деле имеете в виду ареал дерева, которая чаще используется в соревнованиях по программированию, чем более специализированная структура для хранения набора интервалов.
В стандартной библиотеке C ++ такого контейнера нет, но если вы участвуете в соревнованиях ACM, вы можете написать свой собственный и просто скопировать его по мере необходимости. Вы можете найти мою собственную реализацию Вот (включая ленивое распространение), но если вы будете искать в Интернете, вы можете найти более общую версию.
В приложениях, где вам нужна сумма вместо минимума или максимума, вы можете использовать двоичное индексированное дерево вместо дерева сегментов, которое быстрее, использует меньше памяти, а также легче кодируется (около дюжины строк или меньше).
Другие решения
В C ++ нет STL для дерева сегментов. Тем не менее, вы можете проверить Boost Library под названием Интервальная контейнерная библиотека (ICL) который должен удовлетворить ваши требования.