c++ - 从二叉索引树中删除元素

Question

我有存储不同排序值的二进制索引树（BIT）。例如。query(1) 返回 1，query(2) 返回 2，依此类推。

我想在这个 BIT 中找到第 n 个最大元素。但是下次不应该重复该元素。例如。最初第 4 个最大值为 4。下一次第 4 个最大值为 5，之后第 4 个最大值为 6。

我想到的一种方法是获得第 n 个最大值，然后从 BIT 中删除该元素，或者将所有元素右移到该元素 1，这样下次就不会重复了。但我不知道如何删除 BIT 的元素或移动元素。

如果可能的话，谁能告诉我该怎么做？

Answer 1

基本的 BIT 数据结构如下所示：

value 1|2|3|4|5|6   
f     1|0|2|1|1|3   
c     1|1|3|4|5|8   
tree  1|1|2|4|1|4

在哪里：

f[i] - 索引为 i 的值的频率，i = 1 .. MaxVal
c[i] - 索引 i (f[1] + f[2] + ... + f[i])
树的累积频率 [ i] - 以索引 i 存储在 BIT 中的频率总和

（以上直接来自这篇文章）。

查看上面的数据结构，我们可以看到不可能在 O(log n) 时间内进行删除。想象一下，我们想从树中删除第一个元素。为此，我们需要更新 f[0]、c[0] 和 tree[0]，以反映该元素不再存在于树中。不幸的是，我们还需要遍历 c 结构的其余部分，因为它代表一个累积和。将 c[0] 设置为 0 后，c[1] 不再准确，必须更新，而 c[2] 不再准确……直到 c[n-1]。

在最坏的情况下，这将是一个 O(n) 操作，最坏的情况是删除树中的第一个元素。

我认为使用不同的数据结构将是一个更明智的选择。BITs 和其他二叉树非常适合有效地查找和添加元素，但不擅长删除元素。我建议改用优先级队列。优先级队列（请参阅此Wikipedia 文章）通常使用最小堆作为其底层数据结构，并保证 O(log n) 删除。