Рубрики

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

У нас есть массив arr [0. , , н-1]. Мы должны быть в состоянии эффективно найти минимальное значение от индекса L (начало запроса) до R (конец запроса), где 0 <= L <= R <= n-1 . Рассмотрим ситуацию, когда существует много запросов диапазона.

Пример:

Input:  arr[]   = {7, 2, 3, 0, 5, 10, 3, 12, 18};
        query[] = [0, 4], [4, 7], [7, 8]

Output: Minimum of [0, 4] is 0
        Minimum of [4, 7] is 3
        Minimum of [7, 8] is 12

Простое решение — запустить цикл от L до R и найти минимальный элемент в заданном диапазоне. Это решение занимает O (n) время для запроса в худшем случае.

Другой подход заключается в использовании дерева сегментов . Для дерева сегментов время предварительной обработки равно O (n), а время для минимального диапазона запроса равно O (Logn) . Требуется дополнительное пространство O (n) для хранения дерева сегментов. Сегментное дерево позволяет обновлять также в течение O (Log n) .

Можем ли мы сделать лучше, если мы знаем, что массив является статическим?

Как оптимизировать время запроса, когда нет операций обновления и существует много запросов с минимальным диапазоном?

Ниже приведены разные методы.

Способ 1 (простое решение)
Простое решение заключается в создании просмотра двумерного массива [] [], где поиск записи [i] [j] хранит минимальное значение в диапазоне arr [i..j]. Минимум заданного диапазона теперь можно рассчитать за время O (1).

C ++

// C ++ программа для выполнения минимального интервала запроса за O (1) времени с O (n * n)
// дополнительное пространство и время предварительной обработки O (n * n).
#include<bits/stdc++.h>

using namespace std;

#define MAX 500

  
// lookup [i] [j] будет хранить индекс минимального значения в
// arr [i..j]

int lookup[MAX][MAX];

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

struct Query

{

    int L, R;

};

  
// Заполняет поисковый массив lookup [n] [n] для всех возможных значений
// диапазоны запросов

void preprocess(int arr[], int n)

{

    // Инициализируем lookup [] [] для интервалов длиной 1

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

        lookup[i][i] = i;

  

    // Заполняем остальные записи снизу вверх

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

    {

        for (int j = i+1; j<n; j++)

  

           // Чтобы найти минимум [0,4], мы сравниваем минимум

           // arr [lookup [0] [3]] с arr [4].

           if (arr[lookup[i][j - 1]] < arr[j])

              lookup[i][j] = lookup[i][j - 1];

           else

              lookup[i][j] = j;

    }

}

  
// Печатает минимум заданных m диапазонов запросов в arr [0..n-1]

void RMQ(int arr[], int n, Query q[], int m)

{

    // Заполняем таблицу поиска для всех возможных запросов ввода

    preprocess(arr, n);

  

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

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

    {

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

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

  

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

        cout << "Minimum of [" << L << ", "

             << R << "] is "  << arr[lookup[L][R]] << endl;

    }

}

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

int main()

{

    int a[] = {7, 2, 3, 0, 5, 10, 3, 12, 18};

    int n = sizeof(a)/sizeof(a[0]);

    Query q[] = {{0, 4}, {4, 7}, {7, 8}};

    int m = sizeof(q)/sizeof(q[0]);

    RMQ(a, n, q, m);

    return 0;

}

Джава

// Java-программа для выполнения минимального диапазона запроса
// за O (1) время с O (n * n) лишним пробелом
// и O (n * n) время предварительной обработки.

import java.util.*;

  

class GFG 

{

static int MAX = 500;

  
// lookup [i] [j] собирается сохранить индекс
// минимальное значение в arr [i..j]

static int [][]lookup = new int[MAX][MAX];

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

static class Query

{

    int L, R;

  

    public Query(int L, int R)

