Quelles sont les différences entre les arbres à segments, les arbres à intervalles, les arbres à indexation binaire et les arbres à plages ?

Question

Quelles sont les différences entre les arbres à segments, les arbres à intervalles, les arbres à indexation binaire et les arbres à plages en termes de.. :

• Idée clé/définition
• Applications
• Performance/ordre dans les dimensions supérieures/consommation d'espace

S'il vous plaît, ne vous contentez pas de donner des définitions.

Answer 1

Toutes ces structures de données sont utilisées pour résoudre différents problèmes :

• Arbre des segments les intervalles de stockage, et optimisé pour les " lequel de ces intervalles contient un point donné Requêtes ".
• Arbre d'intervalles enregistre également les intervalles, mais il est optimisé pour les " lesquels de ces intervalles chevauchent un intervalle donné ". Il peut également être utilisé pour des requêtes ponctuelles - comme l'arbre de segment.
• Arbre de gamme points de stockage, et optimisé pour les " quels points sont compris dans un intervalle donné Requêtes ".
• Arbre indexé binaire stocke le nombre d'éléments par index, et est optimisé pour " combien y a-t-il d'éléments entre les indices m et n ? Requêtes ".

Performance / Consommation d'espace pour une dimension :

• Arbre des segments - Temps de prétraitement O(n logn), temps de requête O(k+logn), espace O(n logn)
• Arbre d'intervalles - Temps de prétraitement O(n logn), temps de requête O(k+logn), espace O(n)
• Arbre de gamme - Temps de prétraitement O(n logn), temps de requête O(k+logn), espace O(n)
• Arbre indexé binaire - Temps de prétraitement O(n logn), temps de requête O(logn), espace O(n)

(k est le nombre de résultats rapportés).

Toutes les structures de données peuvent être dynamiques, en ce sens que le scénario d'utilisation comprend à la fois des modifications de données et des requêtes :

• Arbre des segments - L'intervalle peut être ajouté/supprimé en O(logn) temps (voir ici )
• Arbre d'intervalles - l'intervalle peut être ajouté/supprimé en O(logn) temps
• Arbre de gamme - de nouveaux points peuvent être ajoutés/supprimés en O(logn) temps (voir ici )
• Arbre indexé binaire - le nombre d'éléments par index peut être augmenté en temps O(logn)

Dimensions supérieures (d>1) :

• Arbre des segments - O(n(logn)^d) temps de prétraitement, O(k+(logn)^d) temps de requête, O(n(logn)^(d-1)) espace
• Arbre d'intervalles - Temps de prétraitement O(n logn), temps de requête O(k+(logn)^d), espace O(n logn)
• Arbre de gamme - O(n(logn)^d) temps de prétraitement, O(k+(logn)^d) temps de requête, O(n(logn)^(d-1)) espace
• Arbre indexé binaire - Temps de prétraitement O(n(logn)^d), temps de requête O((logn)^d), espace O(n(logn)^d)

Answer 2

Non pas que je puisse ajouter quoi que ce soit à La réponse de Lior mais il semble qu'il pourrait avoir besoin d'une bonne table.

Une dimension

k est le nombre de résultats rapportés

Opération

Segment

Intervalle

Gamme

Indexé

Prétraitement

n logn

n logn

n logn

n logn

Requête

k+logn

k+logn

k+logn

logn

Espace

n logn

n

n

n

Insérer/supprimer

logn

logn

logn

logn

Dimensions supérieures

d > 1

Opération

Segment

Intervalle

Gamme

Indexé

Prétraitement

n(logn)^d

n logn

n(logn)^d

n(logn)^d

Requête

k+(logn)^d

k+(logn)^d

k+(logn)^d

(logn)^d

Espace

n(logn)^(d-1)

n logn

n(logn)^(d-1))

n(logn)^d

Answer 3

Les limites du prétraitement et de l'espace pour les arbres de segments et les arbres indexés binaires peuvent être améliorées :

• Les arbres de segments peuvent être stockés dans 2n et construit par la suite dans 2n = O(n) en utilisant la programmation dynamique, si l'on renonce à ajouter des intervalles en tout point arbitraire : https://cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-6
• Le TBI peut être intégré dans n voir cette réponse : Est-il possible de construire un arbre de Fenwick en O(n) ?
• BIT prend également en charge l'opération append to end en tant qu'opération en O(log(n)) temps