Какова лучшая структура данных для универсальной пошаговой функции?

Question

Мне нужно реализовать пошаговую функцию (то есть кусочно-постоянную). Есть несколько требований, которые он должен будет иметь.

1. Его необходимо будет неоднократно оценивать в случайных местах, а затем оценивать последовательно в течение интервала.
2. Это должно быть легко обновлено, то есть добавление увеличения / уменьшения за интервал.

Итак, мой вопрос: какова лучшая структура данных для такого рода вещей? Я думал, что из-за природы произвольного доступа наиболее вероятно двоичное дерево, но я надеюсь, что я что-то не упустил Также есть хорошая реализация для C ++.

Answer 1

Да, поскольку интервалы не могут перекрываться, двоичное дерево является правильной структурой данных. Если вам не нужны быстрые обновления, это может быть так же просто, как отсортированная последовательность конечных точек интервала; запрос значения функции в определенном месте можно выполнить, например, с помощью одного из методов двоичного поиска STL std::lower_bound или std::upper_bound, оценивая диапазон с помощью двух поисков. Тем не менее, для быстрых обновлений лучше всего подходит самобалансирующееся двоичное дерево.

Стандартная библиотека определяет контейнер с древовидным доступом: std::map (хотя это не обязательно для реализации с использованием двоичного дерева, обычно это так).

для полноты следует отметить, что библиотека Boost ICL имеет interval_map, std::map -подобный контейнер, который использует интервалы в качестве ключей и с агрегированием при вставке семантика.