    {

        this.L = L;

        this.R = R;

    }

};

  
// Заполняет поисковый массив lookup [n] [n] для
// все возможные значения диапазонов запросов

static void preprocess(int arr[], int n)

{

    // Инициализируем lookup [] [] для

    // интервалы длиной 1

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

        lookup[i][i] = i;

  

    // Заполняем остальные записи снизу вверх

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

    {

        for (int j = i + 1; j < n; j++)

  

        // Найти минимум [0,4],

        // сравниваем минимум

        // arr [lookup [0] [3]] с arr [4].

        if (arr[lookup[i][j - 1]] < arr[j])

            lookup[i][j] = lookup[i][j - 1];

        else

            lookup[i][j] = j;

    }

}

  
// Печатает минимум заданного m запроса
// диапазоны в arr [0..n-1]

static void RMQ(int arr[], int n, 

                Query q[], int m)

{

    // Заполняем таблицу поиска для

    // все возможные входные запросы

    preprocess(arr, n);

  

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

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

    {

        // Левая и правая границы

        // текущего диапазона

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

  

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

        System.out.println("Minimum of [" + L + 

                           ", " + R + "] is "

                            arr[lookup[L][R]]);

    }

}

  
// Код драйвера

public static void main(String[] args)

{

    int a[] = {7, 2, 3, 0, 5, 10, 3, 12, 18};

    int n = a.length;

    Query q[] = {new Query(0, 4), 

                 new Query(4, 7), 

                 new Query(7, 8)};

    int m = q.length;

    RMQ(a, n, q, m);

}

  
// Этот код предоставлен 29AjayKumar

C #

// C # программа для выполнения минимального диапазона запроса
// за O (1) время с O (n * n) лишним пробелом
// и O (n * n) время предварительной обработки.

using System;

  

class GFG 

{

static int MAX = 500;

  
// lookup [i] [j] собирается сохранить индекс
// минимальное значение в arr [i..j]

static int [,]lookup = new int[MAX, MAX];

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

public class Query

{

    public int L, R;

  

    public Query(int L, int R)

    {

        this.L = L;

        this.R = R;

    }

};

  
// Заполняет поисковый массив lookup [n] [n] для
// все возможные значения диапазонов запросов

static void preprocess(int []arr, int n)

{

    // Инициализируем lookup [] [] для

    // интервалы длиной 1

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

        lookup[i, i] = i;

  

    // Заполняем остальные записи снизу вверх

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

    {

        for (int j = i + 1; j < n; j++)

  

        // Найти минимум [0,4],

        // сравниваем минимум

        // arr [lookup [0] [3]] с arr [4].

        if (arr[lookup[i, j - 1]] < arr[j])

            lookup[i, j] = lookup[i, j - 1];

        else

            lookup[i, j] = j;

    }

}

  
// Печатает минимум заданного m запроса
// диапазоны в arr [0..n-1]

static void RMQ(int []arr, int n, 

                Query []q, int m)

{

    // Заполняем таблицу поиска для

    // все возможные входные запросы

    preprocess(arr, n);

  

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

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

    {

        // Левая и правая границы

        // текущего диапазона

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

  

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

        Console.WriteLine("Minimum of [" + L + 

                          ", " + R + "] is "

                           arr[lookup[L, R]]);

    }

}

  
// Код драйвера

public static void Main(String[] args)

{

    int []a = {7, 2, 3, 0, 5, 10, 3, 12, 18};

    int n = a.Length;

    Query []q = {new Query(0, 4), 

                 new Query(4, 7), 

                 new Query(7, 8)};

    int m = q.Length;

    RMQ(a, n, q, m);

}

  
// Этот код предоставлен PrinciRaj1992

Выход:

Minimum of [0, 4] is 0
Minimum of [4, 7] is 3
Minimum of [7, 8] is 12

Этот подход поддерживает запрос в O (1) , но предварительная обработка занимает O (n 2 ) время. Кроме того, этот подход требует O (n 2 ) дополнительного пространства, которое может стать огромным для больших входных массивов.

Метод 2 (Разложение квадратного корня)
Мы можем использовать разложение квадратного корня, чтобы уменьшить пространство, требуемое в вышеуказанном методе.

Предварительная обработка:
1) Разделите диапазон [0, n-1] на различные блоки по √n каждый.
2) Вычислить минимум каждого блока размером √n и сохранить результаты.

