Finding minimum/maximum value in a Binary Indexed Tree
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.