title: Data structure for dealing with intervals
body: <p>I've spotted a question and couldn't solve it:</p>
  
  <p>[1 ... n^5] interval  was divided into n non-equal non-overlapped intervals.
  given these intervals and their names, can anyone give me a good data structure which can answer these following queries:</p>
  
  <ol>
  <li><p>input: integer x</p>
  
  <p>output: name of interval where x is located</p></li>
  <li><p>input: two integers x,y</p>
  
  <p>output: if they are located in two adjacent intervals, then  union intervals/ new interval holds the name of the left one.</p></li>
  <li><p>input: two integers x,y</p>
  
  <p>output: if they are located in the same interval [i...j], then split it into three: [i...x-1],[x....y-1],[y....j].</p></li>
  </ol>