我遇到了以下面试问题：
我们需要一个数据结构来保持n点在X轴上，这样我们就可以有效地实现
Insert(x)、Delete(x)和Find (a, b)(给出间隔[a, b](。假设Find(a, b)返回的最大数量为k。
我们可以创建一个数据结构，在O(logn(中执行三个操作
我们可以创建一个数据结构，在O(logn(中执行
Insert和Delete，并在O(k+logn(中进行Find。
我从一般信息中知道，Find就像1D点上的Range(但对于计算这个问题中的元素，即我们需要元素的数量(。如果我们使用例如AVL树，那么我们得到选项(2(的时间复杂性。
但当我被告知(1(是正确答案时，我很惊讶。为什么(1(答案是正确的？
答案确实是(1(。
AVL树的想法很好，你的结论是正确的。但是，您可以扩展AVL树，使每个节点都有一个额外的属性：位于节点自身值之前的值的数量。在AVL操作(包括轮换(中，您必须确保此额外属性保持最新。但这可以在恒定开销的情况下完成，因此不会影响Insert或Delete的时间复杂性。
然后Find可以只搜索值a的节点(或最大值小于a(，并对值b执行相同操作。从您发现的两个节点中，您都获得了额外的属性。这两项的减法将得到所需的结果。有一些边界情况需要考虑，比如当树中存在时，则该节点本身也应计算在内，否则不应计算在内。可能没有发现值小于或等于a的节点。然后，在减法运算中，应该将丢失的属性作为0。
显然，这使得Find独立于其返回值(高达k(。两个二进制搜索使其时间复杂度为O(logn(。