Блог

пример:

 range - 0  1  2  3  4  5  6  7  8  9  10
values- 81 21 55 23 45 78 98 69 42 10 33
 

Если структура данных представляет собой массив, то временная сложность O(n) равна, где n — разница между диапазоном запросов.

Могут ли деревья предоставлять O(log n) ? или есть какая-либо лучшая структура данных для моделирования этого?

Некоторые характеристики данных.

1. Непрерывные значения диапазона без пропущенных данных
2. Может иметь отрицательные значения. Таким образом, запрос также может составлять от -10 до 10
3. Сложность пространства можно игнорировать, если можно достичь лучшей временной сложности

Спасибо

Деревья сегментов — это те, которые вы хотите использовать. Хотя 4*n для построения дерева сегментов требуется около (при использовании полностью двоичного дерева) узлов, оно более эффективно для запросов. Запрос в диапазоне будет иметь порядок log(n) или высоту дерева. Узнайте больше о деревьях сегментов здесь .