Segment Trees II: lazy updates

Cambiar todos los elementos en un intervalo

Esta operación se puede realizar en O(log n) usando una técnica conocida como lazy updates (actualizaciones perezosas). Esta técnica básicamente actualiza solo los nodos que necesitamos en ese momento, y pospone las demás actualizaciones para el momento en que sean necesarias. Para esto utilizaremos la operación split.

Para llevar a cabo esta operación  el intervalo que queremos actualizar lo marcaremos como pendiente, y en las operaciones de consulta es donde realmente se actualizara el intervalo, propagando las marcas de actualización de un nodo a sus hijos, y actualizando solamente el valor del nodo padre. De esta forma, solo actualizaremos en realidad los nodos que sean consultados, y los que no sean consultados, se quedarán marcados como pendientes. Para esto necesitaremos cambiar un poco la clase Node, y las operaciones de update y query.

class Node
{
    boolean flag;
    int left, right, value, updated;
    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);
    }
    public void split(int nL, int nR)
    {
        if (left != right) // marcar los hijos
        {
            Node leftChild = tree[nL];
            leftChild.flag = true;
            leftChild.updated = updated;
            Node rightChild = tree[nR];
            rightChild.flag = true;
            rightChild.updated = updated;
        }
        flag = false;
        value = updated;
    }
}

Utilizaremos la variable flag para marcar los nodos como pendientes, y el método split para propagar las actualizaciones a los hijos de los nodos que han sido marcados. El método para actualizar el intervalo se encarga de marcar los nodos.

private void update(int node, int l, int r, int i, int j, int v)
{
    int leftChild = 2*node, rightChild = leftChild+1, mid = (l+r)/2;
    if(i <= l && j>= r)
    {
        tree[node].updated = v;
        tree[node].flag = true;
        tree[node].split(leftChild, rightChild);
    }
    else if (j < l || i > r) return;
    else
    {
        update(leftChild, l, mid, i, j, v);
        update(rightChild, mid+1, r, i, j, v);
        tree[node].merge(tree[leftChild], tree[rightChild]);
    }
}
public void update(int i, int j, int newValue)
{
    update(1, 0, N-1, i, j, newValue);
}

El método query es el que se encarga de propagar las actualizaciones por el árbol  sencillamente usando la operación de split en cada nodo que sea visitado al ejecutar la consulta.

private Node query(int node, int l, int r, int i, int j)
{
    int leftChild = 2*node, rightChild = leftChild+1, mid = (l+r)/2;
    if (l >= i && r <= j)
    {
        if (tree[node].flag) tree[node].split(leftChild, rightChild);
        return tree[node];
    }
    if (j < l || i > r) return null;
    if (tree[node].flag) tree[node].split(leftChild, rightChild); // nodo visitado
    Node a = query(leftChild, l, mid, i, j);
    Node b = query(rightChild, mid+1, r, i, j);
    Node temp = new Node(N, N);
    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;
}

De esta forma las operaciones de actualización son propagadas por el árbol  Por ejemplo, si actualizáramos el intervalo [5, 7] a 1 en el arreglo original [5, 2, 4, 6, 11, 8, 3, 2] la secuencia de operaciones seria la siguiente:

  1. comenzamos en la raíz [0-7]
    1. hijo izquierdo [0-3] esta fuera del intervalo, retornar.
    2. hijo derecho [4-7] esta parcialmente dentro, visitar sus hijos.
      1. hijo izquierdo [4-5] esta parcialmente dentro, visitar sus hijos.
        1. hijo izquierdo [4-4] esta fuera, retornar.
        2. hijo derecho [5-5] esta completamente dentro. Marcar como pendiente y hacer split. Se actualiza su valor, y no se propaga porque no hay hijos.
        3. actualizar el valor de [4-5] usando merge. El valor ahora es 1.
      2. hijo derecho [6-7] esta completamente dentro. Marcar como pendiente y hacer split. Se marcan sus hijos como pendientes, y se actualiza el valor a 1.
      3. actualizar el valor de [4-7] usando merge. El valor ahora es 1.
    3. actualizar el valor de [0-7] usando merge. El valor ahora es 1.
Nodos modificados en la operacioon de actualizacion
Nodos modificados en la operación de actualización

En la figura se puede ver el resultado de la operación anterior. Los nodos marcados en gris fueron actualizados en la operación. Los nodos marcados en amarillo fueron marcados como pendientes y el valor entre paréntesis es el nuevo valor que tendrán después de actualizarlos. Dado que en la operación se recorre el camino de la raíz a un nodo, y luego de vuelta, la operación es O(log n). De esta forma podemos realizar de forma eficiente actualizaciones sobre un intervalo. En próximos post vamos a ver como puede ser generalizado el Segment Tree para resolver otros problemas mas complicados.

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

www.spoj.com/problems/SEGSQRSS/

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