Hemos discutido brevemente la tabla dispersa en Consulta mínima de rango (descomposición de raíz cuadrada y tabla dispersa) El
concepto de tabla dispersa se usa para consultas rápidas en un conjunto de datos estáticos (los elementos no cambian). Hace un preprocesamiento para que las consultas puedan ser respondidas de manera eficiente.
Problema de ejemplo 1: consulta de rango mínimo
Tenemos una array arr[0 . . . n-1]. Necesitamos 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
La idea es calcular previamente el mínimo de todos los subarreglos de tamaño 2 j donde j varía de 0 a Log n . Hacemos una tabla lookup[i][j] tal que lookup[i][j] contiene un mínimo de rango a partir de i y de tamaño 2 j . Por ejemplo, la búsqueda [0] [3] contiene un rango mínimo [0, 7] (comenzando con 0 y de tamaño 2 3 )
¿Cómo llenar esta búsqueda o tabla dispersa?
La idea es simple, llenar de abajo hacia arriba utilizando valores previamente calculados. Calculamos rangos con potencia actual de 2 utilizando valores de potencia inferior a dos. Por ejemplo, para encontrar un mínimo de rango [0, 7] (el tamaño del rango es una potencia de 3), podemos usar el mínimo de los siguientes dos.
a) Mínimo de rango [0, 3] (El tamaño del rango es una potencia de 2)
b) Mínimo de rango [4, 7] (El tamaño del rango es una potencia de 2)
Basado en el ejemplo anterior, a continuación se muestra la fórmula,
// Minimum of single element subarrays is same // as the only element. lookup[i][0] = arr[i] // If lookup[0][2] <= lookup[4][2], // then lookup[0][3] = lookup[0][2] If lookup[i][j-1] <= lookup[i+2j-1][j-1] lookup[i][j] = lookup[i][j-1] // If lookup[0][2] > lookup[4][2], // then lookup[0][3] = lookup[4][2] Else lookup[i][j] = lookup[i+2j-1][j-1]
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 el 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 el 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 lookup[2][3] <= lookup[3][3], // then RMQ(2, 10) = lookup[2][3] If lookup[L][j] <= lookup[R-(int)pow(2, j)+1][j] RMQ(L, R) = lookup[L][j] // If lookup[2][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
// using sparse table
#include <bits/stdc++.h>
using namespace std;
#define MAX 500
// lookup[i][j] is going to store 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];
// Fills lookup array lookup[][] in bottom up manner.
void buildSparseTable(int arr[], int n)
{
// Initialize M for the intervals with length 1
for (int i = 0; i < n; i++)
lookup[i][0] = arr[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][7]]
// and arr[lookup[3][10]]
if (lookup[i][j - 1] <
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 L, int R)
{
// Find highest power of 2 that is smaller
// than or equal to count of elements in given
// range. For [2, 10], j = 3
int j = (int)log2(R - L + 1);
// Compute minimum of last 2^j elements with first
// 2^j elements in range.
// For [2, 10], we compare arr[lookup[0][3]] and
// arr[lookup[3][3]],
if (lookup[L][j] <= lookup[R - (1 << j) + 1][j])
return lookup[L][j];
else
return lookup[R - (1 << j) + 1][j];
}
// Driver program
int main()
{
int a[] = { 7, 2, 3, 0, 5, 10, 3, 12, 18 };
int n = sizeof(a) / sizeof(a[0]);
buildSparseTable(a, n);
cout << query(0, 4) << endl;
cout << query(4, 7) << endl;
cout << query(7, 8) << endl;
return 0;
}
Java
// Java program to do range minimum query
// using sparse table
import java.io.*;
class GFG {
static int MAX =500;
// lookup[i][j] is going to store 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];
// Fills lookup array lookup[][] in bottom up manner.
static void buildSparseTable(int arr[], int n)
{
// Initialize M for the intervals with length 1
for (int i = 0; i < n; i++)
lookup[i][0] = arr[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][7]]
// and arr[lookup[3][10]]
if (lookup[i][j - 1] <
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 L, int R)
{
// Find highest power of 2 that is smaller
// than or equal to count of elements in given
// range. For [2, 10], j = 3
int j = (int)Math.log(R - L + 1);
// Compute minimum of last 2^j elements with first
// 2^j elements in range.
// For [2, 10], we compare arr[lookup[0][3]] and
// arr[lookup[3][3]],
if (lookup[L][j] <= lookup[R - (1 << j) + 1][j])
return lookup[L][j];
else
return lookup[R - (1 << j) + 1][j];
}
// Driver program
public static void main (String[] args)
{
int a[] = { 7, 2, 3, 0, 5, 10, 3, 12, 18 };
int n = a.length;
buildSparseTable(a, n);
System.out.println(query(0, 4));
System.out.println(query(4, 7));
System.out.println(query(7, 8));
}
}
// This code is contributed by vt_m.
Python3
# Python3 program to do range minimum # query using sparse table import math # Fills lookup array lookup[][] in # bottom up manner. def buildSparseTable(arr, n): # Initialize M for the intervals # with length 1 for i in range(0, n): lookup[i][0] = arr[i] j = 1 # Compute values from smaller to # bigger intervals 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][7]] # and arr[lookup[3][10]] if (lookup[i][j - 1] < 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(L, R): # Find highest power of 2 that is smaller # than or equal to count of elements in # given range. For [2, 10], j = 3 j = int(math.log2(R - L + 1)) # Compute minimum of last 2^j elements # with first 2^j elements in range. # For [2, 10], we compare arr[lookup[0][3]] # and arr[lookup[3][3]], if lookup[L][j] <= lookup[R - (1 << j) + 1][j]: return lookup[L][j] else: return lookup[R - (1 << j) + 1][j] # Driver Code if __name__ == "__main__": a = [7, 2, 3, 0, 5, 10, 3, 12, 18] n = len(a) MAX = 500 # lookup[i][j] is going to store 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(MAX)] for j in range(MAX)] buildSparseTable(a, n) print(query(0, 4)) print(query(4, 7)) print(query(7, 8)) # This code is contributed by Rituraj Jain
C#
// C# program to do range minimum query
// using sparse table
using System;
public class GFG {
static int MAX= 500;
// lookup[i][j] is going to store 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];
// Fills lookup array lookup[][] in bottom up manner.
static void buildSparseTable(int []arr, int n)
{
// Initialize M for the intervals with length 1
for (int i = 0; i < n; i++)
lookup[i, 0] = arr[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][7]]
// and arr[lookup[3][10]]
if (lookup[i, j - 1] <
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 L, int R)
{
// Find highest power of 2 that is smaller
// than or equal to count of elements in given
// range. For [2, 10], j = 3
int j = (int)Math.Log(R - L + 1);
// Compute minimum of last 2^j elements with first
// 2^j elements in range.
// For [2, 10], we compare arr[lookup[0][3]] and
// arr[lookup[3][3]],
if (lookup[L, j] <= lookup[R - (1 << j) + 1, j])
return lookup[L, j];
else
return lookup[R - (1 << j) + 1, j];
}
// Driver program
static public void Main ()
{
int []a = { 7, 2, 3, 0, 5, 10, 3, 12, 18 };
int n = a.Length;
buildSparseTable(a, n);
Console.WriteLine(query(0, 4));
Console.WriteLine(query(4, 7));
Console.WriteLine(query(7, 8));
}
}
// This code is contributed by vt_m.
Javascript
<script>
// Javascript program to do range minimum query
// using sparse table
var MAX = 500;
// lookup[i][j] is going to store 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.
var lookup = Array.from(Array(MAX), ()=>Array(MAX));
// Fills lookup array lookup[][] in bottom up manner.
function buildSparseTable(arr, n)
{
// Initialize M for the intervals with length 1
for (var i = 0; i < n; i++)
lookup[i][0] = arr[i];
// Compute values from smaller to bigger intervals
for (var j = 1; (1 << j) <= n; j++) {
// Compute minimum value for all intervals with
// size 2^j
for (var i = 0; (i + (1 << j) - 1) < n; i++) {
// For arr[2][10], we compare arr[lookup[0][7]]
// and arr[lookup[3][10]]
if (lookup[i][j - 1] <
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(L, R)
{
// Find highest power of 2 that is smaller
// than or equal to count of elements in given
// range. For [2, 10], j = 3
var j = parseInt(Math.log2(R - L + 1));
// Compute minimum of last 2^j elements with first
// 2^j elements in range.
// For [2, 10], we compare arr[lookup[0][3]] and
// arr[lookup[3][3]],
if (lookup[L][j] <= lookup[R - (1 << j) + 1][j])
return lookup[L][j];
else
return lookup[R - (1 << j) + 1][j];
}
// Driver program
var a = [7, 2, 3, 0, 5, 10, 3, 12, 18];
var n = a.length;
buildSparseTable(a, n);
document.write( query(0, 4) + "<br>");
document.write( query(4, 7) + "<br>");
document.write( query(7, 8));
// This code is contributed by noob2000.
</script>
Producción
0 3 12
Complejidad de tiempo: O(n*Log)
Espacio auxiliar: O(n*Logn)
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).
Problema de ejemplo 2: consulta de rango GCD
Tenemos una array arr[0 . . . n-1]. Necesitamos encontrar el máximo común divisor en el rango L y R donde 0 <= L <= R <= n-1. Considere una situación en la que hay muchas consultas de rango.
Ejemplos:
Input : arr[] = {2, 3, 5, 4, 6, 8}
queries[] = {(0, 2), (3, 5), (2, 3)}
Output : 1
2
1
Usamos las siguientes propiedades de GCD:
- La función GCD es asociativa [GCD(a, b, c) = GCD(GCD(a, b), c) = GCD(a, GCD(b, c))], podemos calcular GCD de un rango usando GCD de subrangos .
- Si tomamos GCD de un rango superpuesto más de una vez, entonces no cambia la respuesta. Por ejemplo MCD(a, b, c) = MCD(MCD(a, b), MCD(b, c)). Por lo tanto, al igual que el problema de consulta de rango mínimo, solo necesitamos hacer una comparación para encontrar el GCD del rango dado.
Construimos una tabla dispersa usando la misma lógica que la anterior. Después de construir la tabla dispersa, podemos encontrar todos los MCD dividiendo el rango dado en potencias de 2 y sumando el MCD de cada pieza a la respuesta actual.
C++
// C++ program to do range minimum query
// using sparse table
#include <bits/stdc++.h>
using namespace std;
#define MAX 500
// lookup[i][j] is going to store GCD of
// 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 table[MAX][MAX];
// it builds sparse table.
void buildSparseTable(int arr[], int n)
{
// GCD of single element is element itself
for (int i = 0; i < n; i++)
table[i][0] = arr[i];
// Build sparse table
for (int j = 1; j <= log2(n); j++)
for (int i = 0; i <= n - (1 << j); i++)
table[i][j] = __gcd(table[i][j - 1],
table[i + (1 << (j - 1))][j - 1]);
}
// Returns GCD of arr[L..R]
int query(int L, int R)
{
// Find highest power of 2 that is smaller
// than or equal to count of elements in given
// range.For [2, 10], j = 3
int j = (int)log2(R - L + 1);
// Compute GCD of last 2^j elements with first
// 2^j elements in range.
// For [2, 10], we find GCD of arr[lookup[0][3]] and
// arr[lookup[3][3]],
return __gcd(table[L][j], table[R - (1 << j) + 1][j]);
}
// Driver program
int main()
{
int a[] = { 7, 2, 3, 0, 5, 10, 3, 12, 18 };
int n = sizeof(a) / sizeof(a[0]);
buildSparseTable(a, n);
cout << query(0, 2) << endl;
cout << query(1, 3) << endl;
cout << query(4, 5) << endl;
return 0;
}
Java
// Java program to do range minimum query
// using sparse table
import java.util.*;
class GFG
{
static final int MAX = 500;
// lookup[i][j] is going to store GCD of
// 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 [][]table = new int[MAX][MAX];
// it builds sparse table.
static void buildSparseTable(int arr[],
int n)
{
// GCD of single element is
// element itself
for (int i = 0; i < n; i++)
table[i][0] = arr[i];
// Build sparse table
for (int j = 1; j <= n; j++)
for (int i = 0; i <= n - (1 << j); i++)
table[i][j] = __gcd(table[i][j - 1],
table[i + (1 << (j - 1))][j - 1]);
}
// Returns GCD of arr[L..R]
static int query(int L, int R)
{
// Find highest power of 2 that is
// smaller than or equal to count of
// elements in given range.For [2, 10], j = 3
int j = (int)Math.log(R - L + 1);
// Compute GCD of last 2^j elements
// with first 2^j elements in range.
// For [2, 10], we find GCD of
// arr[lookup[0][3]] and arr[lookup[3][3]],
return __gcd(table[L][j],
table[R - (1 << j) + 1][j]);
}
static int __gcd(int a, int b)
{
return b == 0 ? a : __gcd(b, a % b);
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 7, 2, 3, 0, 5, 10, 3, 12, 18 };
int n = a.length;
buildSparseTable(a, n);
System.out.print(query(0, 2) + "\n");
System.out.print(query(1, 3) + "\n");
System.out.print(query(4, 5) + "\n");
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to do range minimum # query using sparse table import math # Fills lookup array lookup[][] in # bottom up manner. def buildSparseTable(arr, n): # GCD of single element is element itself for i in range(0, n): table[i][0] = arr[i] # Build sparse table j = 1 while (1 << j) <= n: i = 0 while i <= n - (1 << j): table[i][j] = math.gcd(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]) i += 1 j += 1 # Returns minimum of arr[L..R] def query(L, R): # Find highest power of 2 that is smaller # than or equal to count of elements in # given range. For [2, 10], j = 3 j = int(math.log2(R - L + 1)) # Compute GCD of last 2^j elements with # first 2^j elements in range. # For [2, 10], we find GCD of arr[lookup[0][3]] # and arr[lookup[3][3]], return math.gcd(table[L][j], table[R - (1 << j) + 1][j]) # Driver Code if __name__ == "__main__": a = [7, 2, 3, 0, 5, 10, 3, 12, 18] n = len(a) MAX = 500 # lookup[i][j] is going to store 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. table = [[0 for i in range(MAX)] for j in range(MAX)] buildSparseTable(a, n) print(query(0, 2)) print(query(1, 3)) print(query(4, 5)) # This code is contributed by Rituraj Jain
C#
// C# program to do range minimum query
// using sparse table
using System;
class GFG
{
static readonly int MAX = 500;
// lookup[i,j] is going to store GCD of
// 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 [,]table = new int[MAX, MAX];
// it builds sparse table.
static void buildSparseTable(int []arr,
int n)
{
// GCD of single element is
// element itself
for (int i = 0; i < n; i++)
table[i, 0] = arr[i];
// Build sparse table
for (int j = 1; j <= n; j++)
for (int i = 0; i <= n - (1 << j); i++)
table[i, j] = __gcd(table[i, j - 1],
table[i + (1 << (j - 1)),
j - 1]);
}
// Returns GCD of arr[L..R]
static int query(int L, int R)
{
// Find highest power of 2 that is
// smaller than or equal to count of
// elements in given range.
// For [2, 10], j = 3
int j = (int)Math.Log(R - L + 1);
// Compute GCD of last 2^j elements
// with first 2^j elements in range.
// For [2, 10], we find GCD of
// arr[lookup[0,3]] and arr[lookup[3,3]],
return __gcd(table[L, j],
table[R - (1 << j) + 1, j]);
}
static int __gcd(int a, int b)
{
return b == 0 ? a : __gcd(b, a % b);
}
// Driver Code
public static void Main(String[] args)
{
int []a = { 7, 2, 3, 0, 5, 10, 3, 12, 18 };
int n = a.Length;
buildSparseTable(a, n);
Console.Write(query(0, 2) + "\n");
Console.Write(query(1, 3) + "\n");
Console.Write(query(4, 5) + "\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to do range minimum query
// using sparse table
let MAX = 500;
// lookup[i][j] is going to store GCD of
// 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 table = new Array(MAX);
for(let i = 0; i < MAX; i++)
{
table[i] = new Array(MAX);
for(let j = 0; j < MAX; j++)
table[i][j] = 0;
}
// it builds sparse table.
function buildSparseTable(arr,n)
{
// GCD of single element is
// element itself
for (let i = 0; i < n; i++)
table[i][0] = arr[i];
// Build sparse table
for (let j = 1; j <= n; j++)
for (let i = 0; i <= n - (1 << j); i++)
table[i][j] = __gcd(table[i][j - 1],
table[i + (1 << (j - 1))][j - 1]);
}
// Returns GCD of arr[L..R]
function query(L,R)
{
// Find highest power of 2 that is
// smaller than or equal to count of
// elements in given range.For [2, 10], j = 3
let j = Math.floor(Math.log(R - L + 1));
// Compute GCD of last 2^j elements
// with first 2^j elements in range.
// For [2, 10], we find GCD of
// arr[lookup[0][3]] and arr[lookup[3][3]],
return __gcd(table[L][j],
table[R - (1 << j) + 1][j]);
}
function __gcd(a,b)
{
return b == 0 ? a : __gcd(b, a % b);
}
// Driver Code
let a = [7, 2, 3, 0, 5, 10, 3, 12, 18];
let n = a.length;
buildSparseTable(a, n);
document.write(query(0, 2) + "<br>");
document.write(query(1, 3) + "<br>");
document.write(query(4, 5) + "<br>");
// This code is contributed by avanitrachhadiya2155
</script>
Producción
1 1 5
Complejidad de tiempo: O(n*Log)
Espacio Auxiliar: O(n*Log)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA