Considérons une séquence de n nombres réels positifs, (un i), et sa séquence de somme partielle, (s i). Étant donné un nombre x ε (0, s n], nous devons trouver i tels que si -1 < x ≤ s i. De plus nous voulons être en mesure de changer l'un des un i sans avoir à mettre à jour toutes les sommes partielles Les deux peuvent être faites en O (log n) temps en utilisant un arbre binaire avec un i en tant que valeurs de nœud feuille, et les valeurs des nœuds non-feuille étant la somme des valeurs des enfants respectifs. Si n est connu et fixé, l'arbre n'a pas besoin d'être auto-équilibré et peut être stocké efficacement dans un réseau linéaire. En outre, si n est une puissance de deux, seuls 2 n - 1 éléments de réseau sont requis. Voir Blue et al., Phys. Rev. E (1995), pp. R867-R868 pour une application. Étant donné la généricité du problème et la simplicité de la solution, je me demande si cette structure de données a un nom spécifique et s'il existe des implémentations existantes (de préférence en C++). Je l'ai déjà implémenté moi-même, mais écrire des structures de données à partir de zéro semble toujours me réinventer - je serais surpris si personne ne l'avait fait auparavant.arbre binaire qui stocke les sommes partielles: Nom et implémentations existantes
7
A
Répondre
4
Fenwick tree (alias arbre indexé binaire) est une structure de données qui maintient une séquence d'éléments et est capable de calculer la somme cumulative de toute plage d'éléments consécutifs en temps O (logn). La modification de la valeur d'un élément a également besoin de l'heure O (logn).
4
Ceci est connu sous le nom finger tree dans la programmation fonctionnelle mais apparemment il y a des implémentations dans les langages impératifs. Dans les articles il y a un lien vers un blog post expliquant une implémentation de cette structure de données en C# qui pourrait vous être utile.