Funcionamiento y necesidad del algoritmo de Mo

El algoritmo de Mo es un algoritmo genérico. Se puede usar en muchos problemas que requieren el procesamiento de consultas de rango en una array estática , es decir, los valores de la array no cambian entre las consultas. En cada consulta, para un rango dado [a, b], la idea es calcular el valor en función de los elementos de la array entre las posiciones de a y b . Dado que la array es estática , las consultas se pueden procesar en cualquier orden y el algoritmo de Mo procesa las consultas en un orden especial que garantiza que el algoritmo funcione de manera eficiente.

Mantiene un rango activo del arreglo, y se conoce en cada momento el resultado de una consulta sobre el rango activo . El algoritmo procesa las consultas una por una y siempre mueve los extremos del rango activo insertando y eliminando elementos.

Complejidad de tiempo: O(N√N*f(N)) , donde la array tiene N elementos y hay N consultas y cada inserción y eliminación de un elemento toma O(f(N)) tiempo.

El truco del algoritmo de Mo es el orden en que se procesan las consultas:

• La array se divide en bloques de k = O(√N) elementos, y una consulta [a ₁ , b ₁ ] se procesa antes que una consulta [a ₂ , b ₂ ] si [a ₁ /k] < [a ₂ /k ] o [a1/k] = [a2/k] y b ₁ < b ₂ es verdadero.
• Por lo tanto, todas las consultas cuyos extremos izquierdos se encuentran en un determinado bloque se procesan una tras otra ordenadas según sus extremos derechos.
• Usando este orden, el algoritmo solo realiza operaciones O(N√N) , debido a que el extremo izquierdo se mueve O(N) veces O(√N) pasos, y el extremo derecho se mueve O(√N) veces O(N) pasos .
• Por lo tanto, ambos extremos se mueven un total de O(N√N) pasos durante el algoritmo.

Ejemplo: considere un problema en el que se da un conjunto de consultas, cada una de las cuales corresponde a un rango en una array, y la tarea es calcular para cada consulta el número de elementos distintos en el rango. En el algoritmo de Mo, las consultas siempre se ordenan de la misma manera, pero depende del problema de cómo se mantiene la respuesta a la consulta. 

• En este problema, la idea es mantener una array cuenta[] donde cuenta[x] indica el número de veces que aparece un elemento x en el rango activo.
• Al pasar de una consulta a otra consulta, el rango activo cambia. Por ejemplo, si el rango actual es {4, 2, 5, 4, 2 , 4, 3, 3, 4} y el siguiente rango es {4, 2, 5, 4, 2, 4, 3 , 3, 4 }. (los rangos están marcados en negrita)
• Habrá tres pasos: el extremo izquierdo se mueve un paso a la derecha y el extremo derecho se mueve dos pasos a la derecha.
• Después de cada paso, la array count[] debe actualizarse.
• Después de agregar un elemento x , aumente el valor de count[x] en 1 , y si count[x] = 1 después de esto también aumente la respuesta a la consulta en 1 .
• De manera similar, después de eliminar un elemento x , disminuya el valor de count[x] en 1 , y si count[x] = 0 después de esto, también disminuya la respuesta a la consulta en 1 .
• En este problema, el tiempo necesario para realizar cada paso es O(1) , por lo que la complejidad temporal total del algoritmo es O(N√N) .