Dada una array arr[] de N enteros, la tarea es realizar las siguientes dos consultas:
- máximo (inicio, final) : Imprime el número máximo de elementos de Fibonacci en el subarreglo de principio a fin
- update(i, x) : agregue x al elemento de array al que hace referencia el índice de array i , es decir: arr[i] = x
Nota: El siguiente ejemplo consiste en una indexación basada en 0.
Ejemplo:
Entrada: arr = [1, 3, 5, 7, 9, 11]
Consulta 1: Máximo (Inicio = 1, Fin = 3)
Consulta 2: Actualización (3, 8) es decir, arr[3] = 8
Salida:
Máximo Fibonacci número en el rango dado = 5
Número máximo de Fibonacci actualizado en el rango dado = 8
Explicación:
En la Consulta Máxima, el subconjunto [1…3]
tiene 2 Fibonacci 3 y 5 a saber. {3, 5, 7}
Por lo tanto, 5 es el número máximo de Fibonacci en el rango dado.
En la consulta de actualización, el valor en el índice 3 se actualiza
a 8, la array arr ahora es, [1, 3, 5, 8, 9, 11]
En la consulta máxima actualizada, la array secundaria [1…3]
tiene todos 3 números de Fibonacci 3, 5 y 8 a saber. [3, 5, 8]
Por lo tanto, 8 es el número máximo de Fibonacci en el rango dado.
Enfoque sencillo:
Una solución simple es ejecutar un ciclo de l a r y calcular el número máximo de Fibonacci de todos los elementos en el rango dado. Para actualizar un valor, simplemente haga arr[i] = x. La primera operación toma el tiempo O(N) y la segunda operación toma el tiempo O(1) .
Enfoque eficiente:
aquí, necesitamos realizar operaciones en tiempo O (Log N ) para que podamos usar Segment Tree para realizar ambas operaciones en tiempo O (Log N) .
Representación de árboles de segmentos:
1. Los Nodes hoja son los elementos de la array de entrada.
2. Cada Node interno representa el número máximo de Fibonacci de todos sus Nodes secundarios o -1 si no existe ningún número de Fibonacci en el rango.
Se utiliza una representación de array de árbol para representar árboles de segmento. Para cada Node en el índice i, el hijo izquierdo está en el índice 2*i+1 , el hijo derecho en el índice 2*i+2 y el padre está en el índice (i-1)/2.
Construcción del árbol de segmentos a partir de una array dada:
comenzamos con un segmento arr[0 . . . n-1], y cada vez que dividimos el segmento actual en dos mitades (si aún no se ha convertido en un segmento de longitud 1), y luego llamamos al mismo procedimiento en ambas mitades, y para cada uno de esos segmentos, almacenamos el máximo Valor de número de Fibonacci o -1 en un Node de árbol de segmentos. Todos los niveles del árbol de segmentos construido se llenarán por completo excepto el último nivel. Además, el árbol será un árbol binario completo porque siempre dividimos los segmentos en dos mitades en cada nivel. Dado que el árbol construido siempre es un árbol binario completo con n hojas, habrá n-1 Nodes internos. Entonces, el total de Nodes será 2*n – 1 . La altura del árbol del segmento será log 2 N. Dado que el árbol se representa mediante una array y se debe mantener la relación entre los índices principal y secundario, el tamaño de la memoria asignada para el árbol de segmentos será 2*( 2 ceil(log2n) ) – 1 .
Para verificar los números de Fibonacci, podemos construir una tabla hash usando programación dinámica que contenga todos los números de Fibonacci menores o iguales al valor máximo que arr puede tomar, digamos MAX, que se usará para probar un número en tiempo O (1).
Luego hacemos una consulta de rango en el árbol de segmentos para averiguar los max_set_bits para el rango dado y generar el valor correspondiente.
A continuación se muestra la implementación del enfoque anterior:
CPP
// CPP code for range maximum query and updates
#include <bits/stdc++.h>
using namespace std;
set<int> fibonacci;
// A utility function to get the
// middle index of given range.
int getMid(int s, int e)
{
return s + (e - s) / 2;
}
// Function to create hash table
// to check Fibonacci numbers
void createHash(int maxElement)
{
int prev = 0, curr = 1;
fibonacci.insert(prev);
fibonacci.insert(curr);
while (curr <= maxElement) {
int temp = curr + prev;
fibonacci.insert(temp);
prev = curr;
curr = temp;
}
}
/* A recursive function to get the sum of
values in given range of the array.
The following are parameters for this
function.
st -> Pointer to segment tree
node -> Index of current node in
the segment tree .
ss & se -> Starting and ending indexes
of the segment represented
by current node, i.e., st[node]
l & r -> Starting and ending indexes
of range query */
int MaxUtil(int* st, int ss, int se, int l,
int r, int node)
{
// If segment of this node is completely
// part of given range, then return
// the max of segment
if (l <= ss && r >= se)
return st[node];
// If segment of this node does not
// belong to given range
if (se < l || ss > r)
return -1;
// If segment of this node is partially
// the part of given range
int mid = getMid(ss, se);
return max(MaxUtil(st, ss, mid, l, r,
2 * node + 1),
MaxUtil(st, mid + 1, se, l,
r, 2 * node + 2));
}
/* A recursive function to update the nodes which
have the given index in their range. The following
are parameters st, ss and se are same as defined
above index -> index of the element to be updated.*/
void updateValue(int arr[], int* st, int ss, int se,
int index, int value, int node)
{
if (index < ss || index > se) {
cout << "Invalid Input" << endl;
return;
}
if (ss == se) {
// update value in array and in segment tree
arr[index] = value;
if (fibonacci.find(value) != fibonacci.end())
st[node] = value;
else
st[node] = -1;
}
else {
int mid = getMid(ss, se);
if (index >= ss && index <= mid)
updateValue(arr, st, ss, mid, index,
value, 2 * node + 1);
else
updateValue(arr, st, mid + 1, se,
index, value, 2 * node + 2);
st[node] = max(st[2 * node + 1],
st[2 * node + 2]);
}
return;
}
// Return max of elements in range from
// index l (query start) to r (query end).
int getMax(int* st, int n, int l, int r)
{
// Check for erroneous input values
if (l < 0 || r > n - 1 || l > r) {
printf("Invalid Input");
return -1;
}
return MaxUtil(st, 0, n - 1, l, r, 0);
}
// A recursive function that constructs Segment
// Tree for array[ss..se]. si is index of
// current node in segment tree st
int constructSTUtil(int arr[], int ss, int se,
int* st, int si)
{
// If there is one element in array, store
// it in current node of segment tree and return
if (ss == se) {
if (fibonacci.find(arr[ss])
!= fibonacci.end())
st[si] = arr[ss];
else
st[si] = -1;
return st[si];
}
// If there are more than one elements, then
// recur for left and right subtrees and
// store the max of values in this node
int mid = getMid(ss, se);
st[si]
= max(constructSTUtil(
arr, ss, mid, st,
si * 2 + 1),
constructSTUtil(
arr, mid + 1, se,
st, si * 2 + 2));
return st[si];
}
/* Function to construct segment tree
from given array.
This function allocates memory
for segment tree.*/
int* constructST(int arr[], int n)
{
// Height of segment tree
int x = (int)(ceil(log2(n)));
// Maximum size of segment tree
int max_size = 2 * (int)pow(2, x) - 1;
// Allocate memory
int* st = new int[max_size];
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0);
// Return the constructed segment tree
return st;
}
// Driver code
int main()
{
int arr[] = { 1, 3, 5, 7, 9, 11 };
int n = sizeof(arr) / sizeof(arr[0]);
// find the largest node value
// in the array
int maxEle = *max_element(arr, arr + n);
// creating a set containing
// all fibonacci numbers
// upto the maximum data value
// in the array
createHash(maxEle);
// Build segment tree from given array
int* st = constructST(arr, n);
// Print max of values in array
// from index 1 to 3
cout << "Maximum fibonacci number"
<< " in given range = "
<< getMax(st, n, 1, 3) << endl;
// Update: set arr[1] = 8 and update
// corresponding segment tree nodes.
updateValue(arr, st, 0, n - 1, 3, 8, 0);
// Find max after the value is updated
cout << "Updated Maximum Fibonacci"
<< " number in given range = "
<< getMax(st, n, 1, 3) << endl;
return 0;
}
Java
// Java code for range maximum query and updates
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
class GFG {
static Set<Integer> fibonacci = new HashSet<>();
// A utility function to get the
// middle index of given range.
static int getMid(int s, int e) {
return s + (e - s) / 2;
}
// Function to create hash table
// to check Fibonacci numbers
static void createHash(int maxElement) {
int prev = 0, curr = 1;
fibonacci.add(prev);
fibonacci.add(curr);
while (curr <= maxElement) {
int temp = curr + prev;
fibonacci.add(temp);
prev = curr;
curr = temp;
}
}
/*
* A recursive function to get the sum of
* values in given range of the array.
* The following are parameters for this function.
*
* st -> Pointer to segment tree
* node -> Index of current node
* in the segment tree .
* ss & se -> Starting and ending indexes
* of the segment represented
* by current node, i.e., st[node]
* l & r -> Starting and ending indexes
* of range query
*/
static int MaxUtil(int[] st, int ss, int se,
int l, int r, int node)
{
// If segment of this node is completely
// part of given range, then return
// the max of segment
if (l <= ss && r >= se)
return st[node];
// If segment of this node does not
// belong to given range
if (se < l || ss > r)
return -1;
// If segment of this node is partially
// the part of given range
int mid = getMid(ss, se);
return Math.max(MaxUtil(st, ss, mid, l, r, 2 * node + 1),
MaxUtil(st, mid + 1, se, l, r, 2 * node + 2));
}
/*
* A recursive function to update the nodes which
* have the given index in their range. The following
* are parameters st, ss and se are same as defined
* above index -> index of the element to be updated.
*/
static void updateValue(int arr[], int[] st, int ss, int se,
int index, int value, int node) {
if (index < ss || index > se) {
System.out.println("Invalid Input");
return;
}
if (ss == se) {
// update value in array and in segment tree
arr[index] = value;
if (fibonacci.contains(value))
st[node] = value;
else
st[node] = -1;
} else {
int mid = getMid(ss, se);
if (index >= ss && index <= mid)
updateValue(arr, st, ss, mid, index,
value, 2 * node + 1);
else
updateValue(arr, st, mid + 1, se,
index, value, 2 * node + 2);
st[node] = Math.max(st[2 * node + 1], st[2 * node + 2]);
}
return;
}
// Return max of elements in range from
// index l (query start) to r (query end).
static int getMax(int[] st, int n, int l, int r)
{
// Check for erroneous input values
if (l < 0 || r > n - 1 || l > r)
{
System.out.printf("Invalid Input\n");
return -1;
}
return MaxUtil(st, 0, n - 1, l, r, 0);
}
// A recursive function that constructs Segment
// Tree for array[ss..se]. si is index of
// current node in segment tree st
static int constructSTUtil(int arr[], int ss, int se,
int[] st, int si)
{
// If there is one element in array, store
// it in current node of segment tree and return
if (ss == se) {
if (fibonacci.contains(arr[ss]))
st[si] = arr[ss];
else
st[si] = -1;
return st[si];
}
// If there are more than one elements, then
// recur for left and right subtrees and
// store the max of values in this node
int mid = getMid(ss, se);
st[si] = Math.max(constructSTUtil(arr, ss, mid, st, si * 2 + 1),
constructSTUtil(arr, mid + 1, se, st, si * 2 + 2));
return st[si];
}
/*
* Function to construct segment tree
* from given array. This function allocates
* memory for segment tree.
*/
static int[] constructST(int arr[], int n)
{
// Height of segment tree
int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));
// Maximum size of segment tree
int max_size = 2 * (int) Math.pow(2, x) - 1;
// Allocate memory
int[] st = new int[max_size];
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0);
// Return the constructed segment tree
return st;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 3, 5, 7, 9, 11 };
int n = arr.length;
// find the largest node value
// in the array
int maxEle = Arrays.stream(arr).max().getAsInt();
// creating a set containing
// all fibonacci numbers
// upto the maximum data value
// in the array
createHash(maxEle);
// Build segment tree from given array
int[] st = constructST(arr, n);
// Print max of values in array
// from index 1 to 3
System.out.println("Maximum fibonacci number in given range = " +
getMax(st, n, 1, 3));
// Update: set arr[1] = 8 and update
// corresponding segment tree nodes.
updateValue(arr, st, 0, n - 1, 3, 8, 0);
// Find max after the value is updated
System.out.println("Updated Maximum fibonacci number in given range = " +
getMax(st, n, 1, 3));
}
}
// This code is contributed by sanjeev2552
Javascript
// JavaScript code for range maximum query and updates
let fibonacci = new Set();
// A utility function to get the
// middle index of given range.
function getMid(s, e)
{
return s + Math.floor((e - s) / 2);
}
// Function to create hash table
// to check Fibonacci numbers
function createHash(maxElement)
{
let prev = 0;
let curr = 1;
fibonacci.add(prev);
fibonacci.add(curr);
while (curr <= maxElement) {
let temp = curr + prev;
fibonacci.add(temp);
prev = curr;
curr = temp;
}
}
/* A recursive function to get the sum of
values in given range of the array.
The following are parameters for this
function.
st -> Pointer to segment tree
node -> Index of current node in
the segment tree .
ss & se -> Starting and ending indexes
of the segment represented
by current node, i.e., st[node]
l & r -> Starting and ending indexes
of range query */
function MaxUtil(st, ss, se, l, r, node)
{
// If segment of this node is completely
// part of given range, then return
// the max of segment
if (l <= ss && r >= se)
return st[node];
// If segment of this node does not
// belong to given range
if (se < l || ss > r)
return -1;
// If segment of this node is partially
// the part of given range
let mid = getMid(ss, se);
return Math.max(MaxUtil(st, ss, mid, l, r, 2 * node + 1),MaxUtil(st, mid + 1, se, l, r, 2 * node + 2));
}
/* A recursive function to update the nodes which
have the given index in their range. The following
are parameters st, ss and se are same as defined
above index -> index of the element to be updated.*/
function updateValue(arr, st, ss, se, index, value, node)
{
if (index < ss || index > se) {
console.log("Invalid Input");
return;
}
if (ss == se) {
// update value in array and in segment tree
arr[index] = value;
if (fibonacci.has(value))
st[node] = value;
else
st[node] = -1;
}
else {
let mid = getMid(ss, se);
if (index >= ss && index <= mid)
updateValue(arr, st, ss, mid, index, value, 2 * node + 1);
else
updateValue(arr, st, mid + 1, se, index, value, 2 * node + 2);
st[node] = Math.max(st[2 * node + 1], st[2 * node + 2]);
}
return;
}
// Return max of elements in range from
// index l (query start) to r (query end).
function getMax(st, n, l, r)
{
// Check for erroneous input values
if (l < 0 || r > n - 1 || l > r) {
console.log("Invalid Input");
return -1;
}
return MaxUtil(st, 0, n - 1, l, r, 0);
}
// A recursive function that constructs Segment
// Tree for array[ss..se]. si is index of
// current node in segment tree st
function constructSTUtil(arr, ss, se, st, si)
{
// If there is one element in array, store
// it in current node of segment tree and return
if (ss == se) {
if (fibonacci.has(arr[ss]))
st[si] = arr[ss];
else
st[si] = -1;
return st[si];
}
// If there are more than one elements, then
// recur for left and right subtrees and
// store the max of values in this node
let mid = getMid(ss, se);
st[si] = Math.max(constructSTUtil(arr, ss, mid, st, si * 2 + 1),constructSTUtil(
arr, mid + 1, se, st, si * 2 + 2));
return st[si];
}
/* Function to construct segment tree
from given array.
This function allocates memory
for segment tree.*/
function constructST(arr, n)
{
// Height of segment tree
let x = Math.floor(Math.ceil(Math.log2(n)));
// Maximum size of segment tree
let max_size = 2 * Math.floor(Math.pow(2, x)) - 1;
// Allocate memory
let st = new Array(max_size).fill(0);
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0);
// Return the constructed segment tree
return st;
}
// Driver code
let arr = [ 1, 3, 5, 7, 9, 11 ];
let n = arr.length;
// find the largest node value
// in the array
let maxEle = Math.max(...arr);
// creating a set containing
// all fibonacci numbers
// upto the maximum data value
// in the array
createHash(maxEle);
// Build segment tree from given array
let st = constructST(arr, n);
// Print max of values in array
// from index 1 to 3
console.log("Maximum fibonacci number in given range = ",getMax(st, n, 1, 3));
// Update: set arr[1] = 8 and update
// corresponding segment tree nodes.
updateValue(arr, st, 0, n - 1, 3, 8, 0);
// Find max after the value is updated
console.log("Updated Maximum Fibonacci number in given range = ", getMax(st, n, 1, 3));
// The code is contributed by Gautam goel (gautamgoelo962)
Número máximo de fibonacci en el rango dado = 5
Número máximo de fibonacci actualizado en el rango dado = 8
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA