Segment Trees III: Generalizacion

El Segment Tree es una estructura tan versátil que puede ser adaptado para resolver una gran variedad de problemas. A continuación vamos a ver como puede extenderse para problemas mas complejos e incluso de varias dimensiones. Para comprender las descripciones de como resolver estos problemas es necesario tener un solido conocimiento de como funciona esta estructura, así que si aun no lo haz hecho, te recomiendo leer primero los posts anteriores sobre el tema.

Mínimo/Máximo elemento

Estas funciones son similares, y en posts anteriores vimos como se pueden implementar.

Mínimo/Máximo y cantidad de veces que aparece.

En este caso tenemos que agregar en cada nodo una variable para almacenar la cantidad de veces que aparece el mínimo/ máximo valor. Y en las operaciones merge y split tener en cuenta esta variable.

Máximo Común Divisor (GCD) / Mínimo Común Múltiplo (LCM)

Esta es una generalización interesante y se obtiene de la misma forma vista hasta ahora, solo hay que llevar en cada nodo el GCD o LCM de los números en el intervalo del arreglo que corresponde.

Suma y producto

En este caso, cada nodo almacenara la suma de los valores en sus hijos, el producto puede ser implementado de forma similar.

Máxima/Mínima suma prefija/sufija

Un prefijo consiste de los primeros k elementos de un intervalo, de forma análoga  un sufijo son los últimos k elementos. La suma máxima prefija de un intervalo es el prefijo con la máxima suma. Por ejemplo, en el arreglo [1, -2, 3, -4] la suma máxima prefija es 2, que es la suma del prefijo [1, -2, 3], ya que ningún otro prefijo tiene mayor suma. Con el Segment Tree podemos encontrar la suma máxima prefija de un intervalo en el arreglo. Para esto en cada nodo colocaremos una variable para almacenar la máxima suma prefija del intervalo que representa, y otra con la suma total de ese intervalo (la suma de la suma de sus hijos). Para encontrar la máxima suma prefija en un nodo que no sea hoja, notamos que el prefijo de suma máxima termina dentro del intervalo del nodo izquierdo, o dentro del intervalo del nodo derecho. En el primer caso, tomamos el valor de la máxima suma prefija del nodo izquierdo. En el segundo caso, sumamos el valor de la suma total del nodo izquierdo con el valor de la máxima suma prefija del nodo derecho. El máximo de estos dos, es el que asumimos como la máxima suma prefija en el intervalo. El mismo concepto puede ser aplicado para calcular sumas máximas/mínimas de sufijos.

Consulta vertical

Este problema consiste en dado un punto x y una serie de intervalos [l, r], determinar cuantos intervalos contienen al punto x. En este caso, formamos el Segment Tree con el tamaño del máximo r. Cada intervalo lo agregamos al árbol sumando 1 en el intervalo que representa. Del mismo modo podemos eliminar intervalos restando 1 al intervalo que representa. Finalmente, para responder las consultas, buscamos el nodo hoja que representa la coordenada x, y luego sumamos los valores en los nodos en el camino de ese nodo hasta la raíz.

Extensión a dos dimensiones

Los Segment Trees pueden ser extendidos a dos o mas dimensiones en una forma bastante natural. Dado una matriz, podríamos calcular el menor elemento en el rectángulo especificado. Para resolver este problema, podemos comenzar con un Segment Tree de una dimensión en el cual cada nodo hoja representa una fila de la matriz, y los demás nodos los intervalos contiguos de filas. Ahora en cada nodo en vez de almacenar variables sobre la información de los elementos, almacenaremos un Segment Tree de una dimensión en el cual cada nodo hoja representa la intersección de una columna con el conjunto de filas que representa el nodo que lo contiene. En este caso las operaciones serian de O(log n × log m)

Y esto no es todo!

El Segment Tree puede ser generalizado a cualquier operación binaria asociativa. Esto significa que, tomando como ejemplo la multiplicación  (a×b)×c = a×(b×c). De esta manera podemos extender los Segment Tree para resolver muchísimos tipos de problemas en varias dimensiones.

Referencias

en.wikipedia.org/wiki/Segment_tree

wcipeg.com/wiki/Segment_tree

comeoncodeon.wordpress.com/2009/09/15/segment-trees/

letuskode.blogspot.com/2013/01/segtrees.html

p–np.blogspot.com/2011/07/segment-tree.html

www.algorithmist.com/index.php/Segmented_Trees

Problemas

www.spoj.com/problems/KGSS/

www.spoj.com/problems/ORDERSET/

www.spoj.com/problems/GSS1/

www.spoj.com/problems/GSS2/

www.spoj.com/problems/GSS3/

www.spoj.com/problems/IOPC1207/

Anuncios

Comentar

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s