PeterNaut's blog

Task with Interval Trees (not segment trees)
By PeterNaut, 11 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply