Aplicaciones, ventajas y desventajas del árbol de segmentos

Primero, comprendamos por qué lo necesitamos antes de aterrizar en la introducción para entender por qué se introdujo este concepto. Supongamos que nos dan una array y necesitamos encontrar la subarreglo 

Propósito de los árboles de segmentos:

Un árbol de segmentos es una estructura de datos que se ocupa de un rango de consultas sobre una array. Tiene un enfoque de divide y vencerás. Se utiliza para resolver el rango mínimo y máximo y Consultas de suma y Consultas de actualización de rango en complejidad de tiempo O (log n).

Construcción del Árbol de Segmentos:

array[]: 5, 3, 2, 4, 1, 8, 6 10

usaremos divide y vencerás

Ahora veremos cómo segmentar el árbol. La construcción está lista.

El número de Nodes será = n + n/2 + n/4 + …… + 2+1

Progresión geométrica: la diferencia común será 2

Sea ‘x’ el número de términos, a = primer término y r = razón común.

(ar)^x-1 = n

a=1,r=2

(2)^x-1=n

log2(2)^x-1=log2n

x=1+log2n=número de niveles

(2) – número de Nodes = 1+2+4+….+n/2+n/4+n

1[(2)^1+inicio de sesión – 1]/2-1 => (2n-1)

Tomemos un ejemplo de devolución y actualización de la suma del subarreglo a[i…..j] de tamaño n.

Ejemplo:

Consulta: salida de la suma de i=1 a i=5

Enfoque 1: iterar de i = 1 a i = 5 y calcular la suma, actualizar el elemento en el i-ésimo índice, actualizaremos a[i] = elemento actualizado. ahora, la complejidad temporal de la consulta es O(n) y la actualización es O(1).

Enfoque 2: enfoque de suma de prefijos

Primero, construiremos la array de suma de prefijos.

Consulta: Salida de la suma de i a j

sum[i….j] = {pref[j] – pref[i-1]} (si i!=0)

preferencia[j] (si i=0)

Complejidad de tiempo : O(1)

Actualizando valor: Ponga a[i] = valor actualizado.

Para actualizar la array de prefijos, debemos cambiar todos los prefijos [i].

Formación:

5

3

2

4

1

8

6

10

yo=4,

Array de suma de prefijos:

5

8

10

14

15

23

29

39

Pongamos un ejemplo para entender esto.

Ejemplo: actualice el cuarto elemento de índice a 13.

Array original: arr[] 

5

3

2

4

13

8

6

10

Suma de prefijo: arr[] todos los elementos se modifican porque el cuarto índice se actualiza, por lo que afectará a todos los elementos después del tercer índice.

5

8

10

14

27

35

41

51

Tabla de comparación de complejidad de tiempo:

	Consulta	Actualizar
Enfoque-1	En)	O(1)
Enfoque-2	O(1)	En)
Árbol de segmentos	O(registro(n))	O(registro(n))

Requisito de complejidad de tiempo de registro (n): muchas veces, la cantidad de consultas y la cantidad de actualizaciones son del orden de 105-106, obtendremos TLE si usamos el enfoque 1 o el enfoque 2.
 

Construcción de un árbol de segmentos:

Es muy simple construir un árbol de segmentos, usamos el enfoque divide y vencerás para construir el árbol de segmentos.

pseudocódigo para la implementación del árbol de segmentos:

const int N = 1e5+2;
int a[N];
árbol int[4*N];

construir vacío (int Node, int st, int en) {

si(st==en) {

árbol[Node] = a[st];
devolver;
}

int medio = (st+en)/2;
build(2*Node, st, mid);
build(2*Node+1, medio+1, en);

árbol[Node] = árbol[2*Node] + árbol[2*Node+1];
}

 

Aplicaciones de los árboles de segmentos:

La estructura de datos del árbol de segmentos se puede utilizar para resolver varios problemas como:

•  Consultas de rango mínimo, máximo y suma, y ​​consultas de actualización de rango
•  árbol de segmentos con la compilación, consulta y actualización máximas.
• árbol de segmentos con compilación mínima, consulta y actualización. 
• Geometría computacional: La geometría computacional es un campo matemático que incluye el diseño y análisis de algoritmos eficientes para resolver problemas geométricos de E/S. También se utiliza para el reconocimiento de patrones y describe algoritmos de modelado sólido.
• Sistemas de información geográfica: Un Sistema de Información Geográfica es un sistema que utiliza datos que se adjuntan a una ubicación única, y analiza y genera información geográficamente referenciada.
• Almacenamiento de segmentos de manera arbitraria.

Ventajas y desventajas de los árboles de segmentos:

S.No	Ventajas	Desventajas
1	No es necesario conocer la rotación de árboles porque en los casos de prueba se utiliza un algoritmo de divide y vencerás.	La complejidad temporal de todas y cada una de las consultas es O(log^2 max(n))
2	Ejecución rápida de código en casos de prueba generales.	El código fuente es más largo que la fuente usando un árbol balanceado.
3	Permite procesar consultas de intervalo o rango en tiempo logarítmico

Tema relacionado: Árbol de segmentos