Consideremos el siguiente problema para entender el Algoritmo de MO.
Nos dan una array y un conjunto de rangos de consulta, debemos encontrar la suma de cada rango de consulta.
Ejemplo:
Input: arr[] = {1, 1, 2, 1, 3, 4, 5, 2, 8};
query[] = [0, 4], [1, 3] [2, 4]
Output: Sum of arr[] elements in range [0, 4] is 8
Sum of arr[] elements in range [1, 3] is 4
Sum of arr[] elements in range [2, 4] is 6
Una solución ingenua es ejecutar un ciclo de L a R y calcular la suma de elementos en el rango dado para cada consulta [L, R]
C++
// C++ Program to compute sum of ranges for different range
// queries.
#include <bits/stdc++.h>
using namespace std;
// Structure to represent a query range
struct Query
{
int L, R;
};
// Prints sum of all query ranges. m is number of queries
// n is the size of the array.
void printQuerySums(int a[], int n, Query q[], int m)
{
// One by one compute sum of all queries
for (int i=0; i<m; i++)
{
// Left and right boundaries of current range
int L = q[i].L, R = q[i].R;
// Compute sum of current query range
int sum = 0;
for (int j=L; j<=R; j++)
sum += a[j];
// Print sum of current query range
cout << "Sum of [" << L << ", "
<< R << "] is " << sum << endl;
}
}
// Driver program
int main()
{
int a[] = {1, 1, 2, 1, 3, 4, 5, 2, 8};
int n = sizeof(a)/sizeof(a[0]);
Query q[] = {{0, 4}, {1, 3}, {2, 4}};
int m = sizeof(q)/sizeof(q[0]);
printQuerySums(a, n, q, m);
return 0;
}
Java
// Java Program to compute sum of ranges for different range
// queries.
import java.util.*;
// Class to represent a query range
class Query{
int L;
int R;
Query(int L, int R){
this.L = L;
this.R = R;
}
}
class GFG
{
// Prints sum of all query ranges. m is number of queries
// n is the size of the array.
static void printQuerySums(int a[], int n, ArrayList<Query> q, int m)
{
// One by one compute sum of all queries
for (int i=0; i<m; i++)
{
// Left and right boundaries of current range
int L = q.get(i).L, R = q.get(i).R;
// Compute sum of current query range
int sum = 0;
for (int j=L; j<=R; j++)
sum += a[j];
// Print sum of current query range
System.out.println("Sum of [" + L +
", " + R + "] is " + sum);
}
}
// Driver program
public static void main(String argv[])
{
int a[] = {1, 1, 2, 1, 3, 4, 5, 2, 8};
int n = a.length;
ArrayList<Query> q = new ArrayList<Query>();
q.add(new Query(0,4));
q.add(new Query(1,3));
q.add(new Query(2,4));
int m = q.size();
printQuerySums(a, n, q, m);
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python program to compute sum of ranges for different range queries.
# Function that accepts array and list of queries and print sum of each query
def printQuerySum(arr,Q):
for q in Q: # Traverse through each query
L,R = q # Extract left and right indices
s = 0
for i in range(L,R+1): # Compute sum of current query range
s += arr[i]
print("Sum of",q,"is",s) # Print sum of current query range
# Driver script
arr = [1, 1, 2, 1, 3, 4, 5, 2, 8]
Q = [[0, 4], [1, 3], [2, 4]]
printQuerySum(arr,Q)
#This code is contributed by Shivam Singh
C#
// C# program to compute sum of ranges for
// different range queries
using System;
using System.Collections;
// Class to represent a query range
public class Query
{
public int L;
public int R;
public Query(int L, int R)
{
this.L = L;
this.R = R;
}
}
class GFG{
// Prints sum of all query ranges. m
//is number of queries n is the size
// of the array.
static void printQuerySums(int []a, int n,
ArrayList q, int m)
{
// One by one compute sum of all queries
for(int i = 0; i < m; i++)
{
// Left and right boundaries of
// current range
int L = ((Query)q[i]).L,
R = ((Query)q[i]).R;
// Compute sum of current query range
int sum = 0;
for(int j = L; j <= R; j++)
sum += a[j];
// Print sum of current query range
Console.Write("Sum of [" + L + ", " +
R + "] is " + sum + "\n");
}
}
// Driver code
public static void Main(string []argv)
{
int []a = { 1, 1, 2, 1, 3, 4, 5, 2, 8 };
int n = a.Length;
ArrayList q = new ArrayList();
q.Add(new Query(0, 4));
q.Add(new Query(1, 3));
q.Add(new Query(2, 4));
int m = q.Count;
printQuerySums(a, n, q, m);
}
}
// This code is contributed by pratham76
Javascript
<script>
// Javascript Program to compute sum of ranges for different range
// queries.
// Class to represent a query range
class Query{
constructor(L, R)
{
this.L = L;
this.R = R;
}
}
// Prints sum of all query ranges. m is number of queries
// n is the size of the array.
function printQuerySums(a, n, q, m)
{
// One by one compute sum of all queries
for (let i = 0; i < m; i++)
{
// Left and right boundaries of current range
let L = q[i].L, R = q[i].R;
// Compute sum of current query range
let sum = 0;
for (let j = L; j <= R; j++)
sum += a[j];
// Print sum of current query range
document.write("Sum of [" + L +
", " + R + "] is " + sum+"<br>");
}
}
// Driver program
let a = [1, 1, 2, 1, 3, 4, 5, 2, 8];
let n = a.length;
let q = [];
q.push(new Query(0,4));
q.push(new Query(1,3));
q.push(new Query(2,4));
let m = q.length;
printQuerySums(a, n, q, m);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Sum of [0, 4] is 8 Sum of [1, 3] is 4 Sum of [2, 4] is 6
La complejidad temporal de la solución anterior es O(mn).
La idea del algoritmo de MO es preprocesar todas las consultas para que el resultado de una consulta se pueda usar en la siguiente consulta. A continuación se muestran los pasos.
Sea a[0…n-1] una array de entrada y q[0..m-1] una array de consultas.
- Ordene todas las consultas de manera que las consultas con valores L de 0 a √n – 1 se junten, luego todas las consultas de √n a 2*√n – 1 , y así sucesivamente. Todas las consultas dentro de un bloque se clasifican en orden creciente de valores R.
- Procese todas las consultas una por una de manera que cada consulta utilice la suma calculada en la consulta anterior.
- Sea ‘sum’ la suma de la consulta anterior.
- Eliminar elementos adicionales de la consulta anterior. Por ejemplo, si la consulta anterior es [0, 8] y la consulta actual es [3, 9], restamos a [0], a [1] y a [2] de la suma
- Agregar nuevos elementos de la consulta actual. En el mismo ejemplo anterior, agregamos a[9] a sum.
Lo mejor de este algoritmo es que, en el paso 2, la variable de índice para R cambia como máximo O(n * √n) veces a lo largo de la ejecución y lo mismo para L cambia su valor como máximo O(m * √n) veces (consulte a continuación , después del código, para más detalles). Todos estos límites son posibles solo porque las consultas se ordenan primero en bloques de tamaño √n .
La parte de preprocesamiento toma un tiempo O(m Log m).
El procesamiento de todas las consultas requiere un tiempo O(n * √n) + O(m * √n) = O((m+n) * √n) .
A continuación se muestra la implementación de la idea anterior.
C++
// Program to compute sum of ranges for different range
// queries
#include <bits/stdc++.h>
using namespace std;
// Variable to represent block size. This is made global
// so compare() of sort can use it.
int block;
// Structure to represent a query range
struct Query
{
int L, R;
};
// Function used to sort all queries so that all queries
// of the same block are arranged together and within a block,
// queries are sorted in increasing order of R values.
bool compare(Query x, Query y)
{
// Different blocks, sort by block.
if (x.L/block != y.L/block)
return x.L/block < y.L/block;
// Same block, sort by R value
return x.R < y.R;
}
// Prints sum of all query ranges. m is number of queries
// n is size of array a[].
void queryResults(int a[], int n, Query q[], int m)
{
// Find block size
block = (int)sqrt(n);
// Sort all queries so that queries of same blocks
// are arranged together.
sort(q, q + m, compare);
// Initialize current L, current R and current sum
int currL = 0, currR = 0;
int currSum = 0;
// Traverse through all queries
for (int i=0; i<m; i++)
{
// L and R values of current range
int L = q[i].L, R = q[i].R;
// Remove extra elements of previous range. For
// example if previous range is [0, 3] and current
// range is [2, 5], then a[0] and a[1] are subtracted
while (currL < L)
{
currSum -= a[currL];
currL++;
}
// Add Elements of current Range
while (currL > L)
{
currSum += a[currL-1];
currL--;
}
while (currR <= R)
{
currSum += a[currR];
currR++;
}
// Remove elements of previous range. For example
// when previous range is [0, 10] and current range
// is [3, 8], then a[9] and a[10] are subtracted
while (currR > R+1)
{
currSum -= a[currR-1];
currR--;
}
// Print sum of current range
cout << "Sum of [" << L << ", " << R
<< "] is " << currSum << endl;
}
}
// Driver program
int main()
{
int a[] = {1, 1, 2, 1, 3, 4, 5, 2, 8};
int n = sizeof(a)/sizeof(a[0]);
Query q[] = {{0, 4}, {1, 3}, {2, 4}};
int m = sizeof(q)/sizeof(q[0]);
queryResults(a, n, q, m);
return 0;
}
Java
// Java Program to compute sum of ranges for
// different range queries
import java.util.*;
// Class to represent a query range
class Query{
int L;
int R;
Query(int L, int R){
this.L = L;
this.R = R;
}
}
class MO{
// Prints sum of all query ranges. m is number of queries
// n is size of array a[].
static void queryResults(int a[], int n, ArrayList<Query> q, int m){
// Find block size
int block = (int) Math.sqrt(n);
// Sort all queries so that queries of same blocks
// are arranged together.
Collections.sort(q, new Comparator<Query>(){
// Function used to sort all queries so that all queries
// of the same block are arranged together and within a block,
// queries are sorted in increasing order of R values.
public int compare(Query x, Query y){
// Different blocks, sort by block.
if (x.L/block != y.L/block)
return (x.L < y.L ? -1 : 1);
// Same block, sort by R value
return (x.R < y.R ? -1 : 1);
}
});
// Initialize current L, current R and current sum
int currL = 0, currR = 0;
int currSum = 0;
// Traverse through all queries
for (int i=0; i<m; i++)
{
// L and R values of current range
int L = q.get(i).L, R = q.get(i).R;
// Remove extra elements of previous range. For
// example if previous range is [0, 3] and current
// range is [2, 5], then a[0] and a[1] are subtracted
while (currL < L)
{
currSum -= a[currL];
currL++;
}
// Add Elements of current Range
while (currL > L)
{
currSum += a[currL-1];
currL--;
}
while (currR <= R)
{
currSum += a[currR];
currR++;
}
// Remove elements of previous range. For example
// when previous range is [0, 10] and current range
// is [3, 8], then a[9] and a[10] are subtracted
while (currR > R+1)
{
currSum -= a[currR-1];
currR--;
}
// Print sum of current range
System.out.println("Sum of [" + L +
", " + R + "] is " + currSum);
}
}
// Driver program
public static void main(String argv[]){
ArrayList<Query> q = new ArrayList<Query>();
q.add(new Query(0,4));
q.add(new Query(1,3));
q.add(new Query(2,4));
int a[] = {1, 1, 2, 1, 3, 4, 5, 2, 8};
queryResults(a, a.length, q, q.size());
}
}
// This code is contributed by Ajay
Python3
# Python program to compute sum of ranges for different range queries
import math
# Function that accepts array and list of queries and print sum of each query
def queryResults(arr,Q):
#Q.sort(): # Sort by L
#sort all queries so that all queries in the increasing order of R values .
Q.sort(key=lambda x: x[1])
# Initialize current L, current R and current sum
currL,currR,currSum = 0,0,0
# Traverse through all queries
for i in range(len(Q)):
L,R = Q[i] # L and R values of current range
# Remove extra elements from previous range
# if previous range is [0, 3] and current
# range is [2, 5], then a[0] and a[1] are subtracted
while currL<L:
currSum-=arr[currL]
currL+=1
# Add elements of current range
while currL>L:
currSum+=arr[currL-1]
currL-=1
while currR<=R:
currSum+=arr[currR]
currR+=1
# Remove elements of previous range
# when previous range is [0, 10] and current range
# is [3, 8], then a[9] and a[10] are subtracted
while currR>R+1:
currSum-=arr[currR-1]
currR-=1
# Print the sum of current range
print("Sum of",Q[i],"is",currSum)
arr = [1, 1, 2, 1, 3, 4, 5, 2, 8]
Q = [[0, 4], [1, 3], [2, 4]]
queryResults(arr,Q)
#This code is contributed by Shivam Singh
C#
// C# Program to compute sum of ranges for different range
// queries
using System;
using System.Collections.Generic;
class GFG
{
// Variable to represent block size. This is made global
// so compare() of sort can use it.
public static int block;
// Structure to represent a query range
public struct Query
{
public int L;
public int R;
public Query(int l, int r)
{
L = l;
R = r;
}
}
// Function used to sort all queries so that all queries
// of the same block are arranged together and within a
// block, queries are sorted in increasing order of R
// values.
public class Comparer : IComparer<Query> {
public int Compare(Query x, Query y)
{
int ret = (int)(x.L / block)
.CompareTo((int)(y.L / block));
return ret != 0 ? ret : x.R.CompareTo(y.R);
}
}
// Prints sum of all query ranges. m is number of
// queries n is size of array a[].
static void queryResults(int[] a, int n, List<Query> q,
int m)
{
// Find block size
block = (int)(Math.Sqrt(n));
// Sort all queries so that queries of same blocks
// are arranged together.
q.Sort(new Comparer());
// Initialize current L, current R and current sum
int currL = 0, currR = 0;
int currSum = 0;
// Traverse through all queries
for (int i = 0; i < m; i++) {
// L and R values of current range
int L = q[i].L, R = q[i].R;
// Remove extra elements of previous range. For
// example if previous range is [0, 3] and
// current range is [2, 5], then a[0] and a[1]
// are subtracted
while (currL < L) {
currSum -= a[currL];
currL++;
}
// Add Elements of current Range
while (currL > L) {
currSum += a[currL - 1];
currL--;
}
while (currR <= R) {
currSum += a[currR];
currR++;
}
// Remove elements of previous range. For
// example when previous range is [0, 10] and
// current range is [3, 8], then a[9] and a[10]
// are subtracted
while (currR > R + 1) {
currSum -= a[currR - 1];
currR--;
}
// Print sum of current range
Console.WriteLine("Sum of [{0}, {1}] is {2}", L,
R, currSum);
}
}
// Driver program
static void Main(string[] args)
{
int[] a = { 1, 1, 2, 1, 3, 4, 5, 2, 8 };
int n = a.Length;
List<Query> q = new List<Query>();
q.Add(new Query(0, 4));
q.Add(new Query(1, 3));
q.Add(new Query(2, 4));
int m = q.Count;
queryResults(a, n, q, m);
}
}
// This code is contributed by cavi4762.
Producción:
Sum of [1, 3] is 4 Sum of [0, 4] is 8 Sum of [2, 4] is 6
La salida del programa anterior no imprime los resultados de las consultas en el mismo orden que la entrada, porque las consultas están ordenadas. El programa se puede ampliar fácilmente para mantener el mismo orden.
Observaciones importantes:
- Todas las consultas se conocen de antemano para que puedan ser procesadas previamente.
- No puede funcionar para problemas en los que tenemos operaciones de actualización también combinadas con consultas de suma.
- El algoritmo de MO solo se puede usar para problemas de consulta en los que una consulta se puede calcular a partir de los resultados de la consulta anterior. Un ejemplo más es máximo o mínimo.
Análisis de la complejidad del tiempo:
la función ejecuta principalmente un bucle for para todas las consultas ordenadas. Dentro del bucle for, hay cuatro consultas while que mueven ‘currL’ y ‘currR’.
¿Cuánto currR se mueve? Para cada bloque, las consultas se ordenan en orden creciente de R. Entonces, para un bloque, currR se mueve en orden creciente. En el peor de los casos, antes del comienzo de cada bloque, currR en el extremo derecho y el bloque actual lo mueve hacia atrás en el extremo izquierdo. Esto significa que para cada bloque, currR se mueve como máximo O(n) . Dado que hay O(√n) bloques, el movimiento total de currR es O(n * √n) .
¿Cuánto currL se mueve? Dado que todas las consultas se ordenan de manera que los valores L se agrupan por bloques, el movimiento es O(√n) cuando pasamos de una consulta a otra consulta. Para m consultas, el movimiento total de currL es O(m * √n)
Tenga en cuenta que una solución simple y más eficiente para resolver este problema es calcular la suma de prefijos para todos los elementos de 0 a n-1. Deje que el prefijo sum se almacene en una array preSum[] (El valor de preSum[i] almacena la suma de arr[0..i]). Una vez que hemos construido preSum[], podemos recorrer todas las consultas una por una. Para cada consulta [L, R], devolvemos el valor de preSum[R] – preSum[L]. Aquí el procesamiento de cada consulta lleva tiempo O (1).
Espacio Auxiliar: O(1)
La idea de este artículo es presentar el algoritmo de MO con un ejemplo muy simple. Pronto discutiremos problemas más interesantes usando el algoritmo de MO.
Consulta de rango mínimo (descomposición de raíz cuadrada y tabla dispersa)
Referencias:
http://blog.anudeep2011.com/mos-algorithm/
Este artículo es una contribución de Ruchir Garg . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA