title: Data structure for range query
body: <p>I was recently asked a coding question on the below problem.
  I have some solution to this problem but I am not very sure if those are most efficient.</p>
  
  <hr>
  
  <p>Problem:</p>
  
  <p>Write a program to track set of text ranges. Start point and end point will be string.</p>
  
  <pre><code>Text range example : [AbA-Ef]
   Aa would fall before this range
   AB would fall inside this range
   etc.
  </code></pre>
  
  <p>String comparison would be like  'A' &lt; 'a' &lt; 'B' &lt; 'b' ... 'Z' &lt; 'z'</p>
  
  <p>We need to support following operations on this range</p>
  
  <ul>
  <li><strong>Add range</strong> - this should merge the ranges if applicable</li>
  <li><strong>Delete range</strong> - this deletes range from tracked ranges and recompute the ranges</li>
  <li><strong>Query range</strong> - Given a character, function should return whether it is part of any of tracked ranges or not.</li>
  </ul>
  
  <p>Note that tracked ranges can be dis-continuous.</p>
  
  <hr>
  
  <p>My solutions:</p>
  
  <p>I came up with two approaches.</p>
  
  <ol>
  <li>Store ranges as doubly linked list or</li>
  <li>Store ranges as some sort of balanced tree with leaf node having actual data and they are inter-connected as linked list.</li>
  </ol>
  
  <p>Do you think that this solution are good enough or you can think of any better way of doing this so that those three API gives your best performance ?</p>