structure de données qui prend en charge <O (n) requêtes somme des éléments 0 à n

Question

A titre d'exemple, imaginez-vous eu les numéros suivants dans une liste dans cet ordre donné:

list = [4, 10, 3, 5, 1] 

si la liste [0] == 4, et list [4] == 1.

Imaginez maintenant que vous avez besoin d'une requête de somme qui vous dira la somme de toutes les valeurs précédentes jusqu'à cette position donnée.

list.sum(0) == 4 
list.sum(1) == 14 
list.sum(2) == 17 
list.sum(3) == 22 
list.sum(4) == 23 

En outre, je voudrais les opérations suivantes, tout en conservant les requêtes de somme intacte:

list.swap(0, 1) // swap the two positions 
list == [10, 4, 3, 5, 1] 
list.slideBefore(0, 3) // slides 1st position value to before the 2nd position 
list == [4, 3, 10, 5, 1] 
list.slideAfter(2, 3) // slide 1st position value to after 2nd position 
list == [4, 3, 5, 10, 1] 
list.replace(3, 9) // replace value at 1st param with literal value 2nd param 
list == [4, 3, 5, 9, 1] 
list.append(17) // adds value to end 
list == [4, 3, 5, 9, 1, 17] 

Ceci peut être traité par trivialement un tableau. Mais la requête somme serait toujours O (n). J'espérais trouver une structure de données qui garderait la requête somme à O (1) ou O (lg n), tout en gardant les opérations ci-dessus à O (1) ou O (lg n).

Je crois que je pourrais être en mesure de manipuler la structure de données fast array pour accomplir ce que je veux, mais je ne l'ai pas complètement développé.

Une autre structure de données que j'ai examinée était l'arbre Fenwick, mais je ne savais pas que cela fonctionnerait.

Des suggestions, des idées, des astuces ou des astuces?

Answer 1

Considérons un tableau simple, dans lequel vous stockez la somme de cet élément au lieu de l'élément. De cette façon, la

int sum(int n){ 
    return array[n]; // O(1) ! 
}; 

int elem(int n){ 
    if (n) 
     return array[n] - array[n-1]; 
    return array[0]; 
}; 

Il aurait O (1) fois pour toutes les opérations, sauf replace, qui prendrait O (n).

Vous pouvez également considérer un arbre binaire qui contient des valeurs uniquement dans leafs et conserve la somme de ses enfants dans chaque nœud.

Answer 2

La structure de données que vous souhaitez utiliser dépend beaucoup de votre modèle d'accès. Si les requêtes sont très fréquentes et que les opérations de modification sont peu fréquentes, vous pouvez simplement conserver un indicateur "dirty" et recalculer les sommes sur la requête si le flag "dirty" est activé.

Vous pouvez ensuite affiner cela en définissant un "index sale", qui contient l'index de l'élément le plus bas qui a été modifié. Sur requête, vous devez recalculer les sommes pour cet article et tout le reste. Ou, peut-être, seulement jusqu'à l'article dont vous avez besoin de la somme pour, à quel point vous pouvez mettre à jour le "index sale".

Cette sorte d'évaluation paresseuse peut être très efficace si les requêtes sont fréquentes et les modifications peu fréquentes, ou si le modèle comporte de nombreuses modifications suivies de nombreuses requêtes. 'Swap' et 'append` peuvent être faits en O (1), et ne "saliraient" pas les sommes si elles n'étaient pas déjà sales. 'replace' ferait bien sûr que l'indice sale serait réglé sur cet index (à condition, bien sûr, qu'il ne soit pas déjà à un indice inférieur).

slidebefore et slideafter sont intrinsèquement O (N) si votre structure de données est un tableau, car vous devez déplacer les données dans le tableau.Dans votre exemple, vous avez:

list == [10, 4, 3, 5, 1] 
list.slideBefore(0, 3) // slides 1st position value to before the 2nd position 
list == [4, 3, 10, 5, 1] 

Donc, les articles 1 et 2 dans le tableau devait être décalé vers la gauche d'une position pour faire de la place pour le point 0 à être repositionné. Si vous aviez slideBefore(0, 1000), alors 1 000 éléments dans le tableau devraient se déplacer d'une position. Si ces opérations sont fréquentes et que votre liste est volumineuse, vous voudrez probablement une représentation sous-jacente différente.

Une autre possibilité est une implémentation de "liste de listes". Imaginez une liste de 20 éléments répartis en 4 sous-listes de 5 éléments chacun. Chaque sous-liste tient un compte des articles et une somme des articles qui s'y trouvent. Chaque noeud d'une sous-liste conserve la somme cumulée de tous les éléments avant lui dans la liste. Lorsque vous mettez à jour un article, vous n'avez qu'à mettre à jour les sommes pour la sous-liste de cet article. Encore une fois, si vous utilisez l'évaluation paresseuse, vous ne calculeriez les sommes que pour les sous-listes suivantes si quelqu'un en faisait la demande.

Pour gérer les insertions et les suppressions, laissez les sous-listes atteindre une valeur maximale avant de les diviser. Dites que votre "idéal" est de cinq éléments par sous-liste. Mais vous lui permettez de passer à 10 avant de le diviser en deux sous-listes. Pour la suppression, vous pouvez soit laisser une sous-liste aller à 0, ou peut-être la combiner avec la sous-liste précédente ou suivante s'il y a moins de 3 éléments dans la sous-liste.

La taille idéale des sous-listes dépend du nombre total d'éléments que vous prévoyez d'être dans la liste et, encore une fois, du mélange d'opérations que vous prévoyez de rencontrer. Les opérations qui sont intrinsèquement O (N) (comme supprimer et glisser) favoriseront les sous-listes plus petites, mais alors le recalcul devient plus cher parce que vous avez plus de sous-listes. Cela ne change pas vraiment la complexité d'exécution de l'algorithme (c'est-à-dire que O (n/5) est toujours considéré comme O (N)), mais il change le réel temps d'exécution par un peu. Pour les listes de taille modérée, cela pourrait être une vraie victoire.