title: Data Structure for Storing Ranges
body: <p>I am wondering if anyone knows of a data structure which would efficiently handle the following situation:</p>
  
  <p>The data structure should store several, possibly overlapping, variable length ranges on some continuous timescale.</p>
  
  <ul>
  <li><p>For example, you might add the ranges <code>a:[0,3], b:[4,7], c:[0,9]</code>.</p></li>
  <li><p>Insertion time does not need to be particularly efficient.</p></li>
  </ul>
  
  <p>Retrievals would take a range as a parameter, and return all the ranges in the set that overlap with the range, for example:</p>
  
  <ul>
  <li><p><code>Get(1,2)</code> would return a and c.  <code>Get(6,7)</code> would return b and c.  <code>Get(2,6)</code> would return all three.</p></li>
  <li><p>Retrievals need to be as efficient as possible.</p></li>
  </ul>