Arbre de segments

En informatique, un arbre segment (en anglais segment tree), est un arbre enraciné pour stocker des intervalles ou des segments. Il permet des requêtes afin de savoir quels segments contiennent un certain point. C'est, en principe, une structure statique : c'est une structure qui ne peut plus être modifiée une fois qu'elle est créée. Une structure de données similaire est l'arbre intervalle. Un arbre segment pour un ensemble I de n intervalles utilise un stockage de O(n log n) et peut être construit en un temps de O(n log n). Dans un arbre segment on peut rechercher tous les intervalles qui contiennent un certain point (la requête) en O(log n + k), où k est le nombre d'intervalles ou segments extraits. Les applications de l'arbre segment sont dans les domaines de la géométrie algorithmique et du système d'information géographique. L'arbre segment peut aussi être généralisé à des espaces avec des plus grandes dimensions.