Segment Tree

SEGMENTAL TREE:

un árbol de segmentos, también conocido como árbol estadístico , es una estructura de datos de árbol utilizada para almacenar información sobre intervalos o segmentos. Permite consultar cuál de los segmentos almacenados contiene un punto dado. Es, en principio, una estructura estática; es decir, es una estructura que no se puede modificar una vez construida. Una estructura de datos similar es el árbol de intervalos .

Un árbol de segmentos para un conjunto I de n intervalos utiliza almacenamiento O ( n log n ) y se puede construir en tiempo O ( n log n ). Los árboles de segmentos admiten la búsqueda de todos los intervalos que contienen un punto de consulta en el tiempo O (log n + k ), siendo k el número de intervalos o segmentos recuperados. [1]

Las aplicaciones del árbol de segmentos se encuentran en las áreas de geometría computacional , sistemas de información geográfica y aprendizaje automático .