Предварительная обработка занимает O (√n * √n) = O (n) время и O (√n) пространство.

Запрос:
1) Чтобы запросить диапазон [L, R], мы берем минимум всех блоков, которые лежат в этом диапазоне. Для левого и правого угловых блоков, которые могут частично перекрываться с заданным диапазоном, мы линейно сканируем их, чтобы найти минимум.

Временная сложность запроса O (√n) . Обратите внимание, что у нас есть минимум прямого доступа к среднему блоку и может быть не более O (√n) средних блоков. Нам может потребоваться отсканировать не более двух угловых блоков, поэтому нам может потребоваться отсканировать 2 * O (√n) элементов угловых блоков. Следовательно, общая временная сложность составляет O (√n) .

См. Технику Разложения Квадрата (или Квадратного Корня) | Установите 1 (Введение) для деталей.

Метод 3 (Алгоритм разреженной таблицы)
Приведенное выше решение требует только O (√n) пространства, но требует O (√n) времени для запроса. Метод разреженных таблиц поддерживает время запроса O (1) с дополнительным пробелом O (n Log n) .

Идея состоит в том, чтобы предварительно вычислить минимум всех подмассивов размера 2 j, где j изменяется от 0 до Log n . Как и в методе 1, мы создаем таблицу поиска. Здесь lookup [i] [j] содержит минимум диапазона, начиная с i и размером 2 j . Например, lookup [0] [3] содержит минимум диапазона [0, 7] (начиная с 0 и размером 2 3 )

Предварительная обработка:
Как заполнить эту таблицу поиска? Идея проста, заполнить снизу вверх, используя ранее вычисленные значения.

Например, чтобы найти минимум диапазона [0, 7], мы можем использовать минимум следующих двух.
а) Минимум диапазона [0, 3]
б) Минимум дальности [4, 7]

На основе приведенного выше примера ниже приведена формула

// If arr[lookup[0][2]] <=  arr[lookup[4][2]], 
// then lookup[0][3] = lookup[0][2]
If arr[lookup[i][j-1]] <= arr[lookup[i+2j-1-1][j-1]]
   lookup[i][j] = lookup[i][j-1]

// If arr[lookup[0][2]] >  arr[lookup[4][2]], 
// then lookup[0][3] = lookup[4][2]
Else 
   lookup[i][j] = lookup[i+2j-1-1][j-1] 

Запрос:
Для любого произвольного диапазона [l, R] нам нужно использовать диапазоны с степенями 2. Идея состоит в том, чтобы использовать ближайшую степень 2. Нам всегда нужно делать не более одного сравнения (сравнивать минимум двух диапазонов, являющихся степенями из 2). Один диапазон начинается с L и заканчивается «L + ближайшая степень-2». Другой диапазон заканчивается на R и начинается с «R — такая же ближайшая степень 2 + 1». Например, если данный диапазон равен (2, 10), мы сравниваем минимум двух диапазонов (2, 9) и (3, 10).

На основе приведенного выше примера ниже приведена формула

// For (2,10), j = floor(Log2(10-2+1)) = 3
j = floor(Log(R-L+1))

// If arr[lookup[0][3]] <=  arr[lookup[3][3]], 
// then RMQ(2,10) = lookup[0][3]
If arr[lookup[L][j]] <= arr[lookup[R-(int)pow(2,j)+1][j]]
   RMQ(L, R) = lookup[L][j]

// If arr[lookup[0][3]] >  arr[lookup[3][3]], 
// then RMQ(2,10) = lookup[3][3]
Else 
   RMQ(L, R) = lookup[R-(int)pow(2,j)+1][j]

Поскольку мы делаем только одно сравнение, временная сложность запроса составляет O (1).

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

