Propagación diferida para actualizaciones de rangos
Aplace las actualizaciones de rangos completos
Propagación diferida para actualizaciones de rangos es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
El problema de las actualizaciones de rangos
¿Qué ocurre si una consulta pide sumar 5 a cada elemento de l a r? Tocar cada hoja cuesta O(n) por actualización, demasiado lento cuando hay muchas actualizaciones de rangos. 😰
La idea de lazy
La propagación perezosa permite que un nodo recuerde un cambio pendiente sin pasarlo todavía a sus hijos. El trabajo se pospone hasta que realmente necesita esos hijos.
Un segundo array para el trabajo pendiente
Junto al árbol mantenemos un array lazy. lazy[node] almacena una actualización que se aplica a todo el rango de ese nodo, pero que aún no se ha propagado hacia abajo.
lazy = [0] * (4 * n)Aplicar a un nodo completo
Cuando una actualización cubre por completo un nodo, ajuste su valor almacenado y acumule el cambio en lazy; después, deténgase. No es necesario descender.
seg[node] += (r - l + 1) * val
lazy[node] += valPropagar hacia abajo antes de descender
Antes de visitar a los hijos, propague hacia abajo cualquier valor lazy pendiente a ambos. Así, los hijos son correctos justo cuando los consulta.
def push_down(node, l, r):
if lazy[node]:
apply(2*node, l, mid)
apply(2*node+1, mid+1, r)
lazy[node] = 0Tres casos por nodo
En cada nodo, el rango de consulta es disjunto, lo cubre por completo o lo cubre parcialmente. Omita, aplique de forma perezosa o recorra recursivamente ambas mitades, respectivamente.
Las actualizaciones lazy siguen siendo logarítmicas
Una actualización de rango solo visita O(log n) nodos porque los nodos cubiertos por completo terminan pronto. Ese es todo el beneficio de usar lazy. ⚡
Las consultas también se propagan hacia abajo
Las consultas de rango también deben propagarse hacia abajo antes de recurrir, para leer los valores actualizados de los hijos. Olvidarlo es el error clásico de la propagación diferida.
Recombinar tras la recursión
Después de actualizar los hijos, recombine el padre a partir de ellos. Esta recombinación hacia arriba mantiene coherente cada nodo interno con su subárbol.
seg[node] = seg[2*node] + seg[2*node+1]Asignación frente a suma
La propagación diferida funciona con muchas operaciones, pero la asignación y la suma se combinan de forma diferente. Determine cómo se combinan dos actualizaciones pendientes antes de implementarlo.
Cuándo merece la pena la propagación diferida
Recurra a la propagación diferida solo cuando realmente necesite actualizaciones de rango. Para actualizaciones puntuales, un árbol de segmentos normal es más sencillo y suficiente.
Comprobación rápida
¿Qué debe ocurrir antes de recurrir a los hijos de un nodo?
Repaso: actualizaciones diferidas
Ha aprendido la propagación diferida: almacenar cambios pendientes, propagar hacia abajo antes de descender, recombinar después y conseguir actualizaciones de rango en O(log n). 🎉
Preguntas frecuentes
¿La lección «Propagación diferida para actualizaciones de rangos» es gratis?
Sí — el texto completo de «Propagación diferida para actualizaciones de rangos» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Propagación diferida para actualizaciones de rangos»?
Aplace las actualizaciones de rangos completos Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Propagación diferida para actualizaciones de rangos»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Árbol de Fenwick para sumas prefijas
- Inversiones con un BIT
- Árbol de segmentos: construcción y consultas
- Propagación diferida para actualizaciones de rangos