1
$\begingroup$

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.

$\endgroup$
  • 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 '13 at 20:30
  • $\begingroup$ Do you mean tries? (cc @D.W.) $\endgroup$ – Raphael Nov 2 '13 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 '13 at 22:49
  • 1
    $\begingroup$ If you do not know what a BIT is: en.wikipedia.org/wiki/Fenwick_tree $\endgroup$ – AquaAlex Nov 2 '13 at 22:50
  • $\begingroup$ @D.W. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8917 $\endgroup$ – saadtaame Jun 8 '14 at 11:11
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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