data-structures => Árbol de segmentos

Introducción al árbol de segmentos

Supongamos que tenemos una matriz:

+-------+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |
+-------+-----+-----+-----+-----+-----+-----+
| Value |  -1 |  3  |  4  |  0  |  2  |  1  |
+-------+-----+-----+-----+-----+-----+-----+

Queremos realizar alguna consulta en esta matriz. Por ejemplo:

¿Cuál es el mínimo de índice 2 a índice 4 ? -> 0
¿Cuál es el máximo de índice 0 a índice 3 ? -> 4
¿Cuál es la suma del índice 1 al índice 5 ? -> 10

¿Cómo lo averiguamos?

Fuerza bruta:
Podríamos atravesar la matriz desde el índice inicial hasta el índice final y responder nuestra consulta. En este enfoque, cada consulta toma tiempo O(n) donde n es la diferencia entre el índice de inicio y el índice de finalización. Pero ¿y si hay millones de números y millones de consultas? Para m consultas, tomaría O(mn) tiempo. Por lo tanto, para valores de 10⁵ en nuestra matriz, si realizamos consultas de 10⁵, en el peor de los casos, tendremos que atravesar elementos de 10¹⁰.

Programación dinámica:
Podemos crear una matriz de 6X6 para almacenar los valores para diferentes rangos. Para la consulta de rango mínimo (RMQ), nuestra matriz se vería así:

              0     1     2     3     4     5
     +-----+-----+-----+-----+-----+-----+-----+
     |     |  -1 |  3  |  4  |  0  |  2  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+
  0  |  -1 |  -1 |  -1 |  -1 |  -1 |  -1 |  -1 |
     +-----+-----+-----+-----+-----+-----+-----+
  1  |  3  |     |  3  |  3  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+
  2  |  4  |     |     |  4  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+
  3  |  0  |     |     |     |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+
  4  |  2  |     |     |     |     |  2  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+
  5  |  1  |     |     |     |     |     |  1  |
     +-----+-----+-----+-----+-----+-----+-----+

Una vez que tengamos esta estructura de matriz, sería suficiente responder a todas las RMQ. Aquí, Matrix [i] [j] almacenaría el valor mínimo de index- i a index- j . Por ejemplo: el mínimo de índice 2 a índice 4 es Matriz [2] [4] = 0 . Esta matriz responde a la consulta en tiempo O(1) , pero se necesita tiempo O (n²) para construir esta matriz y espacio O(n²) para almacenarla. Entonces, si n es un número realmente grande, esto no se escala muy bien.

Árbol de segmentos:
Un árbol de segmentos es una estructura de datos de árbol para almacenar intervalos o segmentos. Permite consultar cuál de los segmentos almacenados contiene un punto dado. Se necesita O(n) tiempo para construir un árbol de segmentos, se necesita O(n) espacio para mantenerlo y responde a una consulta en tiempo O(logn) .

El árbol de segmentos es un árbol binario y los elementos de la matriz dada serán las hojas de ese árbol. Crearemos el árbol de segmentos dividiendo la matriz por la mitad hasta que alcancemos un único elemento. Así que nuestra división nos proporcionaría:

Ahora, si reemplazamos los nodos que no son hojas con el valor mínimo de sus hojas, obtenemos:

Este es nuestro árbol de segmentos. Podemos observar que el nodo raíz contiene el valor mínimo de toda la matriz (rango [0,5]), su hijo izquierdo contiene el valor mínimo de nuestra matriz izquierda (rango [0,2]), el hijo derecho contiene el mínimo valor de nuestra matriz derecha (rango [3,5]) y así sucesivamente. Los nodos de la hoja contienen el valor mínimo de cada punto individual. Obtenemos:

Ahora vamos a hacer una consulta de rango en este árbol. Para hacer una consulta de rango, necesitamos verificar tres condiciones:

Superposición parcial: comprobamos ambas hojas.
Superposición total: Devolvemos el valor almacenado en el nodo.
Sin superposición: Devolvemos un valor muy grande o infinito.

Digamos que queremos verificar el rango [2,4] , eso significa que queremos encontrar el mínimo de índice 2 a 4 . Comenzaremos desde la raíz y comprobaremos si el rango de nuestros nodos está superpuesto por nuestro rango de consulta o no. Aquí,

[2,4] no se superpone completamente [0,5] . Así que vamos a revisar ambas direcciones.
- En el subárbol izquierdo, [2,4] se superpone parcialmente [0,2] . Revisaremos ambas direcciones.
  - En el subárbol izquierdo, [2,4] no se superpone [0,1] , por lo que esto no contribuirá a nuestra respuesta. Volvemos al infinito .
  - En el subárbol derecho, [2,4] se superpone totalmente [2,2] . Devolvemos 4 .
    El mínimo de estos dos valores devueltos (4, infinito) es 4 . Obtenemos 4 de esta porción.
- En el subárbol derecho, [2,4] se superpone parcialmente. Así que vamos a revisar ambas direcciones.
  - En el subárbol izquierdo, [2,4] se superpone completamente [3,4] . Devolvemos 0 .
  - En el subárbol derecho, [2,4] no se superpone [5,5] . Volvemos al infinito .
    El mínimo de estos dos valores devueltos (0, infinito) es 0 . Obtenemos 0 de esta parte.
El mínimo de los valores devueltos (4,0) es 0 . Este es nuestro mínimo deseado en el rango [2,4] .

Ahora podemos verificar que, sin importar cuál sea nuestra consulta, se necesitarían un máximo de 4 pasos para encontrar el valor deseado de este árbol de segmentos.

Utilizar:

Intervalo mínimo de consulta
El ancestro común más bajo
Propagación perezosa
Suma de Subárbol Dinámico
Negligencia y min
Campos duales
Encontrar k-th elemento más pequeño
Encontrar el número de pares desordenados

Implementación de Segment Tree Using Array

Digamos que tenemos una matriz: Item = {-1, 0, 3, 6} . Queremos construir una matriz de SegmentTree para averiguar el valor mínimo en un rango determinado. Nuestro árbol de segmentos se verá como:

Los números debajo de los nodos muestran los índices de cada valor que almacenaremos en nuestra matriz SegmentTree . Podemos ver que, para almacenar 4 elementos, necesitábamos una matriz de tamaño 7. Este valor está determinado por:

Procedure DetermineArraySize(Item):
multiplier := 1
n := Item.size
while multiplier < n
    multiplier := multiplier * 2
end while
size := (2 * multiplier) - 1
Return size

Entonces, si tuviéramos una matriz de longitud 5, el tamaño de nuestra matriz SegmentTree sería: ( 8 * 2 ) - 1 = 15 . Ahora, para determinar la posición del hijo izquierdo y derecho de un nodo, si un nodo está en el índice i , entonces la posición de su:

Niño izquierdo se denota por: (2 * i) + 1 .
Right Child se denota por: (2 * i) + 2 .

Y el índice del padre de cualquier nodo en el índice i se puede determinar por: (i - 1) / 2 .

Entonces, la matriz SegmentTree que representa nuestro ejemplo se vería así:

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
|  -1 |  -1 |  3  |  -1 |  0  |  3  |  6  |
+-----+-----+-----+-----+-----+-----+-----+

Veamos el pseudo-código para construir esta matriz:

Procedure ConstructTree(Item, SegmentTree, low, high, position):
if low is equal to high
    SegmentTree[position] := Item[low]
else
    mid := (low+high)/2
    constructTree(Item, SegmentTree, low, mid, 2*position+1)
    constructTree(Item, SegmentTree, mid+1, high, 2*position+2)
    SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])
end if

Al principio, tomamos la entrada de los valores e inicializamos la matriz SegmentTree con infinity utilizando la longitud de la matriz del elemento como su tamaño. Llamamos al procedimiento utilizando:

bajo = Índice inicial de la matriz de elementos .
alto = índice de acabado de la matriz de elementos .
position = 0, indica la raíz de nuestro árbol de segmentos.

Ahora, tratemos de entender el procedimiento usando un ejemplo:

El tamaño de nuestra matriz de elementos es 4 . Creamos una matriz de longitud (4 * 2) - 1 = 7 y las inicializamos con infinity . Puede utilizar un valor muy grande para ello. Nuestra matriz se vería como:

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | inf | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

