I know how a BIT works. But I was wondering if a BIT can be used to find the minimum/maximum element in the complete range, or more specifically, to find the minimum (or maximum) value after all the update processes have been completed. Now, I know that this can very well be achieved using Segment Trees, but is it possible to do the same using a BIT?

I know the obvious way of traversing the complete BIT and calculating the value at each index. I am looking for a more efficient/optimized way.

  • 3
    $\begingroup$ Do you have a reference to a good description of Binary Indexed Trees? (Not code, please: a description of the concept and algorithm.) In particular, how are tree elements ordered? And what do you mean by a "complete range" and "the update processes"? $\endgroup$
    – D.W.
    Nov 1, 2013 at 20:30
  • $\begingroup$ Do you mean tries? (cc @D.W.) $\endgroup$
    – Raphael
    Nov 2, 2013 at 10:12
  • $\begingroup$ Very interesting question. Theoretically in a balanced tree, the lowest value would be on left most node and the highest value in right most node? $\endgroup$
    – AquaAlex
    Nov 2, 2013 at 22:49
  • 1
    $\begingroup$ If you do not know what a BIT is: en.wikipedia.org/wiki/Fenwick_tree $\endgroup$
    – AquaAlex
    Nov 2, 2013 at 22:50
  • $\begingroup$ @D.W. citeseerx.ist.psu.edu/viewdoc/summary?doi= $\endgroup$
    – mrk
    Jun 8, 2014 at 11:11

1 Answer 1


You cannot do better than $O(n)$.

Consider a set, where all values are $k$, except $2i$ and $2i-1$, which are $k-l$ and $k+l$ respectively. Any entry in the tree that contains a sum of $m$ values will be $mk$, with the single exception of the entry $2i-1$.

Thus, even if we knew we had a set of the form described, we had to look at $\frac n2$ entries in the worst case, in order to determine the minimum and maximum value.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.