Primero, observe que la operación de actualización de elemento único 2 i es equivalente a realizar 1 ii , llame al resultado v , y luego 0 -vii . Por lo tanto, solo necesitamos implementar las operaciones de consulta de rango y actualización de rango.
Esas operaciones se pueden hacer usando un árbol de segmentos con propagación diferida. Específicamente, deje que cada nodo del árbol de segmentos contenga dos valores: la suma de todos los elementos debajo de él (antes de que se hayan realizado las actualizaciones diferidas pendientes) y el valor diferido [math] \ ell [/ math], que representa una actualización pendiente eso agregaría [math] \ ell, R \ ell, R ^ 2 \ ell, \ ldots [/ math] a los elementos debajo de él, en orden.
Para reducir un valor diferido a los hijos de un nodo: aplique la actualización pendiente al nodo actual agregando [math] \ ell \ sum_ {e = 0} ^ {M-1} R ^ e [/ math] al nodo actual sum (donde [math] M [/ math] es el número de elementos bajo este nodo); agregue [math] \ ell [/ math] al valor perezoso del niño izquierdo; agregue [math] \ ell R ^ L [/ math] al valor perezoso del niño derecho, donde [math] L [/ math] es el número de elementos debajo del niño izquierdo; luego borre [math] \ ell [/ math] para el nodo actual.
- ¿Cómo podemos demostrar que el reconocimiento de objetos basado en la visión es un problema np completo?
- ¿Qué debo hacer para mejorar el pensamiento algorítmico, especialmente para la programación dinámica?
- ¿Podemos implementar una estructura de datos de pila usando una estructura de datos de cola?
- Si un algoritmo se ejecuta en tiempo O (N), pero N no excede una constante, ¿puedo decir que el algoritmo se ejecuta en tiempo constante?
- ¿Cuál es el algoritmo para resolver el buscaminas?
Le dejaré completar los detalles de cómo funcionan las consultas de rango y las actualizaciones de rango.
