恒定时间级联计算是否可行

Question

这是一个关于计算机技术局限性的教育目的问题。
我有一种心态，即无法创建以下程序。

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

• 用户可以update(i,value) O(1)（平均情况下）data[i]。
• 用户可以查询getAccu(i) = data[0]+data[1]+...+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 个查询之间获得许多更新时，这才值得麻烦。