interval range tree datastructure c++

Question

I have a requirement where I have to update the color of a graphical frontend based on some attribute value.The attribute value has different ranges ....say -30 to -45, -60 to -80 and so on.....So, I needed a datastaructure where I could store these ranges(prefill them)....And When I do determine the point , I would like to know the range in which this point falls either in O(1) Time or O(logN) time....So, My Query would consist of a single point and the output should be a unique range containing that point...

I am confused between range trees and segment trees....i want to build the tree on top of c++ stl map.

Answer 1

What you need is called interval tree. http://en.wikipedia.org/wiki/Interval_tree. Unfortunately you can't use std::set<> to get O(log N) insert, remove and query, because tree node needs to contain additional data. You can read about them here http://syedwaqarahmad.webs.com/documents/t.cormen-_introduction_to_algorithms_3rd_edition.pdf chapter 14.3.

Instead you can use boost. It has interval container library.

http://www.boost.org/doc/libs/1_46_1/libs/icl/doc/html/index.html