L'analyse en cascade à temps constant est-elle possible?

Question

Ceci est une question éducative sur la limitation de la technologie informatique.
J'ai l'esprit que le programme ci-dessous est impossible à créer. Disons que je dois développer une structure de données statistiques qui s'accumulent.
Voici les spécifications: -

• L'utilisateur peut update(i,value)-data[i] dans O(1) (cas en moyenne). L'utilisateur peut interroger getAccu(i) = data[0]+data[1]+...+data[i] dans O(1) (cas moyen).
• Je ne peux pas supposer l'ordre d'appel des deux fonctions en aucune façon.

Voici mon code (coliru demo).
Il ne répond pas à l'exigence ci-dessus si: -

#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() ... 
} 

Sans limitation de la taille du stockage de la mémoire et le type de structure de données,
est-il possible de faire les deux fonctions update(index,value) et getAccu(index) être O(1)?

Si oui, comment? Si non, pourquoi?

Désolé pour le sujet obscur. Je ne peux pas trouver un plus approprié.

Answer 1

Faire tout en temps constant semble optimiste. Si cela ne vous dérange pas une complexité O(log n), vous pouvez maintenir un arbre binaire équilibré qui stocke dans chaque nœud le total de la sous-arborescence enracinée sur ce nœud. Lorsque vous mettez à jour une valeur, vous devez uniquement mettre à jour les sous-totaux du journal n dans un chemin de la racine à cet élément.

Le calcul de l'accumulateur consiste simplement à localiser le noeud droit à partir de la racine et à ajouter le sous-total gauche chaque fois que vous allez à droite. Au lieu de faire les mises à jour avec impatience, vous pouvez les ajouter en permanence à une liste d'éléments à mettre à jour, puis lorsque vous obtenez une requête et que cette liste n'est pas vide, vous pouvez effectuer chaque mise à jour en log n ou S'il y a beaucoup de mises à jour, mettez à jour uniquement les valeurs dans O(1) et recalculez l'ensemble de l'accumulateur en O(n), mais cela ne vaut le coup que si vous pouvez obtenir beaucoup de mises à jour entre 2 requêtes.