我们假设有n
个值。所有的值都是false
,可以被更改为true
。
我想对这些值执行3个操作,并且它们具有特定的时间复杂度:
val(i)
-> 返回索引i
处的值。 时间复杂度为- O(1)。change(i)
-> 将索引i
处的值更改为true。时间复杂度为 - 摊销O(1)。find(i)
-> 返回最接近索引的索引,其中包含值false
(如果上有false
则返回)。时间复杂度为- O(log n)。
我实际上不太关心空间复杂度。该结构在开始时使用固定长度进行初始化。初始化需要多长时间并不重要。
用于这些操作的数据结构应该是什么样子的?