Segment Tree

Segment Trees

El Segment Tree (o árbol de intervalos) es una estructura de datos que nos permite almacenar información en forma de intervalos, o segmentos. Fue descubierto por J. L. Bentley en 1977, y permite realizar las siguientes operaciones sobre la información de los intervalos:

  • Consultar
  • Modificar un elemento
  • Modificar todos los elementos en un intervalo

Para ver su uso, vamos a ver un problema que puede ser resuelto usando esta estructura.
Supongamos que tenemos el arreglo [5, 2, 4, 6, 11, 8, 3, 2], y tenemos varias operaciones de la forma:

  • Determinar el menor elemento en el intervalo [i, j]
  • Cambiar el elemento en la posición k

Este problema se puede resolver usando Segment Tree en O(log n) para cada operación  Para esto vamos a definir una estructura en forma de árbol binario, donde en cada nodo vamos a llevar la información correspondiente al intervalo [l, r]. En el hijo izquierdo de este nodo almacenaremos la información del intervalo [l, (l + r) / 2] y en el hijo derecho [(l + r) / 2 +1, r]. La raiz del arbol representa el intervalo completo.

Segment Tree correspondiente al arreglo
Segment Tree correspondiente al arreglo

Construcción del árbol

class Node
{
    int left, right, value;
    public Node(int l, int r)
    {
        left = l; right = r;
    }
    public void merge(Node leftChild, Node rightChild)
    {
        if (leftChild == null) value = rightChild.value;
        else if (rightChild == null) value = leftChild.value;
        else value = Math.min(leftChild.value, rightChild.value);
    }
}

El nodo contiene información sobre el intervalo que representa y el valor que tenemos en ese intervalo como mínimo. La operación merge calcula el valor del nodo a partir de los valores de los hijos. En este caso, se almacena en cada nodo el menor valor que aparece en el intervalo que representa ese nodo. El árbol puede ser representado como un arreglo de Node donde cada posición i indica un nodo en el árbol  y la posición 2i representa el hijo izquierdo de este nodo, y la posición 2i+1, el hijo derecho. Este arreglo tiene un tamaño proporcional al tamaño del arreglo original. No es difícil calcular que el mayor tamaño que necesitamos para guardar el árbol es 2^(log2(n)+1), donde n es la cantidad de elementos en el arreglo original. Luego vamos a construir el árbol de manera recursiva. La idea general es llegar primero hasta las hojas y luego regresar el camino hasta la raíz calculando el valor de los nodos padres.

class SegmentTree
{
    int N;
    Node[] tree;
    public SegmentTree(int[] A)
    {
        N = A.length;
        int power = (int) Math.floor(Math.log(A.length) / Math.log(2)) + 1;
        int len = (int) 2 * Math.pow(2, power);
        tree = new Node[len];
        build(1, 0, A.length-1, A);
    }
    private void build(int node, int l, int r, int[] A)
    {
        if (l == r) // nodo hoja
        {
            tree[node] = new Node(l, r);
            tree[node].value = A[l];
            return;
        }
        int leftChild = node*2, rightChild = leftChild+1, mid = (l+r)/2;
        build(leftChild, l, mid, A);      // calcular el valor del hijo izquierdo
        build(rightChild, mid + 1, r, A); // calcular el valor del hijo derecho
        tree[node] = new Node(l, r);
        tree[node].merge(tree[leftChild], tree[rightChild]);
    }
}
Segment Tree construido a partir del arreglo
Segment Tree construido a partir del arreglo

De esta manera, el árbol queda construido en O(n) y podemos comenzar a responder las consultas sobre el menor elemento en un intervalo.

Consultando los intervalos

La operación query la podemos responder con recorrer el camino de la raíz hacia las hojas. Si nos preguntan por el menor elemento en el intervalo [2, 5] visitaremos en el árbol solamente los nodos cuyos intervalos contengan total o parcialmente este intervalo. La secuencia de operaciones es la siguiente:

  1. Comenzamos en la raíz [0, 7]. Como contiene al intervalo, vamos a visitar sus hijos recursivamente.
    1. Visitamos [0, 3]. Como contiene parte del intervalo, visitamos sus hijos recursivamente.
      1. [0,1] no esta en el intervalo, retornamos.
      2. [2, 3] esta incluido completamente en el intervalo de consulta, retornamos su valor.
    2. [4, 7]. Contiene parte del intervalo, visitamos sus hijos.
      1. [4, 5] esta contenido completamente en el intervalo de consulta, retornamos su valor.
      2. [6, 7] no esta dentro del intervalo,  retornamos.

Combinando la información de todos los nodos visitados tendremos el resultado. Siguiendo esta estrategia, el método query quedaría de la siguiente manera:

private Node query(int node, int l, int r, int i, int j)
{
    if (l >= i && r <= j) return tree[node]; // dentro del intervalo
    else if (j < l || i > r) return null;  // fuera del intervalo
    else // parcialmente dentro
    {
        int leftChild = 2*node, rightChild = leftChild+1, mid = (l+r)/2;
        Node a = query(leftChild, l, mid, i, j);    // visitar hijo izquierdo
        Node b = query(rightChild, mid+1, r, i, j); // visitar hijo derecho
        Node temp = new Node(-1, -1); // combinamos la informacion
        temp.merge(a, b);
        return temp;
    }
}
public int query(int i, int j)
{
    Node result = query(1, 0, N-1, i, j);
    return result.value;
}
Nodos visitados en la operacion de consulta
Nodos visitados en la operacion de consulta

Cambiar un elemento

La operación de cambiar un elemento en el arreglo la podemos realizar recorriendo el camino desde la raíz hasta el nodo hoja que corresponde al elemento que queremos cambiar, y luego el camino de regreso hacia la raíz actualizando los valores de todos los padres usando la operación merge.

private void update(int node, int l, int r, int i, int v)
{
    if (l == i && l == r) tree[node].value = v; // nodo hoja
    else if (i < l || i > r) return;        // fuera del intervalo
    else // parcialmente dentro
    {
        int leftChild = 2*node, rightChild = leftChild+1, mid = (l+r)/2;
        update(leftChild, l, mid, i, v);    // visitar hijo izquierdo
        update(rightChild, mid+1, r, i, v); // visitar hijo derecho
        tree[node].merge(tree[leftChild], tree[rightChild]);
    }
}
public void update(int i, int newValue)
{
    update(1, 0, N-1, i, newValue);
}

El Segment Tree es una estructura muy versátil y se puede generalizar fácilmente para soportar distintas operaciones. En próximos posts veremos como modificarlo para soportar operaciones de actualización en intervalos y para resolver otros problemas mas complejos.

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/BRCKTS/

www.spoj.com/problems/DQUERY/

www.spoj.com/problems/FREQUENT/

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