我正在寻找存储e =（k，v）元素的有序列表的数据结构，并支持以下操作，最多在o（log（log log（log））时间中n是元素的数量。内存使用不是问题。
- e get（index）//index 获取元素
- int find（k）//找到k匹配的元素的索引
- delete（index）//在索引处删除元素，以下元素的索引减少了1
- 插入（索引，e）//在索引处插入元素，以下元素将其索引增加1
我考虑了以下不正确的解决方案：
- 使用阵列：
find，delete和insert仍将O（n） - 使用数组 K到索引的阵列：
delete和insert仍将花费O（n）用于移动元素和更新地图 - 使用链接列表 k的映射到元素地址：
get和find仍将花费O（n）
在我的想象力中，最后一个解决方案是最接近的，但不是链接列表，而不是链接的一个自动平衡树，每个节点在其中存储左侧的元素数量将使我们有可能在O中进行get（log（n））。
但是我不确定我是否正确，所以我想询问我的想象力是否正确以及是否有这种数据结构的名称，以便我可以寻找现成的解决方案。/p>
我能想到的最接近的数据结构是Treaps。
隐式Treap是对常规TREAP的简单修改，这是一种非常强大的数据结构。实际上，隐式TREAP可以被视为具有以下过程（在线模式下O（logn）O（logn）中的以下过程的数组）：
- 在任何位置将元素插入元素
- 删除任意元素
- 在任意间隔中查找总和，最小/最大元素等
- 补充，在任意间隔绘画
- 在任意间隔上反转元素
使用Modification与隐键密钥可让您执行除第二个操作以外的所有操作（找到k匹配的元素的索引）。如果我想出一个更好的想法，我将编辑此答案：）