3

I need a data structure that can perform the following three queries in log(n) where n is the range of numbers.

  • insert(a,b) : Insert Interval [a,b].
  • count(x) : Count number of intervals that contain the point x.
  • remove(a,b) : Remove Interval [a,b] from the set of intervals.

I came across the interval trees and its implementation in C++ requires the use of Red Black Trees. I am trying to avoid making the tree from scratch, is there a way I can implement the c++ stl like <map> or <set> to perform these operations ?

EDIT I realised that since all I need is the count of the intervals that contain a point, I used a Binary Indexed Tree, its implementation is simple and performs the above queries in O(log(n)) time.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Kyuubi
  • 1,228
  • 3
  • 18
  • 32
  • Use The Boost Interval Container Library, see [here](http://stackoverflow.com/questions/5407814/c-interval-tree-implementation) – cpp Aug 05 '13 at 11:36
  • Boost ICL provides you with such data structures like interval_map and interval_set. – cpp Aug 05 '13 at 12:10
  • I am aware of those. But I cannot use external libraries. I have to make my own implementation. I was hoping to reduce code size by implementing the STL. – Kyuubi Aug 05 '13 at 12:16
  • 1
    If you have solved this problem, can you please post an answer to your own question and then accept it? That way, the question is actually marked as closed. – templatetypedef Nov 01 '13 at 02:59
  • There was no solution to this problem. I had to workaround it by using a combination of Segment Tree and Binary Indexed Tree. – Kyuubi Nov 02 '13 at 14:23

0 Answers0