Dado que este es un procedimiento recursivo, veremos el funcionamiento de ConstructTree utilizando una tabla de recursión que realiza un seguimiento de low , high , position , mid y calling line en cada llamada. Al principio, llamamos a ConstructTree (Item, SegmentTree, 0, 3, 0) . Aquí, low no es lo mismo que high , obtendremos un mid . La calling line que calling line indica a qué ConstructTree se llama después de esta declaración. Denotamos las llamadas de ConstructTree dentro del procedimiento como 1 y 2 respectivamente. Nuestra mesa se verá como:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+

Entonces, cuando llamamos a ConstructTree-1 , pasamos: low = 0 , high = mid = 1 , position = 2*position+1 = 2*0+1 = 1 . Una cosa que puedes notar, que es 2*position+1 es el hijo izquierdo de root , que es 1 . Dado que low no es igual a high , obtenemos un valor mid . Nuestra mesa se verá como:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       1      |
+-----+------+----------+-----+--------------+

En la siguiente llamada recursiva, pasamos low = 0 , high = mid = 0 , position = 2*position+1 = 2*1+1=3 . Nuevamente el hijo izquierdo del índice 1 es 3 . Aquí, low es e high , así que configuramos SegmentTree[position] = SegmentTree[3] = Item[low] = Item[0] = -1 . Nuestra matriz SegmentTree se verá como:

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf |  -1 | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

Nuestra tabla de recursión se verá así:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   0  |     3    |     |              |
+-----+------+----------+-----+--------------+

Como pueden ver, -1 tiene su posición correcta. Como esta llamada recursiva está completa, volvemos a la fila anterior de nuestra tabla de recursiones. La mesa:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       1      |
+-----+------+----------+-----+--------------+

En nuestro procedimiento, ejecutamos la llamada a ConstructTree-2 . Esta vez, pasamos low = mid+1 = 1 , high = 1 , position = 2*position+2 = 2*1+2 = 4 . Nuestra calling line cambia a 2 . Obtenemos:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       2      |
+-----+------+----------+-----+--------------+

Dado que, low es igual a high , establecemos: SegmentTree[position] = SegmentTree[4] = Item[low] = Item[1] = 2 . Nuestra matriz de SegmentTree :

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf |  -1 |  2  | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

Nuestra tabla de recursión:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       2      |
+-----+------+----------+-----+--------------+
|  1  |   1  |     4    |     |              |
+-----+------+----------+-----+--------------+

De nuevo se puede ver, 2 tiene su posición correcta. Después de esta llamada recursiva, volvemos a la fila anterior de nuestra tabla de recursiones. Obtenemos:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       2      |
+-----+------+----------+-----+--------------+

SegmentTree[position] = SegmentTree[1] = min(SegmentTree[2*position+1], SegmentTree[2*position+2]) = min(SegmentTree[3], SegmentTree[4]) = min(-1,2) = -1 la última línea de nuestro procedimiento, SegmentTree[position] = SegmentTree[1] = min(SegmentTree[2*position+1], SegmentTree[2*position+2]) = min(SegmentTree[3], SegmentTree[4]) = min(-1,2) = -1 . Nuestra matriz de SegmentTree :

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf |  -1 | inf |  -1 |  2  | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

Como esta llamada de recursión está completa, volvemos a la fila anterior de nuestra tabla de recursión y llamamos a ConstructTree-2 :

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       2      |
+-----+------+----------+-----+--------------+

Podemos ver que la parte izquierda de nuestro árbol de segmentos está completa. Si continuamos de esta manera, después de completar todo el procedimiento, finalmente obtendremos una matriz de SegmentTree completada, que se verá así:

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
|  -1 |  -1 |  0  |  -1 |  2  |  4  |  0  |
+-----+-----+-----+-----+-----+-----+-----+

La complejidad de tiempo y espacio de la construcción de esta matriz de SegmentTree es: O(n) , donde n denota el número de elementos en la matriz de elementos . Nuestra matriz SegmentTree construida se puede usar para realizar consultas de rango mínimo (RMQ) . Para construir una matriz para realizar una consulta de rango máximo , necesitamos reemplazar la línea:

SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])

con:

SegmentTree[position] := max(SegmentTree[2*position+1], SegmentTree[2*position+2])

Realizar una consulta de rango mínimo

El procedimiento para realizar una RMQ ya se muestra en la introducción. El pseudo-código para verificar el rango mínimo de consulta será:

Procedure RangeMinimumQuery(SegmentTree, qLow, qHigh, low, high, position):
if qLow <= low and qHigh >= high        //Total Overlap
    Return SegmentTree[position]
else if qLow > high || qHigh < low      //No Overlap
    Return infinity
else                                    //Partial Overlap
    mid := (low+high)/2
    Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
               RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
end if

Aquí, qLow = The lower range of our query , qHigh = The upper range of our query . low = starting index of Item array , high = Finishing index of Item array , position = root = 0 . Ahora tratemos de entender el procedimiento usando el ejemplo que creamos antes:

Nuestra matriz de SegmentTree :

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
|  -1 |  -1 |  0  |  -1 |  2  |  4  |  0  |
+-----+-----+-----+-----+-----+-----+-----+

Queremos encontrar el mínimo en el rango [1,3] .
Dado que este es un procedimiento recursivo, veremos el funcionamiento de RangeMinimumQuery utilizando una tabla de recursión que realiza un seguimiento de qLow , qHigh , low , high , position , mid y calling line . Al principio, llamamos a RangeMinimumQuery (SegmentTree, 1, 3, 0, 3, 0. Aquí, no se cumplen las dos primeras condiciones (superposición parcial). RangeMinimumQuery un valor mid . La calling line indica a qué RangeMinimumQuery se llama después de esto declaración. Denotamos las llamadas RangeMinimumQuery dentro del procedimiento como 1 y 2 respectivamente. Nuestra tabla se verá así:

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+

Así que cuando llamamos RangeMinimumQuery-1 , pasamos: low = 0 , high = mid = 1 , position = 2*position+1 = 1 . Una cosa que puedes notar, es que 2*position+1 es el hijo izquierdo de un nodo . Eso significa que estamos comprobando el hijo izquierdo de root . Dado que [1,3] se superpone parcialmente [0,1] , las dos primeras condiciones no se cumplen, obtenemos una mid . Nuestra mesa:

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   1  |     1    |  0  |       1      |
+------+-------+-----+------+----------+-----+--------------+

En la siguiente llamada recursiva, pasamos low = 0 , high = mid = 0 , position = 2*position+1 = 3 . Llegamos a la hoja más a la izquierda de nuestro árbol. Como [1,3] no se superpone con [0,0] , devolvemos el infinity a nuestra función de llamada. Tabla de recursión:

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   1  |     1    |  0  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   0  |     3    |     |              |
+------+-------+-----+------+----------+-----+--------------+

Como esta llamada recursiva está completa, volvemos a la fila anterior de nuestra tabla de recursiones. Obtenemos:

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   1  |     1    |  0  |       1      |
+------+-------+-----+------+----------+-----+--------------+

En nuestro procedimiento, ejecutamos la llamada RangeMinimumQuery-2 . Esta vez, pasamos low = mid+1 = 1 , high = 1 y position = 2*position+2 = 4 . Nuestra calling line changes to **2** . Obtenemos:

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   1  |     1    |  0  |       2      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  1  |   1  |     4    |     |              |
+------+-------+-----+------+----------+-----+--------------+

Así que vamos al hijo correcto del nodo anterior. Esta vez hay una superposición total. SegmentTree[position] = SegmentTree[4] = 2 el valor SegmentTree[position] = SegmentTree[4] = 2 .

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+

De vuelta en la función de llamada, estamos comprobando cuál es el mínimo de los dos valores devueltos de dos funciones de llamada. Obviamente el mínimo es 2 , devolvemos 2 a la función de llamada. Nuestra tabla de recursión se ve como:

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+

Hemos terminado de mirar la parte izquierda de nuestro árbol de segmentos. Ahora llamaremos a RangeMinimumQuery-2 desde aquí. Pasaremos low = mid+1 = 1+1 =2 , high = 3 y position = 2*position+2 = 2 . Nuestra mesa:

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  2  |   3  |     2    |     |              |
+------+-------+-----+------+----------+-----+--------------+

Hay una superposición total. Entonces devolvemos el valor: SegmentTree[position] = SegmentTree[2] = 0 . Regresamos a la recursión desde donde se llamó a estos dos niños y obtenemos el mínimo de (4,0) , que es 0 y devolvemos el valor.

Después de ejecutar el procedimiento, obtenemos 0 , que es el mínimo de índice 1 a índice 3 .

La complejidad del tiempo de ejecución para este procedimiento es O(logn) donde n es el número de elementos en la matriz de elementos . Para realizar una consulta de rango máximo, necesitamos reemplazar la línea:

Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
               RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))

