algorithm - 这是一个算法设计问题，需要恒定的时间。我想到了如何使用恒定时间来解决这个问题

Question

以下问题假设 RAM 模型。在这个模型下，我们可以在恒定时间内执行两个 O(log n) 位整数的逻辑编辑和算术运算，也可以在恒定时间内读/写任意内存地址的连续 O(logn) 位。这里有2个问题：

给定一个随机的 0/1 序列 B[0, n-1]。即对于0≤i≤n-1，B[i]=0或1。求解下列问题：。(a) 设计数据结构和算法，使用尽可能小的空间，在常数时间内计算B[0, i]中1的个数。(b) 设计数据结构和算法，使用尽可能小的空间，在常数时间内计算B中第i个1的位置。

标签： algorithm