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. Nov 1 '13 at 20:30
• Do you mean tries? (cc @D.W.) – Raphael Nov 2 '13 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? – AquaAlex Nov 2 '13 at 22:49
• If you do not know what a BIT is: en.wikipedia.org/wiki/Fenwick_tree – AquaAlex Nov 2 '13 at 22:50
• – saadtaame Jun 8 '14 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.