1. Árbol de segmentos
Para resolverlo con el árbol de segmentos, necesita saber qué es la propagación diferida.
Cada vez que desea actualizar el intervalo, baja a los nodos que cubren el intervalo, actualiza esos nodos y coloca una bandera en sus hijos para que sepan que necesitan actualizarse. La próxima vez que llegue a los nodos (por ejemplo, cuando realiza consultas) que tienen una bandera, los actualiza y coloca la bandera en sus hijos.
Observe que actualiza solo los nodos que visitaría en cualquier otro problema que use árboles de segmentos (sin propagación diferida) como solución, de modo que la complejidad permanezca O (log N).
Aquí hay un ejemplo simple:
Digamos que tiene una matriz de longitud 2 sobre la cual construye un árbol de segmentos.
El árbol se vería así:
1
/ \
2 3
Ahora, si desea actualizar ambos índices en una matriz dada (eso significa nodos 2 y 3 en el árbol), solo querrá actualizar la raíz, ya que los cubre a ambos, pero desea que los niños sepan que necesitan Para actualizarse. Así que actualiza la raíz y coloca banderas en sus hijos.
La siguiente tarea podría ser consultar el primer índice de la matriz, ahora iría al nodo indexado 2 (ya que es el que cubre el primer índice de la matriz) y verá que debe actualizarse. Entonces, antes de realizar una operación, la actualiza. Si ese nodo tuviera hijos, debería colocar una bandera sobre ellos (propagarlo). Después de realizar esos pasos, realiza su consulta (devuelve el valor).
En una forma simple, cada nodo podría contener 3 valores. Primero sería el valor de ese nodo, segundo sería una bandera que diga si debe actualizarse o no y el tercero sería un nuevo valor en el que debería actualizarse (o un valor que debe agregarse, o lo que sea es lo que necesitas)
Puedes ver esta implementación que encontré (espero que sea correcta):
http://se7so.blogspot.com/2012/12/segment-trees-and-lazy-propagation.html
2. BIT
Este es quizás un poco más complicado de entender, pero es mucho más fácil de codificar.
Deberías mirar este enlace:
Algorithms Weekly por Petr Mitrichev
Asegúrese de entenderlo en papel antes de codificarlo.
- Cómo paralelizar un método recursivo en Java
- ¿Cuáles son todas las áreas donde las estructuras de datos se aplican en escenarios del mundo real?
- ¿Cómo diseñaría un algoritmo para clasificar 100 millones de libros y encontrar duplicados funcionales?
- ¿Por qué algunos algoritmos son más eficientes que otros? ¿Por qué se prefiere la búsqueda binaria sobre la lineal?
- ¿Cuáles son los algoritmos actuales de aprendizaje profundo para la restauración de imágenes?
