是否存在表示主要操作时间为 O(n*log n) 的有序列表的数据结构？
Is there a data structure representing an ordered list with O(n*log n) time on main operations?
我正在寻找一种允许在 O(n*log(n)) 复杂度内解决特定问题的数据结构。它需要表示一组整数，我可以在其中执行以下操作：
- 添加一个元素
- 检查集合中是否存在元素
- 删除大于给定整数的每个值
希望具有对数复杂度。
我找了链表，因为在中间添加一个元素和删除整个结构的一部分很容易，但我不知道如何保持有序列表或实现二分搜索。起初我在考虑哈希表，但我不知道如何过滤集合。我正在查看平衡二叉树，但我不知道我是否在寻找某种错觉，或者它是否以某种方式存在，但我就是找不到。
为了从头开始实施，我建议 Treap。
Treap就是一棵二叉搜索树，每个节点都被赋予一个随机的优先级，并且它作为一棵树满足堆条件。这种随机化的数据结构使得查找、插入、删除和拆分树的预期时间为O(log(n))。前三个相当简单。要拆分，只需将一个节点放在要拆分的点上，其优先级高于根节点。然后一半在该节点的一侧结束，另一半在另一侧结束。
请注意，拆分是 O(log(n))，释放删除的位是 O(n)。
请注意，您可能不必执行任何操作。例如，在 C++ 中，您可以只使用 std::map。除了delete之外那些操作的性能是O(log(n))。从大小为 n 的结构中删除长度为 m 的范围是 O(m + log(n))。如果您考虑有关释放内存的评论，那就太理想了。
我正在寻找一种允许在 O(n*log(n)) 复杂度内解决特定问题的数据结构。它需要表示一组整数，我可以在其中执行以下操作： - 添加一个元素 - 检查集合中是否存在元素 - 删除大于给定整数的每个值 希望具有对数复杂度。
我找了链表，因为在中间添加一个元素和删除整个结构的一部分很容易，但我不知道如何保持有序列表或实现二分搜索。起初我在考虑哈希表，但我不知道如何过滤集合。我正在查看平衡二叉树，但我不知道我是否在寻找某种错觉，或者它是否以某种方式存在，但我就是找不到。
为了从头开始实施，我建议 Treap。
Treap就是一棵二叉搜索树，每个节点都被赋予一个随机的优先级，并且它作为一棵树满足堆条件。这种随机化的数据结构使得查找、插入、删除和拆分树的预期时间为O(log(n))。前三个相当简单。要拆分，只需将一个节点放在要拆分的点上，其优先级高于根节点。然后一半在该节点的一侧结束，另一半在另一侧结束。
请注意，拆分是 O(log(n))，释放删除的位是 O(n)。
请注意，您可能不必执行任何操作。例如，在 C++ 中，您可以只使用 std::map。除了delete之外那些操作的性能是O(log(n))。从大小为 n 的结构中删除长度为 m 的范围是 O(m + log(n))。如果您考虑有关释放内存的评论，那就太理想了。