C ++

// C ++ программа для выполнения минимального диапазона запросов за O (1) времени с
// O (n Log n) дополнительное пространство и O (n Log n) время предварительной обработки
#include<bits/stdc++.h>

using namespace std;

#define MAX 500

  
// lookup [i] [j] будет хранить индекс минимального значения в
// arr [i..j]. В идеале размер таблицы поиска не должен быть фиксированным и
// должен быть определен с использованием n Log n. Он поддерживается постоянным
// сохранить код простым

int lookup[MAX][MAX];

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

struct Query

{

    int L, R;

};

  
// Заполняет поисковый массив lookup [] [] в порядке снизу вверх.

void preprocess(int arr[], int n)

{

    // Инициализируем M для интервалов с длиной 1

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

        lookup[i][0] = i;

  

    // Вычисляем значения от меньшего к большему интервалу

    for (int j=1; (1<<j)<=n; j++)

    {

        // Вычисляем минимальное значение для всех интервалов с размером 2 ^ j

        for (int i=0; (i+(1<<j)-1) < n; i++)

        

            // Для arr [2] [10] мы сравниваем arr [lookup [0] [3]] и

            // arr [lookup [3] [3]]

            if (arr[lookup[i][j-1]] < arr[lookup[i + (1<<(j-1))][j-1]])

                lookup[i][j] = lookup[i][j-1];

            else

                lookup[i][j] = lookup[i + (1 << (j-1))][j-1];      

        }

    }

}

  
// Возвращает минимум arr [L..R]

int query(int arr[], int L, int R)

{

    // Для [2,10], j = 3

    int j = (int)log2(R-L+1);

  

    // Для [2,10] мы сравниваем arr [lookup [0] [3]] и

    // arr [lookup [3] [3]],

    if (arr[lookup[L][j]] <= arr[lookup[R - (1<<j) + 1][j]])

        return arr[lookup[L][j]];

  

   else return arr[lookup[R - (1<<j) + 1][j]];

}

  
// Печатает минимум заданных m диапазонов запросов в arr [0..n-1]

void RMQ(int arr[], int n, Query q[], int m)

{

    // Заполняет таблицу поиска [n] [Log n]

    preprocess(arr, n);

  

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

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

    {

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

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

  

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

        cout << "Minimum of [" << L << ", "

             << R << "] is "  << query(arr, L, R) << endl;

    }

}

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

int main()

{

    int a[] = {7, 2, 3, 0, 5, 10, 3, 12, 18};

    int n = sizeof(a)/sizeof(a[0]);

    Query q[] = {{0, 4}, {4, 7}, {7, 8}};

    int m = sizeof(q)/sizeof(q[0]);

    RMQ(a, n, q, m);

    return 0;

}

Джава

// Java-программа для выполнения минимального диапазона запроса
// за O (1) время с O (n Log n) лишним пробелом
// и O (n Log n) время предварительной обработки

import java.util.*;

  

class GFG 

{

      

static int MAX = 500;

  
// lookup [i] [j] собирается сохранить индекс
// минимального значения в arr [i..j].
// В идеале размер таблицы поиска не должен быть фиксированным
// и должен быть определен с использованием n Log n.
// Он остается постоянным, чтобы сохранить код простым.

static int [][]lookup = new int[MAX][MAX];

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

static class Query

{

    int L, R;

  

    public Query(int L, int R)

    {

        this.L = L;

        this.R = R;

    }

};

  
// Заполняет поисковый массив lookup [] []
// снизу вверх.

static void preprocess(int arr[], int n)

{

    // Инициализируем M для интервалов

    // с длиной 1

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

        lookup[i][0] = i;

  

    // Вычисляем значения из меньших

    // к большим интервалам

    for (int j = 1; (1 << j) <= n; j++)

    {

        // Вычисляем минимальное значение для

        // все интервалы размером 2 ^ j

        for (int i = 0; (i + (1 << j) - 1) < n; i++)

        

            // Для arr [2] [10] сравниваем

            // arr [lookup [0] [3]] и arr [lookup [3] [3]]

            if (arr[lookup[i][j - 1]] < 

                arr[lookup[i + (1 << (j - 1))][j - 1]])

                lookup[i][j] = lookup[i][j - 1];

            else

                lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1];     

        }

    }

}

  
// Возвращает минимум arr [L..R]