con:

Return max(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
               RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))

Propagación perezosa

Digamos que ya ha creado un árbol de segmentos. Es necesario que actualice los valores de la matriz, esto no solo cambiará los nodos de hoja de su árbol de segmentos, sino también el mínimo / máximo en algunos nodos. Veamos esto con un ejemplo:

Este es nuestro árbol de segmentos mínimo de 8 elementos. Para darle un recordatorio rápido, cada nodo representa el valor mínimo del rango mencionado junto a ellos. Digamos que queremos incrementar el valor del primer elemento de nuestra matriz en 3 . ¿Cómo podemos hacer eso? Seguiremos la forma en que realizamos la RMQ. El proceso se vería como:

Al principio, atravesamos la raíz. [0,0] se superpone parcialmente con [0,7] , vamos a ambas direcciones.
- En el subárbol izquierdo, [0,0] se superpone parcialmente con [0,3] , vamos a ambas direcciones.
  - En el subárbol izquierdo, [0,0] se superpone parcialmente con [0,1] , vamos a ambas direcciones.
    - En el subárbol izquierdo, [0,0] se superpone totalmente con [0,0] , y dado que es el nodo hoja, actualizamos el nodo aumentando su valor en 3 . Y devuelve el valor -1 + 3 = 2 .
    - En el subárbol derecho, [1,1] no se superpone con [0,0] , devolvemos el valor en el nodo ( 2 ).
      El mínimo de estos dos valores devueltos ( 2 , 2 ) es 2 , por lo que actualizamos el valor del nodo actual y lo devolvemos.
  - En el subárbol derecho [2,3] no se superpone con [0,0] , devolvemos el valor del nodo. ( 1 ).
    Como el mínimo de estos dos valores devueltos ( 2 , 1 ) es 1 , actualizamos el valor del nodo actual y lo devolvemos.
- En el subárbol derecho [4,7] no se superpone con [0,0] , devolvemos el valor del nodo. ( 1 ).
Finalmente, el valor del nodo raíz se actualiza ya que el mínimo de los dos valores devueltos (1,1) es 1 .

Podemos ver que la actualización de un solo nodo requiere una complejidad de tiempo O(logn) , donde n es el número de nodos hoja. Entonces, si nos piden que actualicemos algunos nodos de i a j , necesitaremos complejidad de tiempo O(nlogn) . Esto se vuelve engorroso para un gran valor de n . Seamos perezosos , es decir, trabajemos solo cuando sea necesario. ¿Cómo? Cuando necesitamos actualizar un intervalo, actualizaremos un nodo y marcaremos a su hijo que necesita ser actualizado y lo actualizaremos cuando sea necesario. Para esto necesitamos una matriz perezosa del mismo tamaño que la de un árbol de segmentos. Inicialmente, todos los elementos de la matriz diferida serán 0, lo que representa que no hay una actualización pendiente. Si hay un elemento distinto de cero en perezoso [i] , este elemento debe actualizar el nodo i en el árbol de segmentos antes de realizar cualquier operación de consulta. ¿Cómo vamos a hacer eso? Veamos un ejemplo:

Digamos, para nuestro árbol de ejemplo, queremos ejecutar algunas consultas. Estos son:

incremento [0,3] por 3 .
incremento [0,3] por 1 .
Incremento [0,0] en 2 .

incremento [0,3] por 3:

Partimos del nodo raíz. Al principio, comprobamos si este valor está actualizado. Para esto verificamos nuestra matriz perezosa que es 0 , lo que significa que el valor está actualizado. [0,3] se superpone parcialmente [0,7] . Así que vamos a las dos direcciones.
- En el subárbol izquierdo, no hay actualización pendiente. [0,3] se superpone totalmente [0,3] . Así que actualizamos el valor del nodo por 3 . Entonces el valor se convierte en -1 + 3 = 2 . Esta vez, no vamos a ir todo el camino. En lugar de bajar, actualizamos el elemento secundario correspondiente en el árbol diferido de nuestro nodo actual y lo incrementamos en 3 . También devolvemos el valor del nodo actual.
- En el subárbol derecho, no hay actualización pendiente. [0,3] no se superpone [4,7] . Entonces devolvemos el valor del nodo actual (1) .
  El mínimo de dos valores devueltos ( 2 , 1 ) es 1 . Actualizamos el nodo raíz a 1 .

Nuestro árbol de segmentos y árbol perezoso se vería así:

Los valores que no son cero en los nodos de nuestro Árbol perezoso representan, hay actualizaciones pendientes en esos nodos y más abajo. Los actualizaremos si es necesario. Si se nos pregunta, cuál es el mínimo en el rango [0,3] , llegaremos al subárbol izquierdo del nodo raíz y, como no hay actualizaciones pendientes, devolveremos 2 , lo cual es correcto. Entonces, este proceso no afecta la corrección de nuestro algoritmo de árbol de segmentos.

incremento [0,3] por 1:

Partimos del nodo raíz. No hay actualización pendiente. [0,3] se superpone parcialmente [0,7] . Así que vamos a ambas direcciones.
- En el subárbol izquierdo, no hay actualización pendiente. [0,3] se superpone completamente [0,3] . Actualizamos el nodo actual: 2 + 1 = 3 . Dado que este es un nodo interno, actualizamos sus hijos en el Árbol diferido para que se incrementen en 1 . También devolveremos el valor del nodo actual ( 3 ).
- En el subárbol derecho, no hay actualización pendiente. [0,3] no se superpone [4,7] . Devolvemos el valor del nodo actual ( 1 ).
Actualizamos el nodo raíz tomando el mínimo de dos valores devueltos ( 3 , 1 ).

Nuestro árbol de segmentos y árbol perezoso se verá así:

Como puede ver, estamos acumulando las actualizaciones en Lazy Tree pero no lo estamos presionando. Esto es lo que significa la propagación perezosa. Si no lo hubiésemos usado, tuvimos que empujar los valores hasta las hojas, lo que nos costaría una complejidad de tiempo más innecesaria.

incremento [0,0] por 2:

Partimos del nodo raíz. Como la raíz está actualizada y [0,0] se superpone parcialmente [0,7] , vamos a ambas direcciones.
- En el subárbol izquierdo, el nodo actual está actualizado y [0,0] se superpone parcialmente [0,3] , vamos a ambas direcciones.
  - En el subárbol izquierdo, el nodo actual en Lazy Tree tiene un valor distinto de cero. Así que hay una actualización que aún no se ha propagado a este nodo. Primero vamos a actualizar este nodo en nuestro árbol de segmentos. Entonces esto se convierte en -1 + 4 = 3 . Luego vamos a propagar este 4 a sus hijos en el árbol perezoso. Como ya hemos actualizado el nodo actual, cambiaremos el valor del nodo actual en Lazy Tree a 0 . Luego [0,0] se superpone parcialmente [0,1] , por lo que vamos a ambas direcciones.
    - En el nodo izquierdo, el valor debe actualizarse ya que hay un valor distinto de cero en el nodo actual de Lazy Tree. Así que actualizamos el valor a -1 + 4 = 3 . Ahora, ya que [0,0] se superpone totalmente [0,0] , actualizamos el valor del nodo actual a 3 + 2 = 5 . Este es un nodo hoja, por lo que no necesitamos propagar más el valor. Actualizamos el nodo correspondiente en Lazy Tree a 0, ya que todos los valores se han propagado hasta este nodo. Devolvemos el valor del nodo actual ( 5 ).
    - En el nodo derecho, el valor debe actualizarse. Entonces el valor se convierte en: 4 + 2 = 6 . Como [0,0] no se superpone [1,1] , devolvemos el valor del nodo actual ( 6 ). También actualizamos el valor en Lazy Tree a 0 . No se necesita propagación ya que este es un nodo de hoja.
      Actualizamos el nodo actual utilizando el mínimo de dos valores devueltos ( 5 , 6 ). Devolvemos el valor del nodo actual ( 5 ).
  - En el subárbol derecho, hay una actualización pendiente. Actualizamos el valor del nodo a 1 + 4 = 5 . Como este no es un nodo de hoja, propagamos el valor a sus hijos en nuestro Árbol diferido y actualizamos el nodo actual a 0 . Como [0,0] no se superpone con [2,3] , devolvemos el valor de nuestro nodo actual ( 5 ).
    Actualizamos el nodo actual utilizando el mínimo de los valores devueltos ( 5 , 5 ) y devolvemos el valor ( 5 ).
