Алгоритм МО (разложение квадратного корня запроса) | Набор 1 (Введение)

Опубликовано: 21 Января, 2022

Давайте рассмотрим следующую проблему, чтобы понять алгоритм МО.
Нам дается массив и набор диапазонов запросов, от нас требуется найти сумму каждого диапазона запросов.

Пример:

 Ввод: arr [] = {1, 1, 2, 1, 3, 4, 5, 2, 8};
        запрос [] = [0, 4], [1, 3] [2, 4]
Вывод: сумма элементов arr [] в диапазоне [0, 4] равна 8
        Сумма элементов arr [] в диапазоне [1, 3] равна 4  
        Сумма элементов arr [] в диапазоне [2, 4] равна 6

Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.

A Naive Solution is to run a loop from L to R and calculate the sum of elements in given range for every query [L, R]

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 + " ");
    }
}
  
// 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

Выход:

Sum of [0, 4] is 8
Sum of [1, 3] is 4
Sum of [2, 4] is 6

Временная сложность вышеуказанного решения составляет O (mn).
Идея алгоритма MO состоит в том, чтобы предварительно обработать все запросы, чтобы результат одного запроса можно было использовать в следующем запросе. Ниже приведены шаги.

Пусть a [0… n-1] будет входным массивом, а q [0..m-1] будет массивом запросов.

  1. Сортировка всех запросов таким образом, чтобы объединять запросы со значениями L от 0 до √n - 1 , затем все запросы от √n до 2 * √n - 1 и т. Д. Все запросы в блоке сортируются в порядке возрастания значений R.
  2. Обработайте все запросы один за другим так, чтобы в каждом запросе использовалась сумма, вычисленная в предыдущем запросе.
    • Пусть «сумма» будет суммой предыдущего запроса.
    • Удалите лишние элементы из предыдущего запроса. Например, если предыдущий запрос - [0, 8], а текущий запрос - [3, 9], то мы вычитаем [0], [1] и [2] из суммы
    • Добавить новые элементы текущего запроса. В том же примере, что и выше, мы добавляем [9] к сумме.

Самое замечательное в этом алгоритме то, что на шаге 2 индексная переменная для R изменяется не более O (n * √n) раз на протяжении всего прогона, и то же самое для L изменяет свое значение не более O (m * √n) раз (см. Ниже , после кода, для подробностей). Все эти границы возможны только потому, что запросы сначала сортируются блоками размером √n .

Предварительная обработка занимает время O (m Log m).

Обработка всех запросов занимает O (n * √n) + O (m * √n) = O ((m + n) * √n) раз.

Below is the implementation of the above idea.

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
Алгоритмы

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022
Amazon SDE Sheet: вопросы и ответы на собеседовании
12 Декабря, 2022