static int query(int arr[], int L, int R)

{

    // Для [2,10], j = 3

    int j = (int)Math.log(R - L + 1);

  

    // Для [2,10] мы сравниваем arr [lookup [0] [3]]

    // и arr [lookup [3] [3]],

    if (arr[lookup[L][j]] <= 

        arr[lookup[R - (1 << j) + 1][j]])

        return arr[lookup[L][j]];

  

    else return arr[lookup[R - (1<<j) + 1][j]];

}

  
// Печатает минимум заданных m диапазонов запросов в arr [0..n-1]

static void RMQ(int arr[], int n, Query q[], int m)

{

    // Заполняет таблицу поиска [n] [Log n]

    preprocess(arr, n);

  

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

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

    {

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

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

  

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

        System.out.println("Minimum of [" + L + ", " + R + 

                           "] is " + query(arr, L, R));

    }

}

  
// Код драйвера

public static void main(String[] args) 

{

    int a[] = {7, 2, 3, 0, 5, 10, 3, 12, 18};

    int n = a.length;

    Query q[] = {new Query(0, 4), 

                 new Query(4, 7), 

                 new Query(7, 8)};

    int m = q.length;

    RMQ(a, n, q, m);

}

  
// Этот код предоставлен Rajput-Ji

python3

# Python3 программа для выполнения минимального диапазона запроса
# за O (1) время с O (n Log n) лишним пробелом
# и O (n Log n) время предварительной обработки

from math import log2

  

MAX = 500

  
# lookup [i] [j] будет хранить индекс
# минимальное значение в arr [i..j].
# В идеале размер таблицы поиска должен
# не исправлено и должно быть определено
# использование n Журнал n. Поддерживается постоянным
# чтобы код был простым.

lookup = [[0 for i in range(500)] 

             for j in range(500)]

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

class Query:

    def __init__(self, l, r):

        self.L = l

        self.R = r

  
# Заполняет поисковый массив lookup [] []
# снизу вверх.

def preprocess(arr: list, n: int):

    global lookup

  

    # Инициализировать M для

    # интервалы с длиной 1

    for i in range(n):

        lookup[i][0] = i

  

    # Вычислить значения из

    # интервалы от меньшего к большему

    j = 1

    while (1 << j) <= n:

  

        # Вычислить минимальное значение для

        # все интервалы размером 2 ^ j

        i = 0

        while i + (1 << j) - 1 < n:

  

            # Для arr [2] [10] мы сравниваем

            # arr [lookup [0] [3]] и

            # arr [lookup [3] [3]]

            if (arr[lookup[i][j - 1]] < 

                arr[lookup[i + (1 << (j - 1))][j - 1]]):

                lookup[i][j] = lookup[i][j - 1]

            else:

                lookup[i][j] = lookup[i + 

                               (1 << (j - 1))][j - 1]

  

            i += 1

        j += 1

  
# Возвращает минимум arr [L..R]

def query(arr: list, L: int, R: int) -> int:

    global lookup

  

    # Для [2,10], j = 3

    j = int(log2(R - L + 1))

  

    # Для [2,10] мы сравниваем

    # arr [lookup [0] [3]] и

    # arr [lookup [3] [3]],

    if (arr[lookup[L][j]] <= 

        arr[lookup[R - (1 << j) + 1][j]]):

        return arr[lookup[L][j]]

    else:

        return arr[lookup[R - (1 << j) + 1][j]]

  
# Печатает минимум данных
# m диапазонов запросов в arr [0..n-1]

