arrays - 保持数组索引的变化

Question

假设一个整数数组arr[1..N]。数组以两种方式改变:

• 值正在被覆盖
• 项目被认为是无效的(例如通过设置特殊值-1)

我正在寻找一种数据结构来回答“第 k 项是什么？”很快。

对于单个无效值，这是微不足道的。有很多这样的值，就会变得有点困惑。

我试着保留一个辅助数组，其中包含 1 表示无效索引，否则包含 0。我可以保留此数组的前缀和并在 O(log n) 时间内查询它们。然后我知道在 1 和 k 之间有 sum(k) 个无效项，所以第 k 个项实际上在 k + 总和(k)。但是，在 k 和 k + sum(k) 之间，可能会再次出现一些无效项 - 它会变得很难看。

这个问题是否有更好的解决方案，大概在 O(log n) 时间内？

祝你有美好的一天!

Answer 1

可以使用包含索引的顺序统计树(例如，基于RB或其他平衡搜索树)。删除和查找都需要O(logN)时间