是否存在支持O(1)任意位置插入且可索引保序的数据结构？

严格最坏时间复杂度下，不存在同时满足以下三个要求的数据结构：

• O(1)时间按整数索引随机访问元素（即支持a[k]形式的直接访问）
• 任意位置插入操作最坏时间复杂度O(1)
• 维护元素的插入相对顺序，保证相邻元素的先后关系和连续索引一一对应

就算放宽到均摊时间复杂度，目前也没有已知结构能把两个操作的均摊复杂度都做到O(1)，现有能同时支持两类操作的结构，至少有一个操作的时间复杂度在Ω(log n)量级。

以下证明基于通用的字RAM模型（也就是普通计算机的计算模型：单次内存读写、基础整数算术运算都是O(1)，单个内存单元能存储的长度固定）：

1. 先明确两个操作的刚性要求：
   • Access(k)：输入整数k，直接返回序列当前第k个位置的元素，耗时不随序列总长度n上涨，始终是常数级别。
   • Insert(k, x)：在位置k插入新元素x，原来位置≥k的元素全部顺次后移一位，插入后序列长度+1，元素之间的相对先后关系不变，耗时同样是常数级别。
2. 要实现O(1)的Access(k)，核心是输入k之后最多经过常数次内存读写就能找到目标元素。我们最熟悉的连续数组就是这个思路：直接用基地址 + k * 单个元素大小的公式算元素地址，访问速度极快，但这种结构下如果在位置k插入元素，必须把k到末尾的所有元素逐个往后挪一位，要是插在序列头部（k=0），就得移动全部n个元素，时间复杂度直接到Ω(n)，不可能做到O(1)插入。
3. 有人会想放弃连续内存，用非连续编号规避元素移动：给每个元素分配一个整数标签，标签大小和元素顺序一致，插入新元素时就给它分配一个介于前后两个元素标签之间的数值，不用修改已有元素的标签，再用哈希表存标签到元素地址的映射，这样插入的时候看起来不用动老元素。但这个方案有个致命问题：标签和连续的整数索引k没有固定对应关系，你没法输入k直接算出对应的标签是多少，要找第k个元素要么从头顺着标签数（O(n)时间），要么借助跳表、平衡树这类有序结构做排名查询，查询时间直接降到Ω(log n)，满足不了O(1)访问的要求。而且标签用固定长度整数存储的话，两个相邻标签之间的可用整数总有被插满的一天，到时候必须给所有元素重新分配标签，这一步的开销也是Ω(n)。
4. 这个问题的本质矛盾是：只要在非尾部位置插入，插入点之后所有元素的逻辑索引都会加1。要做到O(1)访问，要么让元素的物理内存地址和逻辑索引直接绑定（这时候插入就必须移动后面的所有元素，最坏Ω(n)时间），要么维护一张逻辑索引到物理地址的映射表——但插入点后所有元素的逻辑索引都变了，更新映射表就得改Ω(n)个条目，同样是Ω(n)时间。只要允许在序列头部插入，每次插入就会让所有已有元素的逻辑索引加1，常数次的内存修改根本不可能覆盖所有需要更新的状态，因此不可能实现最坏O(1)的插入。

很多人提到的结构其实都不满足题目的要求：

• 链表：提前拿到插入位置的前驱节点时，插入操作确实是O(1)，但要访问第k个元素必须从头节点开始遍历计数，时间复杂度O(n)，不符合O(1)索引访问的要求。
• 哈希表：可以O(1)按指定key查询元素，但无法维护连续整数索引对应的顺序关系，中间插入元素后，没法直接通过整数k定位到对应位置的元素。
• 顺序统计树、跳表：这两类结构确实能支持按排名（即索引）查询和任意位置插入，但两个操作的时间复杂度都是O(log n)，达不到O(1)的要求。
• 分块动态数组：可以把插入的均摊时间复杂度降到O(√n)，但依然随序列长度n增长，达不到O(1)，随机访问虽然是O(1)，但插入性能不满足要求。

内容的提问来源于stack exchange，提问作者PurpleHacker