什么数据结构具有这些属性？
What data structure has these properties?
我需要一个存储数据的结构，使得以下所有操作都是对数时间：
该结构表示唯一元素的有序列表。需要支持以下操作：
- 在列表的右端添加一个元素。
- 从列表中的任意位置删除一个元素。
- 获取列表的长度。
- 获取列表中给定索引处的元素。
- 获取给定元素的索引。
例如，如果将此结构实现为简单的 python 列表，则操作 1、3 和 4 是（摊销的）常数时间，而 2 和 5 是线性的（5 可以制成对数相对容易，但 2 仍然有问题）。
我想到的唯一方法是使用哈希 table 存储在每个元素之前完成的插入次数，以及一个二叉搜索树（必须是 self平衡）存储对 (i, value)，其中 i 是在值之前完成了多少次插入，并且是用于使其成为 BST 的顺序，此外每个节点还存储总大小以它为根的子树（每当更改任何节点时都需要向上传播）。这似乎是一个过于复杂的方案，是否有更简单的结构可以在所有列出的操作中实现对数或更好的性能？
这称为Order statistic tree，通常实现为自平衡二叉搜索树（例如红黑树），每个节点存储一个额外的字段：以该节点为根的子树的大小.
所有正常的 BST 操作都必须稍微修改以保持正确的大小，但最后 3 个操作（获取长度、获取索引处的元素、获取元素的索引）都可以相当简单地实现。第一个只是根节点的大小字段；如果您知道 'x is the kth largest element if and only if the number of elements smaller than x is k-1'，并且节点的左（分别为右）子树仅包含比当前节点更小（分别为更大）的元素，那么其他两个操作会更容易。
考虑 BST 中的搜索结构也有帮助：从根开始，在 BST 中搜索 'x'，如果 'x' 小于当前值，我们向左移动节点值，如果当前节点及其整个左子树小于'x'则向右移动，所以一个元素的索引正好是那些更小的个数之和值。
我需要一个存储数据的结构，使得以下所有操作都是对数时间：
该结构表示唯一元素的有序列表。需要支持以下操作：
- 在列表的右端添加一个元素。
- 从列表中的任意位置删除一个元素。
- 获取列表的长度。
- 获取列表中给定索引处的元素。
- 获取给定元素的索引。
例如，如果将此结构实现为简单的 python 列表，则操作 1、3 和 4 是（摊销的）常数时间，而 2 和 5 是线性的（5 可以制成对数相对容易，但 2 仍然有问题）。
我想到的唯一方法是使用哈希 table 存储在每个元素之前完成的插入次数，以及一个二叉搜索树（必须是 self平衡）存储对 (i, value)，其中 i 是在值之前完成了多少次插入，并且是用于使其成为 BST 的顺序，此外每个节点还存储总大小以它为根的子树（每当更改任何节点时都需要向上传播）。这似乎是一个过于复杂的方案，是否有更简单的结构可以在所有列出的操作中实现对数或更好的性能？
这称为Order statistic tree，通常实现为自平衡二叉搜索树（例如红黑树），每个节点存储一个额外的字段：以该节点为根的子树的大小.
所有正常的 BST 操作都必须稍微修改以保持正确的大小，但最后 3 个操作（获取长度、获取索引处的元素、获取元素的索引）都可以相当简单地实现。第一个只是根节点的大小字段；如果您知道 'x is the kth largest element if and only if the number of elements smaller than x is k-1'，并且节点的左（分别为右）子树仅包含比当前节点更小（分别为更大）的元素，那么其他两个操作会更容易。
考虑 BST 中的搜索结构也有帮助：从根开始，在 BST 中搜索 'x'，如果 'x' 小于当前值，我们向左移动节点值，如果当前节点及其整个左子树小于'x'则向右移动，所以一个元素的索引正好是那些更小的个数之和值。