c++ - O(klogn) 时间算法从 Fenwick-Tree 中找到第 k 个最小元素

Question

我的意思是在 O(k log(n)) 时间内找到分域树中 kth 最小的实际频率。
如果我的数据是:

Tree = [1,3,1,10,3]
Actual frequency = [1,2,1,6,3]

因此第二小的元素位于索引 1 处。

Answer 1

你需要第 k 个最小的实际频率，我认为如果不对实际频率进行排序就无法确定。如果您只有 Fenwick 树，那么您可以在 O(n*log(n)) 时间内计算实际频率序列(因为您可以在 O( log(n)) (参见 here )，并且您有 n 个频率)。通过快速排序对实际频率序列进行排序需要 O(n*log(n))，找到排序序列的第 k 个元素需要 O(n)(可能有是具有相同实际频率的条目，因此您不能在 O(1) 中执行此操作；但您可以使用线性搜索)。 所以整个搜索可以在 O(n*log(n)) 中完成。

希望这对您有所帮助。我不知道如何在 O(k*log(n)) 中完成此操作。