Árbol de segmento

En ciencia de la computación, un árbol de segmento (en inglés: Segment tree) es una estructura de datos en forma de árbol para guardar intervalos o segmentos. Permite consultar cuál de los segmentos guardados contiene un punto. Este es, en principio, una estructura estática; es decir, su contenido no puede ser modificado una vez que su estructura es construida. Una estructura de datos similar es el árbol de intervalo.Un árbol de segmento para un conjunto I de n intervalos usa O(n log n) de memoria de almacenamiento y puede construirse en un tiempo O(n log n). Los árboles de segmento soportan búsqueda para todos los intervalos que contienen un punto de consulta en O(log n + k), k el número de intervalos o segmentos recuperados.Algunas aplicaciones del árbol de segmento son vistas en las áreas de la geometría computacional y en los sistemas de información geográfica.El árbol de segmentos puede generalizarse para espacios multidimensionales.