title: Efficient data structures for disjoint integer intervals
body: <p>I have a set of disjoint integer intervals and want to check whether a given integer lies in one of these intervals. Of course, this can be achieved by means of a binary search in logarithmic time. However, the vast majority of the queries return <code>false</code>, i.e., only very few integers lie in any interval. To speedup the application, I'm looking for a probabilistic, <em>constant-time</em> algorithm (some sort of hash function) that tells me whether a given integer is definitely not or maybe in an interval. Here is a sketch of the intended algorithm, where <code>magic_data_structure</code> is initialized with the intervals stored in <code>tree</code>:</p>
  
  <pre><code>x = some_integer;
  if(!magic_data_structure.find(x))
    return false; // definitely not in any interval
  return tree.find(x); // binary search on tree
  </code></pre>
  
  <p>Any ideas or hints for literature? Thank you very much in advance for your help!</p>
  
  <p>P.S.: Does anybody know improvements of interval trees for <em>non-overlapping</em> intervals which (unlike the ones described above) may include other intervals?</p>