- En el subárbol derecho, no hay actualización pendiente y como [0,0] no se superpone [4,7] , devolvemos el valor del nodo actual ( 1 ).
Actualizamos el nodo raíz utilizando el mínimo de los dos valores devueltos ( 5 , 1 ).

Nuestro árbol de segmentos y árbol perezoso se verá así:

Podemos notar que, el valor en [0,0] , cuando es necesario, obtuvo todo el incremento.

Ahora, si se le pide que encuentre el rango mínimo [3,5] , si ha comprendido hasta este punto, puede averiguar fácilmente cómo iría la consulta y el valor devuelto será 1 . Nuestro segmento Tree y Lazy Tree se vería así:

Simplemente hemos seguido el mismo proceso que seguimos para encontrar RMQ con restricciones añadidas de verificación de Lazy Tree en busca de actualizaciones pendientes.

Otra cosa que podemos hacer es en lugar de devolver los valores de cada nodo, ya que sabemos cuál será el nodo secundario de nuestro nodo actual, simplemente podemos verificarlos para encontrar el mínimo de estos dos.

El pseudocódigo para actualizar en Lazy Propagation sería:

Procedure UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
                                endRange, delta, low, high, position):
if low > high                                                //out of bounds
    Return
end if
if LazyTree[position] is not equal to 0                      //update needed
    segmentTree[position] := segmentTree[position] + LazyTree[position]
    if low is not equal to high                              //non-leaf node    
        LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
        LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
    end if
    LazyTree[position] := 0
end if
if startRange > low or endRange < high                       //doesn't overlap
    Return
end if
if startRange <= low && endRange >= high                     //total overlap
    segmentTree[position] := segmentTree[position] + delta
    if low is not equal to high
        LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
        LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
    end if
    Return
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
                                endRange, delta, low, mid, 2 * position + 1)
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
                                endRange, delta, mid + 1, high, 2 * position + 2)
segmentTree[position] := min(segmentTree[2 * position + 1], 
                                                    segmentTree[2 * position + 2])

Y el pseudo-código para RMQ en la propagación perezosa será:

Procedure RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh, low, high, position):
if low > high
    Return infinity
end if
if LazyTree[position] is not equal to 0                      //update needed
    segmentTree[position] := segmentTree[position] + LazyTree[position]
    if low is not equal to high
        segmentTree[position] := segmentTree[position] + LazyTree[position]
    if low is not equal to high                              //non-leaf node    
        LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + LazyTree[position]
        LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + LazyTree[position]
    end if
    LazyTree[position] := 0
end if
if qLow > high and qHigh < low                                //no overlap
    Return infinity
end if
if qLow <= low and qHigh >= high                              //total overlap
    Return segmentTree[position]
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
Return min(RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh, 
                                        low, mid, 2 * position + 1),
           RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh,
                                        mid + 1, high, 2 * position + 1)

Modified text is an extract of the original Stack Overflow Documentation

Licenciado bajo CC BY-SA 3.0

No afiliado a Stack Overflow

data-structures
Árbol de segmentos

Buscar..

Introducción al árbol de segmentos

Implementación de Segment Tree Using Array

Realizar una consulta de rango mínimo

Propagación perezosa