title: Order statistic on intervals
body: <p>Given an array of numbers <code>a[0], a[1], ..., a[n-1]</code>, we get queries of the kind:</p>
  
  <p>output <code>k</code>-th largest number in the range <code>a[i], a[i+1], ..., a[j]</code></p>
  
  <p>Can these queries be answered in polylogarithmic time (in <code>n</code>) per query? If not, is it possible to average results and still get a good amortized complexity?</p>
  
  <p><strong>EDIT</strong>: this can be solved using persistent segment trees 
  <a href="http://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/" rel="nofollow">http://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/</a></p>