求支持O(1)时间执行get(i)、remove(i)、add(i,e)的数据结构方案

首先明确：不存在能同时让get(i)、remove(i)、add(i, e)三个操作都达到严格O(1)时间复杂度的通用数据结构。核心原因在于：当你在中间位置执行add或remove时，题目要求后续所有元素的逻辑索引必须自增/自减1，这意味着需要更新这些元素的索引映射关系——而这种更新无法在O(1)时间内完成，必然涉及至少部分元素的遍历操作，带来线性时间开销。

不过可以根据你的使用场景，选择以下几种在性能上更接近需求的实现方案：

1. 动态数组（比如Python list、Java ArrayList） #

• get(i)：直接通过下标随机访问，严格O(1)
• add(i, e)/remove(i)：如果操作在数组尾部，这两个操作是O(1)；如果在中间位置，需要移动后续所有元素，时间复杂度为O(n)
• 适用场景：大部分add/remove操作集中在尾部的场景，此时整体性能接近需求

2. 双向链表+哈希表组合 #

• 用双向链表存储元素，哈希表记录逻辑索引到链表节点的映射
• get(i)：直接通过哈希表定位节点，O(1)
• add(i, e)：找到索引i-1对应的节点，插入新节点后，需要将哈希表中所有≥i的索引值加1——这一步是O(k)（k为大于等于i的元素数量），本质还是O(n)
• 注意：如果可以放宽“后续元素索引严格自增1”的要求（比如用节点的唯一标识代替连续逻辑索引），这种结构可以让所有操作达到O(1)，但不符合题目给定的规则

3. 分块数组（块状链表） #

• 将元素分成多个固定大小的块，每个块内部用数组存储
• get(i)：先计算i所在的块，再在块内随机访问，O(1)（块大小固定时）
• add(i, e)/remove(i)：仅操作目标元素所在的块，当块满/空时拆分/合并块，平均时间复杂度为O(√n)，比纯数组的O(n)高效很多，但仍不是严格O(1)
• 适用场景：需要频繁在中间位置执行add/remove，且对时间复杂度要求较高的场景

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