c++ - 恒定时间级联计算是否可能？

Question

这是一道关于计算机技术局限性的教育题。
我的心态是无法创建以下程序。

假设我必须开发一个累积统计数据结构。
这是规范:-

• 用户可以在O(1) 中update(i,value) 到data[i](平均情况)。
• 用户可以在O(1 )(平均情况)。
• 我无法以任何方式假定这两个函数的调用顺序。

这是我的代码(coliru demo)。
它不符合上述要求:-

#include <iostream>
#include <vector>
int data[5]={0,1,2,3,4};
int accu[5]={0,1,3,6,10};
/** assume that index always >=1 */
void update(int index,int value){  //O(n) i.e. O(array length)
    data[index]=value;
    for(int n=index-1;n<5;n++){
        accu[n]=accu[n-1]+data[n];
    }
}
int getAccu(int index){            //O(1)
    return accu[index];
}
int main(){
    update(2,12);
    //note: data = 0,1,12,3,4
    //      accu = 0,1,13,16,20
    std::cout<<getAccu(3)<<std::endl; //16
    //update() ... getAccu()... update() ...
}

不受内存存储大小和数据结构类型的限制，
是否可以使 update(index,value) 和 getAccu(index) 这两个函数都为 O(1)？

如果是，怎么办？如果不是，为什么？

抱歉，这个话题晦涩难懂。我找不到更合适的。

Answer 1

在恒定时间内做所有事情似乎很乐观。如果您不介意 O(log n) 的复杂性，您可以维护一个平衡的二叉树，它在每个节点中存储以该节点为根的子树的总数。

当您更新一个值时，您只需要更新从根到该元素的路径中的 log n 个小计。

计算累加器就是从根开始找到右边的节点，每次向右时加上左边的小计。

您可以在恒定时间内将它们添加到待更新项目列表中，而不是急切地进行更新，然后当您收到查询并且该列表不为空时，您可以在 中进行每次更新log n 或者如果有很多更新只更新 O(1) 中的值并在 O(n) 中重新计算整个累加器，但这只值得如果您可能在 2 个查询之间获得许多更新，那就麻烦了。