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.
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