设计将引用元素移动到开头的数据结构.C++

Question

我需要设计一种数据结构，允许以类似于普通数组的方式按索引访问数组。但是在引用第 i 个元素之后，我应该将其移动到开头。 它可以通过链表和O(n( 访问复杂性轻松完成，但我需要一种方法来实现更好的性能。如果您愿意，您可以假设禁止插入此类数据结构。

例如：

T=[5, 4, 9, 45] - Initial state
1. Access to 2-th element => T[2] returns 9, now T=[9,5,4,45](We move 2-th element to the beginning)
2. Access to 3-th element => T[3] returns 45, now T=[45,9,5,4](We move 3-th element to the beginning)
3. T[0] returns 45, T=[45,9,5,4]
4. T[2] returns 5, T=[5,45,9,4]

我希望问题清楚了。请建议任何相关的链接或代码片段。

编辑： 我听说过笛卡尔树和绳索。哪一个更适合在这里应用，为什么？

Answer 1

平衡绳索保证摊销的 O(log N( 分度、删除和插入时间。所讨论的操作可以分解为三个序列。