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.

Improve this question
$\endgroup$
5
  • 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. ♦
    Commented Nov 1, 2013 at 20:30
  • $\begingroup$ Do you mean tries? (cc @D.W.) $\endgroup$
    – Raphael
    Commented 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
    Commented 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
    Commented Nov 2, 2013 at 22:50
  • $\begingroup$ @D.W. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8917 $\endgroup$
    – mrk
    Commented Jun 8, 2014 at 11:11

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

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

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