Árbol de segmento
# Árbol de segmento

En ciencias 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.

## Descripción de estructura

Esta sección describe la estructura de un árbol de segmento en un espacio de una dimensión.

Sea S un conjunto de intervalos o segmentos. Sea $p_1,$ $p_2,$ ..., $p_m$ una lista de distintos puntos extremos de intervalos, ordenada de izquierda a derecha. Considere la división de la línea de los números reales provocado por estos puntos. La región de esta división es llamada intervalos elementales. Por tanto, los intervalos elementales son, de izquierda a derecha:

    $(-\infty ,p_{1}),[p_{1},p_{1}],(p_{1},p_{2}),[p_{2},p_{2}],...,(p_{m-1},p_{m}),[p_{m},p_{m}],(p_{m},+\infty )$

Es decir, la lista de intervalos elementales está compuesta de intervalos abiertos entre dos puntos finales consecutivos $p_i$ y $p_{i+1},$ alternándose con intervalos cerrados compuesto por un único punto extremo. Puntos por separados son tratados como intervalos porque la respuesta a una consulta no es necesariamente la misma en el interior de un intervalo elemental que en sus puntos extremos.

Dado un conjunto I de intervalos o segmentos, un árbol de segmento T para I está estructurado de la siguiente manera:

* T es un árbol binario.
* Sus nodos hojas corresponden a los intervalos elementales provocados por los puntos extremos en I, en una forma ordenada: la hoja más a la izquierda coincide con el intervalo más a la izquierda. El intervalo elemental correspondiente a una hoja v es denotado por Int(v).
* Los nodos internos de T coinciden con intervalos que son la unión de intervalos elementales: el intervalo Int(N) correspondiente al nodo N es la unión de los intervalos correspondientes a las hojas del subárbol con raíz en N. Eso implica que Int(N) es la unión de los intervalos de sus dos hijos.
* Cada nodo v en T almacena el intervalo Int(v) y un conjunto de intervalos, en alguna estructura de datos. Este subconjunto canónico del nodo v contiene los intervalos [x, x′] de I tal que [x, x′] contiene Int(v) y no contiene Int(padre(v)). Es decir, cada segmento en I almacena los segmentos que abarcan completamente su intervalo, pero no abarca completamente el intervalo de su padre.

## Requerimientos de almacenamiento

Esta sección analiza el costo de almacenamiento de un árbol de segmento en un espacio de una dimensión.

Un árbol de segmento T en un conjunto I de n intervalos usa O(nlogn) de almacenamiento.

    Prueba:
    Lema: Cualquier intervalo [x, x′] de I es almacenado en el conjunto canónico para como máximo dos nodos en la misma profundidad.
       Prueba: Sea $v_1,$ $v_2,$ $v_3$ tres nodos en la misma profundidad, enumerados de izquierda a derecha y p(v) el nodo padre de cualquier nodo v. Suponga [x, x′] es almacenado en $v_1$ y $v_3.$ Esto significa que [x, x′] abarca todo el intervalo desde el punto extremo izquierdo de $Int(v_1)$ hasta el punto extremo derecho de $Int(v_3).$ Note que todo segmento en un nivel en particular no se solapa y se encuentra ordenado de izquierda a derecha: esto es verdadero por construcción para el nivel que contienen las hojas y la propiedad no se pierde cuando se mueve desde cualquier nivel al nivel inmediato superior por combinación de pares de segmentos adyacentes. Ahora $p(v_2)$ = $p(v_1)$ o el primero a la derecha del último (Los bordes en el árbol no se cruzan). En el primer caso, el punto más a la izquierda de $Int(p(v_2))$ es el mismo que el punto más a la izquierda de $Int(v_1);$ en el segundo caso, el punto más a la izquierda de $Int(p(v_2))$ está a la derecha del punto más a la derecha de $Int(p(v_1)),$ por lo tanto también está a la derecha del punto más a la derecha de $Int(v_1).$ En ambos casos $Int(p(v_2))$ comienza en/a la derecha del punto más a la izquierda de $Int(v_1).$ Razonamiento similar muestra que $Int(p(v_2))$ termina en/a la izquierda del punto más a la derecha de $Int(v_3).$ $Int(p(v_2))$ en consecuencia debe estar contenido en [x, x′]; por eso, [x, x′] no podrá estar almacenado en $v_2.$
    El conjunto I tiene como máximo 4n + 1 intervalo elemental. Porque T es un árbol balanceado con a lo máximo 4n + 1 nodos hojas, su altura es O(logn). Como cualquier intervalo es almacenado a lo máximo dos veces en una profundidad del árbol, entonces la cantidad total almacenada es O(nlogn).

