0
$\begingroup$

I need to store a list of sequential intervals. So for example I would to say:

  • {0-5} = a
  • {6} = b
  • {7-10} = c

and so on. I need to add and remove items from this list: .insert(d,{1,3})

will make our array:

  • {0} = a
  • {1-3} = d
  • {4-5} = a
  • {6} = b
  • {7-10} = c

Morehover you may need to check what items cover a range: .itemsIn({6,8}) will return b,c.

I can keep an array with pointers to the same object instance for each value in a range but I suppose I can do a better job. Interval tree?

$\endgroup$
1
  • 1
    $\begingroup$ I'm a little confused. It sounds like you already know of an answer (an interval tree). So what is your question? Is there some reason you've rejected that solution? Please make sure to tell us your requirements, what research you've done and what you've found so far, and what possible approaches you've considered and why you've rejected them; see cs.stackexchange.com/help/how-to-ask. $\endgroup$ – D.W. Feb 15 '18 at 17:49
1
$\begingroup$

If every interval begins immediately after the previous one ends, then you only need to store the start point of each interval (and the endpoint of the very last interval), which you can do with a self-balancing binary search tree. Inserting and deleting intervals is then $O(\log n)$-time, and identifying the intervals overlapping a query interval is $O(\log n + k)$-time, if the answer includes $k$ intervals.

$\endgroup$
0
$\begingroup$

Take a look at: Richard Bonichon and Pascal, Cuoq, A Mergeable Interval Map link, 2010. I've spent a bit of time trying to find the original journal where this was published, but this link is the most stable one.

I cannot say that I followed all of the proofs and logic in that paper, but I understood enough to realize that it wasn't what I was looking for, but I think it is meant to solve your range query.

The solution data structure should, for instance, be able to answer queries such as finding all bindings that intersect a given interval. Being able to do this is necessary for lookups, but also at the time of adding a new binding, in order to maintain the invariant that the intervals in the map are disjoint.

The basic idea is to enforce a "covering" ordering logic on the nodes of a tree:

In Patricia trees, there is a static hi- erarchy for deciding which node goes above the other, and this static hierarchy ensures trees are balanced or almost balanced without any re-balancing operations. In the case of our data structure, we similarly define a static ordering on intervals that tells which node must be placed above the others. Intuitively, the interval containing the multiple of the largest power of two is put at the top. Like the ordering in Patricia trees, this ordering has the bounded chain length property...

I also recommend understanding Okasaki's Fast Mergeable Integer Maps first.

$\endgroup$
1
  • 1
    $\begingroup$ Could you give a brief summary of what these do? A full citation to the paper (title, publication details, etc.) would also be useful, in case the link breaks. $\endgroup$ – David Richerby May 17 '18 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.