4

我需要找到一个可以使用以下操作的数据结构：

  • 构建(S,k) - O(nlogn)
  • 搜索(S,k) - O(logn)
  • 插入(S,k) - O(logn)
  • 删除(S,k) - O(logn)
  • Decrease-Upto(s,k,d) - O(logn) - 这个方法应该减去 d(d>0) 每个 <=k 的节点

显而易见的第一个选择是 RedBlackTree。

但是，我无法找到关于 O(Logn) 中的 Decrease-Upto 的解决方案。如果 k 大于树中的最大键会发生什么 - 这种情况下我必须更新整个树。

有人可以提出其他建议吗？也许一些提示？

4

1 回答 1

4

您可以在树的每个节点中存储一个额外的值，我们称之为 delta。您将节点的增量添加到存储在其所有后代中的键中以获取实际键。因此，要获取特定节点中键的实际值，您需要将从根到该节点的所有增量相加，并将此总和添加到存储的键中。

要做到这一点Decrease-Upto，您只需从根更改一条路径上的 O(log n) 节点的增量。

您不必在此操作后更改树的结构，因为它不会更改键的顺序。

于 2010-02-10T12:41:10.933 回答