def RMQ(arr: list, n: int, q: list, m: int):

  

    # Заполняет таблицу поиска [n] [Log n]

    preprocess(arr, n)

  

    # Один за другим вычислить сумму всех запросов

    for i in range(m):

  

        # Левая и правая границы

        # текущего диапазона

        L = q[i].L

        R = q[i].R

  

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

        print("Minimum of [%d, %d] is %d" % 

                  (L, R, query(arr, L, R)))

  
Код водителя

if __name__ == "__main__":

    a = [7, 2, 3, 0, 5, 10, 3, 12, 18]

    n = len(a)

    q = [Query(0, 4), Query(4, 7), 

                      Query(7, 8)]

    m = len(q)

  

    RMQ(a, n, q, m)

  
# Этот код предоставлен
# sanjeev2552

C #

// C # программа для выполнения минимального диапазона запроса
// за O (1) время с O (n Log n) лишним пробелом
// и O (n Log n) время предварительной обработки

using System;

      

class GFG 

{

      

static int MAX = 500;

  
// lookup [i, j] собирается сохранить индекс
// минимального значения в arr [i..j].
// В идеале размер таблицы поиска не должен быть фиксированным
// и должен быть определен с использованием n Log n.
// Он остается постоянным, чтобы сохранить код простым.

static int [,]lookup = new int[MAX, MAX];

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

public class Query

{

    public int L, R;

  

    public Query(int L, int R)

    {

        this.L = L;

        this.R = R;

    }

};

  
// Заполняет поисковый массив lookup [,]
// снизу вверх.

static void preprocess(int []arr, int n)

{

    // Инициализируем M для интервалов

    // с длиной 1

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

        lookup[i, 0] = i;

  

    // Вычисляем значения из меньших

    // к большим интервалам

    for (int j = 1; (1 << j) <= n; j++)

    {

        // Вычисляем минимальное значение для

        // все интервалы размером 2 ^ j

        for (int i = 0; (i + (1 << j) - 1) < n; i++)

        

            // Для arr [2,10] сравниваем

            // arr [lookup [0,3]] и arr [lookup [3,3]]

            if (arr[lookup[i, j - 1]] < 

                arr[lookup[i + (1 << (j - 1)), j - 1]])

                lookup[i, j] = lookup[i, j - 1];

            else

                lookup[i, j] = lookup[i + (1 << (j - 1)), j - 1];     

        }

    }

}

  
// Возвращает минимум arr [L..R]

static int query(int []arr, int L, int R)

{

    // Для [2,10], j = 3

    int j = (int)Math.Log(R - L + 1);

  

    // Для [2,10] мы сравниваем arr [lookup [0,3]]

    // и arr [lookup [3,3]],

    if (arr[lookup[L, j]] <= 

        arr[lookup[R - (1 << j) + 1,j]])

        return arr[lookup[L, j]];

  

    else return arr[lookup[R - (1 << j) + 1, j]];

}

  
// Печатает минимум заданных m диапазонов запросов в arr [0..n-1]

static void RMQ(int []arr, int n, Query []q, int m)

{

    // Заполняет таблицу поиска [n, Log n]

    preprocess(arr, n);

  

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

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

    {

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

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

  

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

        Console.WriteLine("Minimum of [" + L + ", " + R + 

                          "] is " + query(arr, L, R));

    }

}

  
// Код драйвера

public static void Main(String[] args) 

{

    int []a = {7, 2, 3, 0, 5, 10, 3, 12, 18};

    int n = a.Length;

    Query []q = {new Query(0, 4), 

                 new Query(4, 7), 

                 new Query(7, 8)};

    int m = q.Length;

    RMQ(a, n, q, m);

}

  
// Этот код предоставлен Принчи Сингхом

Выход:

Minimum of [0, 4] is 0
Minimum of [4, 7] is 3
Minimum of [7, 8] is 12

Таким образом, метод разреженной таблицы поддерживает операцию запроса за O (1) времени с O (n Log n) временем предварительной обработки и O (n Log n) пространством.

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

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

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

0.00 (0%) 0 votes