Tenemos una array arr[0 . . . n-1]. Deberíamos poder encontrar de manera eficiente el valor mínimo desde el índice L (inicio de consulta) hasta R (final de consulta) donde 0 <= L <= R <= n-1 . Considere una situación en la que hay muchas consultas de rango.
Ejemplo:
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
Una solución simple es ejecutar un ciclo de L a R y encontrar el elemento mínimo en el rango dado. Esta solución tarda O (n) tiempo para consultar en el peor de los casos.
Otro enfoque es utilizar el árbol de segmentos . Con el árbol de segmentos, el tiempo de preprocesamiento es O(n) y el tiempo para la consulta mínima de rango es O(Logn) . El espacio adicional requerido es O(n) para almacenar el árbol de segmentos. El árbol de segmentos permite actualizaciones también en tiempo O(Log n) .
¿Podemos hacerlo mejor si sabemos que la array es estática?
¿Cómo optimizar el tiempo de consulta cuando no hay operaciones de actualización y hay muchas consultas mínimas de rango?
A continuación se presentan diferentes métodos.
Método 1 (Solución simple)
Una solución simple es crear una búsqueda de array 2D[][] donde una entrada de búsqueda[i][j] almacena el valor mínimo en el rango arr[i..j]. El mínimo de un rango dado ahora se puede calcular en tiempo O(1).
C++
// C++ program to do range
// minimum query in O(1) time with
// O(n*n) extra space and O(n*n)
// preprocessing time.
#include <bits/stdc++.h>
using namespace std;
#define MAX 500
// lookup[i][j] is going to store
// index of minimum value in
// arr[i..j]
int lookup[MAX][MAX];
// Structure to represent a query range
struct Query {
int L, R;
};
// Fills lookup array lookup[n][n]
// for all possible values
// of query ranges
void preprocess(int arr[], int n)
{
// Initialize lookup[][] for the
// intervals with length 1
for (int i = 0; i < n; i++)
lookup[i][i] = i;
// Fill rest of the entries in bottom up manner
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++)
// To find minimum of [0,4],
// we compare minimum
// of arr[lookup[0][3]] with arr[4].
if (arr[lookup[i][j - 1]] < arr[j])
lookup[i][j] = lookup[i][j - 1];
else
lookup[i][j] = j;
}
}
// Prints minimum of given m
// query ranges in arr[0..n-1]
void RMQ(int arr[], int n, Query q[], int m)
{
// Fill lookup table for
// all possible input queries
preprocess(arr, n);
// 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;
// Print sum of current query range
cout << "Minimum of [" << L
<< ", " << R << "] is "
<< arr[lookup[L][R]] << endl;
}
}
// Driver code
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
// Java program to do range minimum query
// in O(1) time with O(n*n) extra space
// and O(n*n) preprocessing time.
import java.util.*;
class GFG {
static int MAX = 500;
// lookup[i][j] is going to store index of
// minimum value in arr[i..j]
static int[][] lookup = new int[MAX][MAX];
// Structure to represent a query range
static class Query {
int L, R;
public Query(int L, int R)
{
this.L = L;
this.R = R;
}
};
// Fills lookup array lookup[n][n] for
// all possible values of query ranges
static void preprocess(int arr[], int n)
{
// Initialize lookup[][] for
// the intervals with length 1
for (int i = 0; i < n; i++)
lookup[i][i] = i;
// Fill rest of the entries in bottom up manner
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++)
// To find minimum of [0,4],
// we compare minimum of
// arr[lookup[0][3]] with arr[4].
if (arr[lookup[i][j - 1]] < arr[j])
lookup[i][j] = lookup[i][j - 1];
else
lookup[i][j] = j;
}
}
// Prints minimum of given m query
// ranges in arr[0..n-1]
static void RMQ(int arr[], int n, Query q[], int m)
{
// Fill lookup table for
// all possible input queries
preprocess(arr, n);
// 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;
// Print sum of current query range
System.out.println("Minimum of [" + L + ", " + R
+ "] is "
+ arr[lookup[L][R]]);
}
}
// Driver Code
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);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to do range
# minimum query in O(1) time with
# O(n*n) extra space and O(n*n)
# preprocessing time.
MAX = 500
# lookup[i][j] is going to store
# index of minimum value in
# arr[i..j]
lookup = [[0 for j in range(MAX)]
for i in range(MAX)]
# Structure to represent
# a query range
class Query:
def __init__(self, L, R):
self.L = L
self.R = R
# Fills lookup array lookup[n][n]
# for all possible values
# of query ranges
def preprocess(arr, n):
# Initialize lookup[][] for the
# intervals with length 1
for i in range(n):
lookup[i][i] = i;
# Fill rest of the entries in
# bottom up manner
for i in range(n):
for j in range(i + 1, n):
# To find minimum of [0,4],
# we compare minimum
# of arr[lookup[0][3]] with arr[4].
if (arr[lookup[i][j - 1]] < arr[j]):
lookup[i][j] = lookup[i][j - 1];
else:
lookup[i][j] = j;
# Prints minimum of given m
# query ranges in arr[0..n-1]
def RMQ(arr, n, q, m):
# Fill lookup table for
# all possible input queries
preprocess(arr, n);
# One by one compute sum of
# all queries
for i in range(m):
# Left and right boundaries
# of current range
L = q[i].L
R = q[i].R;
# Print sum of current query range
print("Minimum of [" + str(L) + ", " +
str(R) + "] is " +
str(arr[lookup[L][R]]))
# Driver code
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);
# This code is contributed by Rutvik_56
C#
// C# program to do range minimum query
// in O(1) time with O(n*n) extra space
// and O(n*n) preprocessing time.
using System;
class GFG {
static int MAX = 500;
// lookup[i][j] is going to store index of
// minimum value in arr[i..j]
static int[, ] lookup = new int[MAX, MAX];
// Structure to represent a query range
public class Query {
public int L, R;
public Query(int L, int R)
{
this.L = L;
this.R = R;
}
};
// Fills lookup array lookup[n][n] for
// all possible values of query ranges
static void preprocess(int[] arr, int n)
{
// Initialize lookup[][] for
// the intervals with length 1
for (int i = 0; i < n; i++)
lookup[i, i] = i;
// Fill rest of the entries in bottom up manner
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
// To find minimum of [0,4],
// we compare minimum of
// arr[lookup[0][3]] with arr[4].
if (arr[lookup[i, j - 1]] < arr[j])
lookup[i, j] = lookup[i, j - 1];
else
lookup[i, j] = j;
}
}
// Prints minimum of given m query
// ranges in arr[0..n-1]
static void RMQ(int[] arr, int n, Query[] q, int m)
{
// Fill lookup table for
// all possible input queries
preprocess(arr, n);
// 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;
// Print sum of current query range
Console.WriteLine("Minimum of [" + L + ", " + R
+ "] is "
+ arr[lookup[L, R]]);
}
}
// Driver Code
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);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to do range minimum query
// in O(1) time with O(n*n) extra space
// and O(n*n) preprocessing time
let MAX = 500;
// lookup[i][j] is going to store index of
// minimum value in arr[i..j]
let lookup = new Array(MAX);
for(let i = 0; i < MAX; i++)
{
lookup[i] = new Array(MAX);
for(let j = 0; j < MAX; j++)
lookup[i][j] = 0;
}
// Structure to represent a query range
class Query
{
constructor(L, R)
{
this.L = L;
this.R = R;
}
}
// Fills lookup array lookup[n][n] for
// all possible values of query ranges
function preprocess(arr, n)
{
// Initialize lookup[][] for
// the intervals with length 1
for (let i = 0; i < n; i++)
lookup[i][i] = i;
// Fill rest of the entries in bottom up manner
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++)
// To find minimum of [0,4],
// we compare minimum of
// arr[lookup[0][3]] with arr[4].
if (arr[lookup[i][j - 1]] < arr[j])
lookup[i][j] = lookup[i][j - 1];
else
lookup[i][j] = j;
}
}
// Prints minimum of given m query
// ranges in arr[0..n-1]
function RMQ(arr,n,q,m)
{
// Fill lookup table for
// all possible input queries
preprocess(arr, n);
// 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;
// Print sum of current query range
document.write("Minimum of [" + L + ", " + R
+ "] is "
+ arr[lookup[L][R]]+"<br>");
}
}
// Driver Code
let a=[7, 2, 3, 0, 5, 10, 3, 12, 18];
let n = a.length;
let q = [ new Query(0, 4), new Query(4, 7),
new Query(7, 8) ];
let m = q.length;
RMQ(a, n, q, m);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Minimum of [0, 4] is 0 Minimum of [4, 7] is 3 Minimum of [7, 8] is 12
Este enfoque admite consultas en O(1) , pero el preprocesamiento lleva tiempo O(n 2 ) . Además, este enfoque necesita O(n 2 ) espacio adicional que puede volverse enorme para arrays de entrada grandes.
Método 2 (descomposición de raíz cuadrada)
Podemos usar descomposiciones de raíz cuadrada para reducir el espacio requerido en el método anterior.
Preprocesamiento:
1) Divida el rango [0, n-1] en diferentes bloques de √n cada uno.
2) Calcule el mínimo de cada bloque de tamaño √n y almacene los resultados.
El preprocesamiento toma O(√n * √n) = O(n) tiempo y O(√n) espacio.
Consulta:
1) Para consultar un rango [L, R], tomamos un mínimo de todos los bloques que se encuentran en este rango. Para los bloques de las esquinas izquierda y derecha que pueden superponerse parcialmente con el rango dado, los escaneamos linealmente para encontrar el mínimo.
La complejidad temporal de la consulta es O(√n) . Tenga en cuenta que tenemos un mínimo del bloque medio directamente accesible y puede haber como máximo O(√n) bloques medios. Puede haber como máximo dos bloques de esquina que tengamos que escanear, por lo que es posible que tengamos que escanear 2*O(√n) elementos de bloques de esquina. Por lo tanto, la complejidad temporal total es O(√n) .
Consulte la técnica de descomposición Sqrt (o raíz cuadrada) | Conjunto 1 (Introducción) para más detalles.
Método 3 (algoritmo de tabla dispersa)
La solución anterior requiere solo O(√n) espacio pero toma O(√n) tiempo para consultar. El método de tabla dispersa admite el tiempo de consulta O(1) con espacio adicional O(n Log n) .
La idea es precalcular un mínimo de todos los subarreglos de tamaño 2 j donde j varía de 0 a Log n . Al igual que el método 1, hacemos una tabla de búsqueda. Aquí lookup[i][j] contiene un rango mínimo a partir de i y de tamaño 2 j . Por ejemplo, lookup[0][3] contiene un mínimo de rango [0, 7] (comenzando con 0 y de tamaño 2 3 )
Preprocesamiento:
¿Cómo llenar esta tabla de búsqueda? La idea es simple, llenar de abajo hacia arriba utilizando valores previamente calculados.
Por ejemplo, para encontrar un mínimo de rango [0, 7], podemos usar un mínimo de los dos siguientes.
a) Mínimo de rango [0, 3]
b) Mínimo de rango [4, 7]
Basado en el ejemplo anterior, a continuación se muestra la fórmula,
// 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][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][j-1]
Consulta:
Para cualquier rango arbitrario [l, R], necesitamos usar rangos que estén en potencias de 2. La idea es usar la potencia de 2 más cercana. Siempre necesitamos hacer como máximo una comparación (comparar un mínimo de dos rangos que son potencias de 2). Un rango comienza con L y termina con «L + potencia de 2 más cercana». El otro rango termina en R y comienza con «R – misma potencia más cercana de 2 + 1». Por ejemplo, si el rango dado es (2, 10), comparamos un mínimo de dos rangos (2, 9) y (3, 10).
Basado en el ejemplo anterior, a continuación se muestra la fórmula,
// 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]
Como solo hacemos una comparación, la complejidad temporal de la consulta es O(1).
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to do range minimum
// query in O(1) time with
// O(n Log n) extra space and
// O(n Log n) preprocessing time
#include <bits/stdc++.h>
using namespace std;
#define MAX 500
// lookup[i][j] is going to
// store index of minimum value in
// arr[i..j]. Ideally lookup
// table size should not be fixed
// and should be determined using
// n Log n. It is kept
// constant to keep code simple.
int lookup[MAX][MAX];
// Structure to represent a query range
struct Query {
int L, R;
};
// Fills lookup array
// lookup[][] in bottom up manner.
void preprocess(int arr[], int n)
{
// Initialize M for the
// intervals with length 1
for (int i = 0; i < n; i++)
lookup[i][0] = i;
// Compute values from smaller
// to bigger intervals
for (int j = 1; (1 << j) <= n; j++)
{
// Compute minimum value for
// all intervals with size
// 2^j
for (int i = 0; (i + (1 << j) - 1) < n; i++)
{
// For arr[2][10], we
// compare arr[lookup[0][3]]
// and 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];
}
}
}
// Returns minimum of arr[L..R]
int query(int arr[], int L, int R)
{
// For [2,10], j = 3
int j = (int)log2(R - L + 1);
// For [2,10], we compare arr[lookup[0][3]] and
// 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]];
}
// Prints minimum of given
// m query ranges in arr[0..n-1]
void RMQ(int arr[], int n, Query q[], int m)
{
// Fills table lookup[n][Log n]
preprocess(arr, n);
// 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;
// Print sum of current query range
cout << "Minimum of [" << L << ", "
<< R << "] is "
<< query(arr, L, R) << endl;
}
}
// Driver code
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
// Java program to do range minimum query
// in O(1) time with O(n Log n) extra space
// and O(n Log n) preprocessing time
import java.util.*;
class GFG {
static int MAX = 500;
// lookup[i][j] is going to store index
// of minimum value in arr[i..j].
// Ideally lookup table size should not be fixed
// and should be determined using n Log n.
// It is kept constant to keep code simple.
static int[][] lookup = new int[MAX][MAX];
// Structure to represent a query range
static class Query {
int L, R;
public Query(int L, int R)
{
this.L = L;
this.R = R;
}
};
// Fills lookup array lookup[][]
// in bottom up manner.
static void preprocess(int arr[], int n)
{
// Initialize M for the intervals
// with length 1
for (int i = 0; i < n; i++)
lookup[i][0] = i;
// Compute values from smaller
// to bigger intervals
for (int j = 1; (1 << j) <= n; j++)
{
// Compute minimum value for
// all intervals with size 2^j
for (int i = 0;
(i + (1 << j) - 1) < n;
i++)
{
// For arr[2][10], we compare
// arr[lookup[0][3]]
// and 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];
}
}
}
// Returns minimum of arr[L..R]
static int query(int arr[], int L, int R)
{
// For [2,10], j = 3
int j = (int)Math.log(R - L + 1);
// For [2,10], we compare
// arr[lookup[0][3]]
// and 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]];
}
// Prints minimum of given m
// query ranges in arr[0..n-1]
static void RMQ(int arr[], int n,
Query q[], int m)
{
// Fills table lookup[n][Log n]
preprocess(arr, n);
// 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;
// Print sum of current query range
System.out.println("Minimum of ["
+ L + ", " + R
+ "] is "
+ query(arr, L, R));
}
}
// Driver Code
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);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to do range minimum query
# in O(1) time with O(n Log n) extra space
# and O(n Log n) preprocessing time
from math import log2
MAX = 500
# lookup[i][j] is going to store index of
# minimum value in arr[i..j].
# Ideally lookup table size should
# not be fixed and should be determined
# using n Log n. It is kept constant
# to keep code simple.
lookup = [[0 for i in range(500)]
for j in range(500)]
# Structure to represent a query range
class Query:
def __init__(self, l, r):
self.L = l
self.R = r
# Fills lookup array lookup[][]
# in bottom up manner.
def preprocess(arr: list, n: int):
global lookup
# Initialize M for the
# intervals with length 1
for i in range(n):
lookup[i][0] = i
# Compute values from
# smaller to bigger intervals
j = 1
while (1 << j) <= n:
# Compute minimum value for
# all intervals with size 2^j
i = 0
while i + (1 << j) - 1 < n:
# For arr[2][10], we compare
# arr[lookup[0][3]] and
# 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
# Returns minimum of arr[L..R]
def query(arr: list, L: int, R: int) -> int:
global lookup
# For [2,10], j = 3
j = int(log2(R - L + 1))
# For [2,10], we compare
# arr[lookup[0][3]] and
# 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]]
# Prints minimum of given
# m query ranges in arr[0..n-1]
def RMQ(arr: list, n: int, q: list, m: int):
# Fills table lookup[n][Log n]
preprocess(arr, n)
# One by one compute sum of all queries
for i in range(m):
# Left and right boundaries
# of current range
L = q[i].L
R = q[i].R
# Print sum of current query range
print("Minimum of [%d, %d] is %d" %
(L, R, query(arr, L, R)))
# Driver Code
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)
# This code is contributed by
# sanjeev2552
C#
// C# program to do range minimum query
// in O(1) time with O(n Log n) extra space
// and O(n Log n) preprocessing time
using System;
class GFG {
static int MAX = 500;
// lookup[i,j] is going to store index
// of minimum value in arr[i..j].
// Ideally lookup table size should not be fixed
// and should be determined using n Log n.
// It is kept constant to keep code simple.
static int[, ] lookup = new int[MAX, MAX];
// Structure to represent a query range
public class Query {
public int L, R;
public Query(int L, int R)
{
this.L = L;
this.R = R;
}
};
// Fills lookup array lookup[,]
// in bottom up manner.
static void preprocess(int[] arr, int n)
{
// Initialize M for the intervals
// with length 1
for (int i = 0; i < n; i++)
lookup[i, 0] = i;
// Compute values from smaller
// to bigger intervals
for (int j = 1; (1 << j) <= n; j++)
{
// Compute minimum value for
// all intervals with size 2^j
for (int i = 0;
(i + (1 << j) - 1) < n;
i++)
{
// For arr[2,10], we compare
// arr[lookup[0,3]] and 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];
}
}
}
// Returns minimum of arr[L..R]
static int query(int[] arr, int L, int R)
{
// For [2,10], j = 3
int j = (int)Math.Log(R - L + 1);
// For [2,10], we compare arr[lookup[0,3]]
// and 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]];
}
// Prints minimum of given m
// query ranges in arr[0..n-1]
static void RMQ(int[] arr,
int n, Query[] q, int m)
{
// Fills table lookup[n,Log n]
preprocess(arr, n);
// 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;
// Print sum of current query range
Console.WriteLine("Minimum of [" + L + ", " + R
+ "] is " + query(arr, L, R));
}
}
// Driver Code
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);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to do range minimum query
// in O(1) time with O(n Log n) extra space
// and O(n Log n) preprocessing time
const MAX = 500;
// lookup[i][j] is going to store index
// of minimum value in arr[i..j].
// Ideally lookup table size should not be fixed
// and should be determined using n Log n.
// It is kept constant to keep code simple.
let lookup = new Array(MAX).fill(0).map(() => new Array(MAX))
// Structure to represent a query range
class Query {
constructor(L, R) {
this.L = L;
this.R = R;
}
};
// Fills lookup array lookup[][]
// in bottom up manner.
function preprocess(arr, n) {
// Initialize M for the intervals
// with length 1
for (let i = 0; i < n; i++)
lookup[i][0] = i;
// Compute values from smaller
// to bigger intervals
for (let j = 1; (1 << j) <= n; j++) {
// Compute minimum value for
// all intervals with size 2^j
for (let i = 0;
(i + (1 << j) - 1) < n;
i++) {
// For arr[2][10], we compare
// arr[lookup[0][3]]
// and 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];
}
}
}
// Returns minimum of arr[L..R]
function query(arr, L, R) {
// For [2,10], j = 3
let j = Math.floor(Math.log(R - L + 1));
// For [2,10], we compare
// arr[lookup[0][3]]
// and 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]];
}
// Prints minimum of given m
// query ranges in arr[0..n-1]
function RMQ(arr, n, q, m) {
// Fills table lookup[n][Log n]
preprocess(arr, n);
// 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;
// Print sum of current query range
document.write("Minimum of ["
+ L + ", " + R
+ "] is "
+ query(arr, L, R) + "<br>");
}
}
// Driver Code
let a = [7, 2, 3, 0, 5, 10, 3, 12, 18];
let n = a.length;
let q = [new Query(0, 4), new Query(4, 7),
new Query(7, 8)];
let m = q.length;
RMQ(a, n, q, m);
// This code is contributed by Saurabh jaiswal
</script>
Producción
Minimum of [0, 4] is 0 Minimum of [4, 7] is 3 Minimum of [7, 8] is 12
Por lo tanto, el método de tabla dispersa admite la operación de consulta en tiempo O (1) con tiempo de preprocesamiento O (n Log n) y espacio O (n Log n).
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