# Finding minimum/maximum value in a Binary Indexed Tree

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.

• 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"?
– D.W.
Commented Nov 1, 2013 at 20:30
• Do you mean tries? (cc @D.W.) Commented Nov 2, 2013 at 10:12
• 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? Commented Nov 2, 2013 at 22:49
• If you do not know what a BIT is: en.wikipedia.org/wiki/Fenwick_tree Commented Nov 2, 2013 at 22:50
• – mrk
Commented Jun 8, 2014 at 11:11

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.