时间戳

首页 > 解决方案 > 订单统计树和一维点问题的运算时间复杂度

c++ - 订单统计树和一维点问题的运算时间复杂度

问题描述

我遇到了以下面试问题：

我们需要一个数据结构来保持X 轴上的 n个点，这样我们就可以有效地实现 和Insert(x)（给出区间 中的点数）。假设返回的最大数是。Delete(x)Find (a, b)[a, b]Find(a, b)k

  1. 我们可以创建一个在O(log n)中执行三个操作的数据结构

  2. 我们可以创建一个在O(log n)和O(k + log n)中执行Insertand的数据结构。DeleteFind

我从一般信息中知道，这Find就像一维点上的范围（但为了计算这个问题中的元素，即我们需要元素的数量）。如果我们使用例如 AVL 树，那么我们得到选项 (2) 的时间复杂度。

但是当我被告知（1）是正确答案时，我感到很惊讶。为什么（1）是正确的答案？

标签： c++algorithmmathdata-structurestree

解决方案

答案确实是（1）。

AVL 树的想法很好，你的结论是正确的。但是您可以扩展 AVL 树，使每个节点都有一个额外的属性：在节点自己的值之前的值的数量。在 AVL 操作（包括轮换）中，您必须注意保持这个额外的属性是最新的。但这可以通过恒定的开销来完成，因此它不会影响Insertor的时间复杂度Delete。

然后Find可以只搜索值为a的节点（或最大值小于a的节点），并对值b执行相同操作。从您发现的两个节点中，您可以获得额外的属性。这两者的减法将给出所需的结果。有一些边界情况需要考虑，例如当a存在于树中时，该节点本身也应该计算在内，否则不计算在内。可能找不到值小于或等于a的节点。那么在减法中，缺失的属性应该作为0。

显然，这使其Find独立于其返回值（最多k）。这两个二进制搜索给它一个O(logn)的时间复杂度。

推荐阅读