Блог пользователя Domonion

Автор Domonion, 10 лет назад, По-русски

Смотрел ШАД Яндекс. Там в видео про геометрический поиск рассказывали про структуру данных интервальное дерево(interval tree). Позволяет решать следующую задачу за O(Log2N + k(размер ответа)): Дано множество отрезков и множество запросов. Каждый запрос характеризуется точкой. Для каждого запроса необходимо определить множество отрезков, которые содержат в себе эту точку. Я не понял, как оно строится. На Wiki тоже ничего не понял. Кто-нибудь знает что-нибудь о ней

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

http://e-maxx.ru/algo/segment_tree. Здесь очень хорошо объясняют

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится