Рубрики

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

Рассмотрим следующую проблему, чтобы понять алгоритм МО.

Нам дан массив и набор диапазонов запросов, мы должны найти сумму каждого диапазона запросов.

Пример:

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

Наивное решение — запустить цикл от L до R и вычислить сумму элементов в заданном диапазоне для каждого запроса [L, R]

// Программа для вычисления суммы диапазонов для разных диапазонов
// запросы.
#include <bits/stdc++.h>

using namespace std;

  
// Структура для представления диапазона запроса

struct Query

{

    int L, R;

};

  
// Печатает сумму всех диапазонов запросов. m количество запросов
// n - размер массива.

void printQuerySums(int a[], int n, Query q[], int m)

{

    // Один за другим вычисляем сумму всех запросов

    for (int i=0; i<m; i++)

    {

        // Левая и правая границы текущего диапазона

        int L = q[i].L, R = q[i].R;

  

        // Вычисляем сумму текущего диапазона запросов

        int sum = 0;

        for (int j=L; j<=R; j++)

            sum += a[j];

  

        // Выводим сумму текущего диапазона запросов

        cout << "Sum of [" << L << ", "

            << R << "] is "  << sum << endl;

    }

}

  
// Драйвер программы

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;

}

Выход:

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], a [1] и a [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) времени.

Ниже приведена реализация вышеуказанной идеи на C ++.

// Программа для вычисления суммы диапазонов для разных диапазонов
// запросы
#include <bits/stdc++.h>

using namespace std;

  
// Переменная для представления размера блока. Это сделано глобальным
// так что Compare () сортировки может использовать его.

int block;

  
// Структура для представления диапазона запроса

struct Query

{

    int L, R;

};

  
// Функция используется для сортировки всех запросов так, чтобы все запросы
// одного и того же блока расположены вместе и внутри блока,
// запросы сортируются в порядке возрастания значений R.

bool compare(Query x, Query y)

{

    // Различные блоки, сортировка по блокам.

    if (x.L/block != y.L/block)

        return x.L/block < y.L/block;

  

    // Тот же блок, сортировка по значению R

    return x.R < y.R;

}

  
// Печатает сумму всех диапазонов запросов. m количество запросов
// n - размер массива a [].

void queryResults(int a[], int n, Query q[], int m)

{

    // Найти размер блока

    block = (int)sqrt(n);

  

    // Сортируем все запросы так, чтобы запросы были одинаковыми

    // расположены вместе.

    sort(q, q + m, compare);

  

    // Инициализируем текущий L, текущий R и текущую сумму

    int currL = 0, currR = 0;

    int currSum = 0;

  

    // Обход всех запросов

    for (int i=0; i<m; i++)

    {

        // L и R значения текущего диапазона

        int L = q[i].L, R = q[i].R;

  

        // Удалить лишние элементы предыдущего диапазона. За

        // пример, если предыдущий диапазон [0, 3] и текущий

        // диапазон равен [2, 5], затем вычитаются a [0] и a [1]

        while (currL < L)

        {

            currSum -= a[currL];

            currL++;

        }

  

        // Добавить элементы текущего диапазона

        while (currL > L)

        {

            currSum += a[currL-1];

            currL--;

        }

        while (currR <= R)

        {

            currSum += a[currR];

            currR++;

        }

  

        // Удалить элементы предыдущего диапазона. Например

        // когда предыдущий диапазон равен [0, 10] и текущий диапазон

        // равен [3, 8], затем вычитаются a [9] и a [10]

        while (currR > R+1)

        {

            currSum -= a[currR-1];

            currR--;

        }

  

        // Вывести сумму текущего диапазона

        cout << "Sum of [" << L << ", " << R

             << "] is "  << currSum << endl;

    }

}

  
// Драйвер программы

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;

}

Выход:

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

Выходные данные вышеприведенной программы не выводят результаты запросов в том же порядке, что и входные, поскольку запросы сортируются. Программа может быть легко расширена, чтобы сохранить тот же порядок.

Важные замечания:

  1. Все запросы известны заранее, так что они могут быть предварительно обработаны
  2. Это не может работать для проблем, где у нас есть операции обновления, также смешанные с запросами суммы.
  3. Алгоритм MO можно использовать только для задач запроса, где запрос может быть вычислен по результатам предыдущего запроса. Еще один такой пример — максимум или минимум.

Анализ сложности времени:
Функция в основном запускает цикл for для всех отсортированных запросов. Внутри цикла for есть четыре запроса while, которые перемещают currL и currR.

Сколько сдвигается курсора? Для каждого блока запросы сортируются в порядке возрастания R. Таким образом, для блока currR перемещается в порядке возрастания. В худшем случае, перед началом каждого блока, currR в крайнем правом положении, а текущий блок перемещает его назад в крайнее левое положение. Это означает, что для каждого блока currR перемещается не более O (n) . Поскольку существует O (√n) блоков, общее движение currR равно O (n * √n) .

На сколько курс перемещен? Поскольку все запросы сортируются таким образом, чтобы значения L группировались по блокам, движение равно O (√n), когда мы переходим от одного запроса к другому. Для m запросов общее движение currL равно O (m * √n)

Обратите внимание, что Простое и более эффективное решение для решения этой проблемы — это вычисление суммы префикса для всех элементов от 0 до n-1. Пусть сумма префикса будет сохранена в массиве preSum [] (значение preSum [i] хранит сумму arr [0..i]). Как только мы построили preSum [], мы можем пройти по всем запросам один за другим. Для каждого запроса [L, R] мы возвращаем значение preSum [R] — preSum [L]. Здесь обработка каждого запроса занимает O (1) времени.

Идея этой статьи — представить алгоритм MO на очень простом примере. Вскоре мы будем обсуждать более интересные проблемы, используя алгоритм MO.

Минимальный запрос диапазона (разложение по квадратным корням и разреженная таблица)

Ссылки:
http://blog.anudeep2011.com/mos-algorithm/

Эта статья предоставлена Ruchir Garg . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

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

0.00 (0%) 0 votes