## Construcción

Esta sección describe la construcción de un árbol de segmento en un espacio de una dimensión.

Un árbol de segmento desde el conjunto de segmentos I, puede ser construido como sigue. Primero, los puntos finales de los intervalos en I se ordenan. Los intervalos elementales son obtenidos desde este. Entonces, un árbol binario balanceado es construido con los intervalos elementales y para cada nodo v es determinado el intervalo Int(v) que este representa. Quedando computar los subconjuntos canónicos para los nodos. Para lograr esto, los intervalos en I son insertados uno por uno en el árbol de segmento. Un intervalo X = [x, x′] puede ser insertado en un subárbol en T, usando el siguiente procedimiento:

* Si Int(T) está contenido en X entonces se almacena X en T y final.
* Si no:
* Si X se interseca con el subconjunto canónico del hijo izquierdo de T entonces inserta X en este hijo, recursivamente.
* Si X se interseca con el subconjunto canónico del hijo derecho de T entonces inserta X en este hijo, recursivamente.

La operación de construcción completa toma un tiempo O(nlogn), donde n es el número de segmentos en I.

    Prueba
    Ordenar los puntos finales toma un tiempo O(nlogn). Construir un árbol binario balanceado desde los puntos finales ordenados toma tiempo lineal con respecto a n.
    La inserción de un intervalo X = [x, x′] en el árbol cuesta O(logn).
       Prueba: Visitar cada nodo toma un tiempo constante (asumiendo que los subconjuntos canónicos son almacenados en una estructura de datos simple como una lista enlazada). Cuando nosotros visitamos el nodo v nosotros almacenamos X en v o Int(v) contiene un punto extremo de X. Como se prueba arriba, un intervalo es almacenado a lo máximo dos veces en cada nivel del árbol. Hay también a lo máximo un nodo en cada nivel cuyo intervalo correspondiente contiene a x y un nodo cuyo intervalo contiene a x′. Así que, a lo sumo cuatro nodos por nivel son visitados. Debido a que hay O(logn) niveles, el costo total de la inserción es O(logn).

Algoritmo para la construcción de un árbol de segmento en C++:

## Consulta

Esta sección describe la operación de consulta de un árbol de segmento en un espacio de una dimensión.

Una consulta para un árbol de segmento, recibe un punto $q_x$ y recupera una lista de todos los segmentos almacenados que contienen el punto $q_x.$

Formalmente; dado un nodo (subárbol) v y un punto de consulta $q_x,$ la consulta puede ser hecha usando el siguiente algoritmo:

* Reportar todos los intervalos en I(v).
* Si v no es una hoja:
   * Si $q_x$ está en Int(hijo izquierdo de v) entonces
      * Realizar una consulta en el hijo izquierdo de v.
   * Si $q_x$ está en Int(hijo derecho de v) entonces
      * Realizar una consulta en el hijo derecho de v.

En un árbol de segmento que contiene n intervalos, quienes contienen un punto de consulta pueden ser reportados en un tiempo O(logn + k), donde k es el número de intervalos reportados.

    Prueba: El algoritmo de consulta visita un nodo por nivel del árbol, así que en total visita O(logn) nodos. Por otro lado, en un nodo v, los segmentos en I son reportados en un tiempo O(1 + $k_v),$ donde $k_v$ es el número de intervalos en el nodo v reportados. La suma de todos los $k_v$ para todos los nodos v visitados es k el número de segmentos reportados.

Algoritmo para realizar consultas en el árbol de segmento construido con el algoritmo anterior:

## Generalización para espacios multidimensionales

El árbol de segmento puede ser generalizado a espacios multidimensionales, en forma de árbol de segmento multinivel. En versiones multidimensionales, el árbol de segmento almacena una colección de rectángulos de ejes paralelos y puede recuperar los rectángulos que contienen un punto de consulta dado. La estructura usa $O(nlog^dn)$ de almacenamiento y responde consultas en $O(log^dn).$ El uso de fractional cascading baja el tiempo de consulta por un factor logarítmico. El uso del árbol de intervalo en el nivel más profundo de las estructuras asociadas baja el almacenamiento con un factor logarítmico.

