title: How to adapt Fenwick tree to answer range minimum queries
body: <p><a href="https://en.wikipedia.org/wiki/Fenwick_tree" rel="noreferrer">Fenwick tree</a> is a data-structure that gives an efficient way to answer to main queries:</p>
  
  <ul>
  <li>add an element to a particular index of an array <code>update(index, value)</code></li>
  <li>find sum of elements from 1 to N <code>find(n)</code></li>
  </ul>
  
  <p>both operations are done in <code>O(log(n))</code> time and I understand the <a href="https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/" rel="noreferrer">logic and implementation</a>. It is not hard to implement a bunch of other operations like find a sum from N to M.</p>
  
  <p>I wanted to understand how to adapt Fenwick tree for RMQ. It is obvious to change Fenwick tree for first two operations. But I am failing to figure out how to find minimum on the range from N to M.</p>
  
  <p>After searching for solutions majority of people think that this is not possible and a small minority claims that it actually can be done (<a href="http://habrahabr.ru/post/160099/" rel="noreferrer">approach1</a>, <a href="https://stackoverflow.com/q/17157093/1090562">approach2</a>).</p>
  
  <p>The first approach (written in Russian, based on my google translate has 0 explanation and only two functions) relies on three arrays (initial, left and right) upon my testing was not working correctly for all possible test cases.</p>
  
  <p>The second approach requires only one array and based on the claims runs in <code>O(log^2(n))</code> and also has close to no explanation of why and how should it work. I have not tried to test it.</p>
  
  <hr>
  
  <p>In light of controversial claims, I wanted to find out whether it is possible to augment Fenwick tree to answer <code>update(index, value)</code> and <code>findMin(from, to)</code>.</p>
  
  <p>If it is possible, I would be happy to hear how it works.</p>