Arrays de diferencias para actualizaciones de rangos
Aplique rápidamente muchas operaciones de suma en rangos
Arrays de diferencias 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.
Invierta el problema
Las sumas de prefijos respondían rápidamente a las consultas de intervalos. Un arreglo de diferencias invierte la idea para aplicar rápidamente muchas actualizaciones de intervalos. 🔁
La forma lenta
Sumar un valor a todos los elementos de un intervalo, repetido muchas veces, cuesta O(n) por actualización. Con q actualizaciones, ese costo se dispara.
Almacene los cambios
En lugar de modificar cada celda, registre únicamente dónde comienza un cambio y dónde termina. Marque los extremos, no el centro.
Qué contiene un arreglo de diferencias
Un arreglo de diferencias almacena la diferencia entre cada elemento y el anterior. Modificar una diferencia desplaza todo un tramo posterior.
El truco de las dos marcas
Para sumar v de l a r, sume v en el índice l y reste v en el índice r + 1. Solo dos modificaciones cubren todo el intervalo.
diff[l] += v
diff[r + 1] -= vPor qué se resta
El signo más en l activa el cambio; el signo menos en r + 1 lo vuelve a desactivar. Juntos delimitan la actualización a un solo intervalo.
Aplique todas las actualizaciones de forma eficiente
Cada actualización consiste en solo dos escrituras en el arreglo, por lo que q actualizaciones toman O(q) en total. El trabajo pesado se pospone hasta el final.
Recupere el arreglo final
Después de colocar todas las marcas, calcule una suma de prefijos del arreglo de diferencias. Esa única pasada reconstruye todos los valores finales.
for i in range(1, n):
diff[i] += diff[i - 1]Reserve una posición de seguridad
Haga que el arreglo tenga una celda adicional para que r + 1 nunca quede fuera de sus límites. Esa posición de seguridad adicional evita errores de índice.
El costo total
Dedica O(q) a marcar las actualizaciones y una pasada de O(n) a reconstruir el arreglo. El costo combinado es muy inferior al O(n por q) de la solución ingenua.
Dónde resulta útil
Los arreglos de diferencias son ideales para contar reservas, calcular peajes de carreteras y resolver cualquier problema con muchas operaciones de suma en intervalos y una única lectura final.
Comprobación rápida
Suma v a todos los elementos desde el índice l hasta el índice r.
Resumen
Puede agrupar actualizaciones de intervalos con un arreglo de diferencias: marque l y r + 1, y después calcule una suma de prefijos una sola vez para reconstruir el arreglo. Actualizaciones rápidas y una sola lectura. ✅
Preguntas frecuentes
¿La lección «Arrays de diferencias para actualizaciones de rangos» es gratis?
Sí — el texto completo de «Arrays de diferencias 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 «Arrays de diferencias para actualizaciones de rangos»?
Aplique rápidamente muchas operaciones de suma en rangos 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 «Arrays de diferencias 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
- Construya un array de sumas prefijas
- Sume cualquier rango mediante resta
- Cuente subarrays con una suma objetivo
- Arrays de diferencias para actualizaciones de rangos