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

Автор PeterNaut, 11 лет назад, По-английски

Which task needs a straight forward interval tree for its solution? With interval tree I mean the data structure that stores a set of lines and has queries asking which lines touch a certain point x? With no neccesity for updates.

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

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

I think in the offline setting mostly relevant in competitions, most of these tasks can be solved with segment tree as well, if you do a coordinate compression beforehand. That might be why you don't find an example where a "real" interval tree is actually needed. Also, if you don't have updates you can just use a sorted array of intervals.