La descomposición de la raíz cuadrada es una técnica general, mientras que el algoritmo de Mo es una implementación específica. También podría implementar la descomposición sqrt de otras maneras, por ejemplo, agrupando las consultas en lugar de la matriz.
Problema Te dan una matriz y tienes dos operaciones.
- Agregue algún valor a alguna posición de la matriz
- Consultar la suma de elementos en el rango [L, R]
Este es un problema estándar que puede resolver fácilmente usando la descomposición de raíz cuadrada dividiendo la matriz en bloques sqrt y manteniendo una suma de bloques para cada uno.
- ¿Cuáles son los algoritmos para determinar si un punto está dentro de una forma cerrada arbitraria o no?
- ¿Cuáles son algunos de los recursos disponibles para los estudiantes de informática en predicción de la estructura secundaria de ARN?
- ¿Qué algoritmo puedo usar para encontrar el camino más corto en un sistema de variante de tiempo?
- ¿Qué tan útil es el conocimiento de los algoritmos informáticos tradicionales para escribir códigos CFD?
- ¿Qué es el diseño paramétrico y cuáles son algunos ejemplos de él?
Por otro lado, el algoritmo de Mo es un tipo más específico de descomposición sqrt. Es aplicable solo cuando no hay actualizaciones. Se trata de asignar las consultas a los depósitos en función del depósito de los índices de la izquierda y luego ordenarlos en los índices de la derecha. En realidad, hay una variación del algoritmo de Mo que también puede manejar actualizaciones en la complejidad del tiempo O (n ^ (5/3)).
