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.
-
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.– D.W. ♦2013年11月01日 20:30:29 +00:00Commented Nov 1, 2013 at 20:30
-
$\begingroup$ Do you mean tries? (cc @D.W.) $\endgroup$Raphael– Raphael2013年11月02日 10:12:48 +00:00Commented 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– AquaAlex2013年11月02日 22:49:47 +00:00Commented 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– AquaAlex2013年11月02日 22:50:41 +00:00Commented Nov 2, 2013 at 22:50
-
$\begingroup$ @D.W. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8917 $\endgroup$mrk– mrk2014年06月08日 11:11:07 +00:00Commented Jun 8, 2014 at 11:11
1 Answer 1
You cannot do better than $O(n)$.
Consider a set, where all values are $k,ドル except 2ドルi$ and 2ドルi-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 2ドルi-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.