datos y propagación perezoso en el árbol segmento

Question

parece que hay sólo un buen artículo sobre la propagación perezoso en el árbol del segmento en toda Internet y es: http://www.spoj.pl/forum/viewtopic.php?f=27&t=8296

entendí el concepto de actualización único nodo de consulta y marcando su niño. Pero mi pregunta es ¿qué ocurre si primero consulto el nodo hijo y luego el nodo padre?

En este árbol (junto con la ubicación en el conjunto de pila)

  0->[0 9] 
     1->[0 4] 2->[5 9] 
    3->[0 2] 4->[3 4] 5->[5 7] 6->[8 9] 
..................................... 

primera consulta, si actualizo [0 4], sus datos serán cambiados y su hijo serán marcados. Segunda consulta, es el estado de lectura del segmento [0 9].

Aquí me encuentro con el problema. La implementación de mi árbol de segmentos es tal que el valor de cada nodo es la suma de su hijo izquierdo y derecho. Entonces, cuando actualice el valor del nodo, tengo que actualizarlo, son todos los padres. Para solucionar el problema lógico, ahora estoy actualizando todos los padres del nodo (hasta que llegue a la raíz del árbol). Pero esto está haciendo mella en el rendimiento y mi propósito de utilizar el árbol de segmentos para la actualización de lotes rápidos es que se elimine.

¿Puede alguien explicar por favor, donde me equivoco al usar el árbol de segmentos?

Answer 1

Cuando consulta un nodo en el árbol de segmentos, debe asegurarse de que todos sus antecesores y el nodo en sí se actualicen correctamente. Usted hace esto mientras visita los nodos de consulta.

Al visitar un nodo de consulta, recorre la ruta desde la raíz al nodo de consulta, mientras se ocupa de todas las actualizaciones pendientes. Dado que hay ancestros O (log N) que debe visitar, para cualquier nodo de consulta dado, solo hace el trabajo O (log N).

Aquí está mi código para un árbol de segmento con propagación diferida.

// interval updates, interval queries (lazy propagation) 
const int SN = 256; // must be a power of 2 

struct SegmentTree { 

    // T[x] is the (properly updated) sum of indices represented by node x 
    // U[x] is pending increment for _each_ node in the subtree rooted at x 
    int T[2*SN], U[2*SN]; 

    SegmentTree() { clear(T,0), clear(U,0); } 

    // increment every index in [ia,ib) by incr 
    // the current node is x which represents the interval [a,b) 
    void update(int incr, int ia, int ib, int x = 1, int a = 0, int b = SN) { // [a,b) 
     ia = max(ia,a), ib = min(ib,b); // intersect [ia,ib) with [a,b) 
     if(ia >= ib) return;   // [ia,ib) is empty 
     if(ia == a && ib == b) {  // We push the increment to 'pending increments' 
      U[x] += incr;    // And stop recursing 
      return; 
     } 
     T[x] += incr * (ib - ia);   // Update the current node 
     update(incr,ia,ib,2*x,a,(a+b)/2); // And push the increment to its children 
     update(incr,ia,ib,2*x+1,(a+b)/2, b); 
    } 

    int query(int ia, int ib, int x = 1, int a = 0, int b = SN) { 
     ia = max(ia,a), ib = min(ib,b); // intersect [ia,ib) with [a,b) 
     if(ia >= ib) return 0;   // [ia,ib) is empty 
     if(ia == a && ib == b) 
      return U[x]*(b - a) + T[x]; 

     T[x] += (b - a) * U[x];   // Carry out the pending increments 
     U[2*x] += U[x], U[2*x+1] += U[x]; // Push to the childrens' 'pending increments' 
     U[x] = 0; 

     return query(ia,ib,2*x,a,(a+b)/2) + query(ia,ib,2*x+1,(a+b)/2,b); 
    } 
}; 

Answer 2

Voy a contrastar la operación de actualización lenta de una operación de actualización normal y cómo esto cambia la operación de consulta.

En una operación de actualización simple normal, actualiza la raíz de un árbol y luego actualiza recursivamente solo la parte necesaria del árbol (lo que le da una velocidad de O(log(n))). Si intenta usar la misma lógica para las actualizaciones de un rango, puede ver cómo puede deteriorarse a O(n) (considere los rangos muy amplios y asegúrese de que en su mayoría necesitará actualizar ambas partes del árbol).

Así que para superar esta idea O(n) es actualizar el árbol solo cuando realmente lo necesite (consulta/actualización en el segmento que se actualizó previamente, lo que hace que sus actualizaciones sean flojas). Así que así es como funciona:

• creación de un árbol se mantiene absolutamente igual. La única diferencia menor es que también creas una matriz que contiene información sobre posibles actualizaciones.
• cuando actualiza el nodo del árbol, también verifica si necesita actualizarse (de la operación de actualización anterior) y si lo está - lo actualiza, marque los elementos secundarios que se actualizarán en el futuro y desmarque el nodo (ser flojo)
• Cuando consulta el árbol, también verifica si el nodo necesita actualizarse y si es así actualícelo, márquelo y desmarquelo después.

Aquí hay un ejemplo de actualización y consulta (resolución de consultas de rango máximo). Para un full code - check this article.

void update_tree(int node, int a, int b, int i, int j, int value) { 
    if(lazy[node] != 0) { // This node needs to be updated 
     tree[node] += lazy[node]; // Update it 
     if(a != b) { 
      lazy[node*2] += lazy[node]; // Mark child as lazy 
      lazy[node*2+1] += lazy[node]; // Mark child as lazy 
     } 
     lazy[node] = 0; // Reset it 
    } 

    if(a > b || a > j || b < i) // Current segment is not within range [i, j] 
     return; 

    if(a >= i && b <= j) { // Segment is fully within range 
     tree[node] += value; 
     if(a != b) { // Not leaf node 
      lazy[node*2] += value; 
      lazy[node*2+1] += value; 
     } 
     return; 
    } 

    update_tree(node*2, a, (a+b)/2, i, j, value); // Updating left child 
    update_tree(1+node*2, 1+(a+b)/2, b, i, j, value); // Updating right child 
    tree[node] = max(tree[node*2], tree[node*2+1]); // Updating root with max value 
} 

y consulta:

int query_tree(int node, int a, int b, int i, int j) { 
    if(a > b || a > j || b < i) return -inf; // Out of range 

    if(lazy[node] != 0) { // This node needs to be updated 
     tree[node] += lazy[node]; // Update it 
     if(a != b) { 
      lazy[node*2] += lazy[node]; // Mark child as lazy 
      lazy[node*2+1] += lazy[node]; // Mark child as lazy 
     } 
     lazy[node] = 0; // Reset it 
    } 

    if(a >= i && b <= j) // Current segment is totally within range [i, j] 
     return tree[node]; 

    return max(query_tree(node*2, a, (a+b)/2, i, j), query_tree(1+node*2, 1+(a+b)/2, b, i, j)); 
}