一千萬個為什麽

搜索

在二進制索引樹中查找最小值/最大值

我知道BIT是如何工作的。但我想知道是否可以使用BIT來查找整個範圍內的最小/最大元素,或者更具體地說,是在完成所有更新過程後找到最小(或最大)值。現在,我知道使用Segment Trees可以很好地實現這一點,但使用BIT可以做到這一點嗎?

我知道遍歷完整BIT並計算每個索引值的明顯方法。我正在尋找一種更有效/優化的方式。

最佳答案

你不能比$ O(n)$更好。

考慮一個集合,其中所有值都是$ k $,除了$ 2i $和$ 2i-1 $,分別是$ k-l $和$ k + l $。樹中包含$ m $值總和的任何條目都是$ mk $,條目$ 2i-1 $的唯一例外。

因此,即使我們知道我們有一套描述的形式,我們也必須在最壞的情況下查看$ \ frac n2 $條目,以確定最小值和最大值。

轉載註明原文: 在二進制索引樹中查找最小值/最大值