能否实现支持O(1)插入、查找、delete_greater_equal的子集数据结构？

问题描述 #

我们需要设计一种抽象数据类型，用来维护集合 {0,1,2,...,n-1} 的一个子集，支持以下三种操作：

• insert(i)：若元素i未存在于子集中，则将其插入
• find(i)：当且仅当元素i在子集中时返回True
• delete_greater_equal(i)：删除子集中所有大于等于i的元素

问：是否可以实现该数据结构，使三个操作的最坏情况时间复杂度均为O(1)？

解答 #

当然可以实现，核心思路是通过标记边界而非物理删除元素，配合记录插入状态的数组来完成所有操作：

我们需要三个基础组件：

• 布尔数组 in_set[]：初始全为False，用来记录元素i是否被插入过
• 整数变量 cutoff：初始值设为n（表示所有元素都处于有效状态），作为当前子集的“有效上限”——所有 >= cutoff 的元素都被视为已删除
• 整数数组 insert_cutoff[]：初始全为0，用来记录元素i最后一次被插入时的cutoff值

各操作的具体实现：

• insert(i)：如果 i >= cutoff，将 in_set[i] 设为True，同时把 insert_cutoff[i] 更新为当前的cutoff；如果 i < cutoff，说明该元素已被之前的删除操作覆盖，插入无意义，直接忽略
• find(i)：返回 in_set[i] == True 且 insert_cutoff[i] >= cutoff——前者说明元素被插入过，后者说明插入操作发生在最近一次影响到i的删除操作之后，因此元素当前仍在子集中
• delete_greater_equal(i)：只需将 cutoff 更新为 max(cutoff, i) 即可，这一步仅涉及变量赋值与比较，完全是O(1)时间

这种实现方式下，三个操作均为常数时间的数组访问或变量操作，最坏情况时间复杂度均为O(1)，完全符合要求。

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