Dada una array arr[] de N enteros, la tarea es realizar las siguientes dos consultas:
- consulta (inicio, final) : imprime la cantidad de números 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
Ejemplos:
Entrada: arr = { 1, 2, 3, 4, 8, 9 }
Consulta 1: consulta (inicio = 0, fin = 4)
Consulta 2: actualización (i = 3, x = 5)
Consulta 3: consulta (inicio = 0, fin = 4)
Salida: 4
5
Explicación
En la consulta 1 , el subarreglo [0…4] tiene 4 números de Fibonacci, a saber. {1, 2, 3, 8}
En la Consulta 2 , el valor en el índice 3 se actualiza a 5, la array arr ahora es, {1, 2, 3, 5, 8, 9}
En la Consulta 3 , el subarreglo [0 …4] tiene 5 números de fibonacci a saber. {1, 2, 3, 5, 8}
Enfoque: para manejar actualizaciones de puntos y consultas de rango, un árbol de segmentos es óptimo para este propósito.
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 arr i . Podemos tomar MAX, que se usará para probar un número en complejidad de tiempo O(1).
Construyendo el árbol de segmentos:
- El problema ahora se reduce a la suma del subarreglo utilizando el problema del árbol de segmentos.
- Ahora, podemos construir el árbol de segmentos donde un Node de hoja se representa como 0 (si no es un número primo) o 1 (si es un número de Fibonacci).
- Los Nodes internos del árbol de segmentos son iguales a la suma de sus Nodes secundarios, por lo tanto, un Node representa los números de Fibonacci totales en el rango de L a R con el rango [L, R] debajo de este Node y el subárbol debajo de él.
Manejo de consultas y actualizaciones de puntos:
- Cada vez que recibimos una consulta de principio a fin, podemos consultar el árbol de segmentos para la suma de los Nodes en el rango de principio a fin, que a su vez representan la cantidad de números de Fibonacci en el rango de principio a fin.
- Para realizar una actualización de punto y para actualizar el valor en el índice i a x, verificamos los siguientes casos:
Deje que el valor anterior de arr i sea y y el nuevo valor sea x.- Caso 1: Fibonacci: si x e y son números
de Fibonacci, la cantidad de números de Fibonacci en el subarreglo no cambia, por lo que solo actualizamos el arreglo y no modificamos el árbol de segmentos - Caso 2: si x e y no son números
de Fibonacci La cantidad de números de Fibonacci en el subarreglo no cambia, así que solo actualizamos el arreglo y no modificamos el árbol de segmentos - Caso 3: si y es un número de Fibonacci pero x no lo es,
el recuento de números de Fibonacci en el subarreglo disminuye, por lo que actualizamos el arreglo y agregamos -1 a cada rango. El índice i que se va a actualizar forma parte del árbol de segmentos. - Caso 4: si y no es un número de Fibonacci pero x es un número
de Fibonacci El recuento de números de Fibonacci en el subarreglo aumenta, por lo que actualizamos el arreglo y agregamos 1 a cada rango. El índice i que se va a actualizar forma parte del árbol de segmentos.
- Caso 1: Fibonacci: si x e y son números
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find number of fibonacci numbers
// in a subarray and performing updates
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
// Function to create hash table
// to check Fibonacci numbers
void createHash(set<int>& hash,
int maxElement)
{
int prev = 0, curr = 1;
hash.insert(prev);
hash.insert(curr);
while (curr <= maxElement) {
int temp = curr + prev;
hash.insert(temp);
prev = curr;
curr = temp;
}
}
// A utility function to get the middle
// index from corner indexes.
int getMid(int s, int e)
{
return s + (e - s) / 2;
}
// Recursive function to get the number
// of Fibonacci numbers in a given range
/* where
st --> Pointer to segment tree
index --> Index of current node in the
segment tree. Initially 0 is passed
as root is always at index 0
ss & se --> Starting and ending indexes of
the segment represented by current
node, i.e., st[index]
qs & qe --> Starting and ending indexes
of query range
*/
int queryFibonacciUtil(int* st, int ss,
int se, int qs,
int qe, int index)
{
// If segment of this node is a part
// of given range, then return
// the number of Fibonacci numbers
// in the segment
if (qs <= ss && qe >= se)
return st[index];
// If segment of this node
// is outside the given range
if (se < qs || ss > qe)
return 0;
// If a part of this segment
// overlaps with the given range
int mid = getMid(ss, se);
return queryFibonacciUtil(st, ss, mid, qs,
qe, 2 * index + 1)
+ queryFibonacciUtil(st, mid + 1, se,
qs, qe, 2 * index + 2);
}
// Recursive function to update
// the nodes which have the given
// index in their range.
/* where
st, si, ss and se are same as getSumUtil()
i --> index of the element to be updated.
This index is in input array.
diff --> Value to be added to all nodes
which have i in range
*/
void updateValueUtil(int* st, int ss,
int se, int i,
int diff, int si)
{
// Base Case:
// If the input index lies outside
// the range of this segment
if (i < ss || i > se)
return;
// If the input index is in range
// of this node, then update the value
// of the node and its children
st[si] = st[si] + diff;
if (se != ss) {
int mid = getMid(ss, se);
updateValueUtil(st, ss, mid, i,
diff, 2 * si + 1);
updateValueUtil(st, mid + 1, se,
i, diff, 2 * si + 2);
}
}
// Function to update a value in the
// input array and segment tree.
// It uses updateValueUtil() to update
// the value in segment tree
void updateValue(int arr[], int* st,
int n, int i,
int new_val,
set<int> hash)
{
// Check for erroneous input index
if (i < 0 || i > n - 1) {
printf("Invalid Input");
return;
}
int diff, oldValue;
oldValue = arr[i];
// Update the value in array
arr[i] = new_val;
// Case 1: Old and new values
// both are Fibonacci numbers
if (hash.find(oldValue) != hash.end()
&& hash.find(new_val) != hash.end())
return;
// Case 2: Old and new values
// both not Fibonacci numbers
if (hash.find(oldValue) == hash.end()
&& hash.find(new_val) == hash.end())
return;
// Case 3: Old value was Fibonacci,
// new value is non Fibonacci
if (hash.find(oldValue) != hash.end()
&& hash.find(new_val) == hash.end()) {
diff = -1;
}
// Case 4: Old value was non Fibonacci,
// new_val is Fibonacci
if (hash.find(oldValue) == hash.end()
&& hash.find(new_val) != hash.end()) {
diff = 1;
}
// Update the values of nodes in segment tree
updateValueUtil(st, 0, n - 1, i, diff, 0);
}
// Return number of Fibonacci numbers
// in range from index qs (query start)
// to qe (query end).
// It mainly uses queryFibonacciUtil()
void queryFibonacci(int* st, int n,
int qs, int qe)
{
int FibonacciInRange
= queryFibonacciUtil(st, 0, n - 1,
qs, qe, 0);
cout << "Number of Fibonacci numbers "
<< "in subarray from "
<< qs << " to "
<< qe << " = "
<< FibonacciInRange << "\n";
}
// 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, set<int> hash)
{
// If there is one element in array,
// check if it is Fibonacci number
// then store 1 in the segment tree
// else store 0 and return
if (ss == se) {
// if arr[ss] is fibonacci number
if (hash.find(arr[ss]) != hash.end())
st[si] = 1;
else
st[si] = 0;
return st[si];
}
// If there are more than one elements,
// then recur for left and right subtrees
// and store the sum of the
// two values in this node
int mid = getMid(ss, se);
st[si] = constructSTUtil(arr, ss, mid, st,
si * 2 + 1, hash)
+ constructSTUtil(arr, mid + 1, se, st,
si * 2 + 2, hash);
return st[si];
}
// Function to construct a segment tree from given array.
// This function allocates memory for segment tree and
// calls constructSTUtil() to fill the allocated memory
int* constructST(int arr[], int n, set<int> hash)
{
// Allocate memory for segment tree
// Height of segment tree
int x = (int)(ceil(log2(n)));
// Maximum size of segment tree
int max_size = 2 * (int)pow(2, x) - 1;
int* st = new int[max_size];
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0, hash);
// Return the constructed segment tree
return st;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 8, 9 };
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
set<int> hash;
createHash(hash, maxEle);
// Build segment tree from given array
int* st = constructST(arr, n, hash);
// Query 1: Query(start = 0, end = 4)
int start = 0;
int end = 4;
queryFibonacci(st, n, start, end);
// Query 2: Update(i = 3, x = 5),
// i.e Update a[i] to x
int i = 3;
int x = 5;
updateValue(arr, st, n, i, x, hash);
// uncomment to see array after update
// for(int i = 0; i < n; i++)
// cout << arr[i] << " ";
// Query 3: Query(start = 0, end = 4)
start = 0;
end = 4;
queryFibonacci(st, n, start, end);
return 0;
}
Java
// Java program to find number of fibonacci numbers
// in a subarray and performing updates
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
class GFG
{
static final int MAX = 1000;
// Function to create hash table
// to check Fibonacci numbers
static void createHash(Set<Integer> hash, int maxElement)
{
int prev = 0, curr = 1;
hash.add(prev);
hash.add(curr);
while (curr <= maxElement)
{
int temp = curr + prev;
hash.add(temp);
prev = curr;
curr = temp;
}
}
// A utility function to get the middle
// index from corner indexes.
static int getMid(int s, int e)
{
return s + (e - s) / 2;
}
// Recursive function to get the number
// of Fibonacci numbers in a given range
/*
* where st --> Pointer to segment tree index --> Index of current node in the
* segment tree. Initially 0 is passed as root is always at index 0 ss & se -->
* Starting and ending indexes of the segment represented by current node, i.e.,
* st[index] qs & qe --> Starting and ending indexes of query range
*/
static int queryFibonacciUtil(int[] st, int ss, int se,
int qs, int qe, int index)
{
// If segment of this node is a part
// of given range, then return
// the number of Fibonacci numbers
// in the segment
if (qs <= ss && qe >= se)
return st[index];
// If segment of this node
// is outside the given range
if (se < qs || ss > qe)
return 0;
// If a part of this segment
// overlaps with the given range
int mid = getMid(ss, se);
return queryFibonacciUtil(st, ss, mid,
qs, qe, 2 * index + 1)
+ queryFibonacciUtil(st, mid + 1, se,
qs, qe, 2 * index + 2);
}
// Recursive function to update
// the nodes which have the given
// index in their range.
/*
* where st, si, ss and se are same as getSumUtil() i --> index of the element
* to be updated. This index is in input array. diff --> Value to be added to
* all nodes which have i in range
*/
static void updateValueUtil(int[] st, int ss,
int se, int i,
int diff, int si)
{
// Base Case:
// If the input index lies outside
// the range of this segment
if (i < ss || i > se)
return;
// If the input index is in range
// of this node, then update the value
// of the node and its children
st[si] = st[si] + diff;
if (se != ss)
{
int mid = getMid(ss, se);
updateValueUtil(st, ss, mid, i,
diff, 2 * si + 1);
updateValueUtil(st, mid + 1, se, i,
diff, 2 * si + 2);
}
}
// Function to update a value in the
// input array and segment tree.
// It uses updateValueUtil() to update
// the value in segment tree
static void updateValue(int arr[], int[] st, int n,
int i, int new_val, Set<Integer> hash)
{
// Check for erroneous input index
if (i < 0 || i > n - 1)
{
System.out.printf("Invalid Input");
return;
}
int diff = 0, oldValue;
oldValue = arr[i];
// Update the value in array
arr[i] = new_val;
// Case 1: Old and new values
// both are Fibonacci numbers
if (hash.contains(oldValue) &&
hash.contains(new_val))
return;
// Case 2: Old and new values
// both not Fibonacci numbers
if (!hash.contains(oldValue) &&
!hash.contains(new_val))
return;
// Case 3: Old value was Fibonacci,
// new value is non Fibonacci
if (hash.contains(oldValue) &&
!hash.contains(new_val))
{
diff = -1;
}
// Case 4: Old value was non Fibonacci,
// new_val is Fibonacci
if (!hash.contains(oldValue) &&
hash.contains(new_val))
{
diff = 1;
}
// Update the values of nodes in segment tree
updateValueUtil(st, 0, n - 1, i, diff, 0);
}
// Return number of Fibonacci numbers
// in range from index qs (query start)
// to qe (query end).
// It mainly uses queryFibonacciUtil()
static void queryFibonacci(int[] st, int n, int qs, int qe)
{
int FibonacciInRange = queryFibonacciUtil(st, 0,
n - 1, qs, qe, 0);
System.out.printf("Number of Fibonacci numbers in subarray from %d to %d = %d\n", qs, qe, FibonacciInRange);
}
// 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, Set<Integer> hash)
{
// If there is one element in array,
// check if it is Fibonacci number
// then store 1 in the segment tree
// else store 0 and return
if (ss == se)
{
// if arr[ss] is fibonacci number
if (hash.contains(arr[ss]))
st[si] = 1;
else
st[si] = 0;
return st[si];
}
// If there are more than one elements,
// then recur for left and right subtrees
// and store the sum of the
// two values in this node
int mid = getMid(ss, se);
st[si] = constructSTUtil(arr, ss, mid, st,
si * 2 + 1, hash)
+ constructSTUtil(arr, mid + 1, se,
st, si * 2 + 2, hash);
return st[si];
}
// Function to construct a segment tree from given array.
// This function allocates memory for segment tree and
// calls constructSTUtil() to fill the allocated memory
static int[] constructST(int arr[], int n, Set<Integer> hash)
{
// Allocate memory for segment tree
// 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;
int[] st = new int[max_size];
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0, hash);
// Return the constructed segment tree
return st;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 8, 9 };
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
Set<Integer> hash = new HashSet<>();
createHash(hash, maxEle);
// Build segment tree from given array
int[] st = constructST(arr, n, hash);
// Query 1: Query(start = 0, end = 4)
int start = 0;
int end = 4;
queryFibonacci(st, n, start, end);
// Query 2: Update(i = 3, x = 5),
// i.e Update a[i] to x
int i = 3;
int x = 5;
updateValue(arr, st, n, i, x, hash);
// uncomment to see array after update
// for(int i = 0; i < n; i++)
// cout << arr[i] << " ";
// Query 3: Query(start = 0, end = 4)
start = 0;
end = 4;
queryFibonacci(st, n, start, end);
}
}
// This code is contributed by sanjeev2552
Python3
# Python program to find number of fibonacci numbers
# in a subarray and performing updates
import math
MAX = 1000
# Function to create hash table
# to check Fibonacci numbers
def createHash(hash, maxElement):
prev = 0
curr = 1
hash.add(prev)
hash.add(curr)
while (curr <= maxElement):
temp = curr + prev
hash.add(temp)
prev = curr
curr = temp
# A utility function to get the middle
# index from corner indexes.
def getMid(s, e):
return math.floor(s + (e - s) / 2)
# Recursive function to get the number
# of Fibonacci numbers in a given range
# where
# st --> Pointer to segment tree
# index --> Index of current node in the
# segment tree. Initially 0 is passed
# as root is always at index 0
# ss & se --> Starting and ending indexes of
# the segment represented by current
# node, i.e., st[index]
# qs & qe --> Starting and ending indexes
# of query range
def queryFibonacciUtil(st, ss, se, qs, qe, index):
# If segment of this node is a part
# of given range, then return
# the number of Fibonacci numbers
# in the segment
if (qs <= ss and qe >= se):
return st[index]
# If segment of this node
# is outside the given range
if (se < qs or ss > qe):
return 0
# If a part of this segment
# overlaps with the given range
mid = getMid(ss, se)
return queryFibonacciUtil(st, ss, mid, qs, qe, 2 * index + 1) + queryFibonacciUtil(st, mid + 1, se, qs, qe, 2 * index + 2)
# Recursive function to update
# the nodes which have the given
# index in their range.
# where
# st, si, ss and se are same as getSumUtil()
# i --> index of the element to be updated.
# This index is in input array.
# diff --> Value to be added to all nodes
# which have i in range
def updateValueUtil(st, ss, se, i, diff, si):
# Base Case:
# If the input index lies outside
# the range of this segment
if (i < ss or i > se):
return
# If the input index is in range
# of this node, then update the value
# of the node and its children
st[si] = st[si] + diff
if (se != ss):
mid = getMid(ss, se)
updateValueUtil(st, ss, mid, i, diff, 2 * si + 1)
updateValueUtil(st, mid + 1, se, i, diff, 2 * si + 2)
# Function to update a value in the
# input array and segment tree.
# It uses updateValueUtil() to update
# the value in segment tree
def updateValue(arr, st, n, i, new_val, hash):
# Check for erroneous input index
if (i < 0 or i > n - 1):
print("Invalid Input")
return
diff = 0
oldValue = 0
oldValue = arr[i]
# Update the value in array
arr[i] = new_val
# Case 1: Old and new values
# both are Fibonacci numbers
if oldValue in hash:
if new_val in hash:
return
# Case 2: Old and new values
# both not Fibonacci numbers
if not oldValue in hash:
if not new_val in hash:
return
# Case 3: Old value was Fibonacci,
# new value is non Fibonacci
if oldValue in hash:
if not new_val in hash:
diff = -1
# Case 4: Old value was non Fibonacci,
# new_val is Fibonacci
if not oldValue in hash:
if new_val in hash:
diff = 1
# Update the values of nodes in segment tree
updateValueUtil(st, 0, n - 1, i, diff, 0)
# Return number of Fibonacci numbers
# in range from index qs (query start)
# to qe (query end).
# It mainly uses queryFibonacciUtil()
def queryFibonacci(st, n, qs, qe):
FibonacciInRange = queryFibonacciUtil(st, 0, n - 1, qs, qe, 0)
print(
f"Number of Fibonacci numbers in subarray from {qs} to {qe} = {FibonacciInRange}")
# Recursive function that constructs
# Segment Tree for array[ss..se].
# si is index of current node
# in segment tree st
def constructSTUtil(arr, ss, se, st, si, hash):
# If there is one element in array,
# check if it is Fibonacci number
# then store 1 in the segment tree
# else store 0 and return
if (ss == se):
# if arr[ss] is fibonacci number
if arr[ss] in hash:
st[si] = 1
else:
st[si] = 0
return st[si]
# If there are more than one elements,
# then recur for left and right subtrees
# and store the sum of the
# two values in this node
mid = getMid(ss, se)
st[si] = constructSTUtil(arr, ss, mid, st, si * 2 + 1, hash) + \
constructSTUtil(arr, mid + 1, se, st, si * 2 + 2, hash)
return st[si]
# Function to construct a segment tree from given array.
# This function allocates memory for segment tree and
# calls constructSTUtil() to fill the allocated memory
def constructST(arr, n, hash):
# Allocate memory for segment tree
# Height of segment tree
x = math.floor(math.ceil(math.log2(n)))
# Maximum size of segment tree
max_size = 2 * math.floor(math.pow(2, x)) - 1
st = [0]*max_size
# Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0, hash)
# Return the constructed segment tree
return st
# Driver Code
arr = [1, 2, 3, 4, 8, 9]
n = len(arr)
# find the largest node value in the array
maxEle = -1
for i in range(len(arr)):
if arr[i] > maxEle:
maxEle = arr[i]
# Creating a set containing all Fibonacci numbers
# upto the maximum data value in the array
hash = set()
createHash(hash, maxEle)
# Build segment tree from given array
st = constructST(arr, n, hash)
# Query 1: Query(start = 0, end = 4)
start = 0
end = 4
queryFibonacci(st, n, start, end)
# Query 2: Update(i = 3, x = 5),
# i.e Update a[i] to x
i = 3
x = 5
updateValue(arr, st, n, i, x, hash)
# uncomment to see array after update
# for(int i = 0; i < n; i++)
# cout << arr[i] << " ";
# Query 3: Query(start = 0, end = 4)
start = 0
end = 4
queryFibonacci(st, n, start, end)
# The code is contributed by Gautam goel (gautamgoel962)
Javascript
<script>
// Javascript program to find number of fibonacci numbers
// in a subarray and performing updates
let MAX = 1000;
// Function to create hash table
// to check Fibonacci numbers
function createHash(hash, maxElement)
{
let prev = 0, curr = 1;
hash.add(prev);
hash.add(curr);
while (curr <= maxElement)
{
let temp = curr + prev;
hash.add(temp);
prev = curr;
curr = temp;
}
}
// A utility function to get the middle
// index from corner indexes.
function getMid(s, e)
{
return s + parseInt((e - s) / 2, 10);
}
// Recursive function to get the number
// of Fibonacci numbers in a given range
/*
* where st --> Pointer to segment tree index --> Index of current node in the
* segment tree. Initially 0 is passed as root is always at index 0 ss & se -->
* Starting and ending indexes of the segment represented by current node, i.e.,
* st[index] qs & qe --> Starting and ending indexes of query range
*/
function queryFibonacciUtil(st, ss, se, qs, qe, index)
{
// If segment of this node is a part
// of given range, then return
// the number of Fibonacci numbers
// in the segment
if (qs <= ss && qe >= se)
return st[index];
// If segment of this node
// is outside the given range
if (se < qs || ss > qe)
return 0;
// If a part of this segment
// overlaps with the given range
let mid = getMid(ss, se);
return queryFibonacciUtil(st, ss, mid,
qs, qe, 2 * index + 1)
+ queryFibonacciUtil(st, mid + 1, se,
qs, qe, 2 * index + 2);
}
// Recursive function to update
// the nodes which have the given
// index in their range.
/*
* where st, si, ss and se are same as getSumUtil() i --> index of the element
* to be updated. This index is in input array. diff --> Value to be added to
* all nodes which have i in range
*/
function updateValueUtil(st, ss, se, i, diff, si)
{
// Base Case:
// If the input index lies outside
// the range of this segment
if (i < ss || i > se)
return;
// If the input index is in range
// of this node, then update the value
// of the node and its children
st[si] = st[si] + diff;
if (se != ss)
{
let mid = getMid(ss, se);
updateValueUtil(st, ss, mid, i,
diff, 2 * si + 1);
updateValueUtil(st, mid + 1, se, i,
diff, 2 * si + 2);
}
}
// Function to update a value in the
// input array and segment tree.
// It uses updateValueUtil() to update
// the value in segment tree
function updateValue(arr, st, n, i, new_val, hash)
{
// Check for erroneous input index
if (i < 0 || i > n - 1)
{
document.write("Invalid Input");
return;
}
let diff = 0, oldValue;
oldValue = arr[i];
// Update the value in array
arr[i] = new_val;
// Case 1: Old and new values
// both are Fibonacci numbers
if (hash.has(oldValue) &&
hash.has(new_val))
return;
// Case 2: Old and new values
// both not Fibonacci numbers
if (!hash.has(oldValue) &&
!hash.has(new_val))
return;
// Case 3: Old value was Fibonacci,
// new value is non Fibonacci
if (hash.has(oldValue) &&
!hash.has(new_val))
{
diff = -1;
}
// Case 4: Old value was non Fibonacci,
// new_val is Fibonacci
if (!hash.has(oldValue) &&
hash.has(new_val))
{
diff = 1;
}
// Update the values of nodes in segment tree
updateValueUtil(st, 0, n - 1, i, diff, 0);
}
// Return number of Fibonacci numbers
// in range from index qs (query start)
// to qe (query end).
// It mainly uses queryFibonacciUtil()
function queryFibonacci(st, n, qs, qe)
{
let FibonacciInRange = queryFibonacciUtil(st, 0,
n - 1, qs, qe, 0);
document.write("Number of Fibonacci numbers in subarray from " + qs + " to " + qe + " = " + FibonacciInRange + "</br>");
}
// 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, hash)
{
// If there is one element in array,
// check if it is Fibonacci number
// then store 1 in the segment tree
// else store 0 and return
if (ss == se)
{
// if arr[ss] is fibonacci number
if (hash.has(arr[ss]))
st[si] = 1;
else
st[si] = 0;
return st[si];
}
// If there are more than one elements,
// then recur for left and right subtrees
// and store the sum of the
// two values in this node
let mid = getMid(ss, se);
st[si] = constructSTUtil(arr, ss, mid, st,
si * 2 + 1, hash)
+ constructSTUtil(arr, mid + 1, se,
st, si * 2 + 2, hash);
return st[si];
}
// Function to construct a segment tree from given array.
// This function allocates memory for segment tree and
// calls constructSTUtil() to fill the allocated memory
function constructST(arr, n, hash)
{
// Allocate memory for segment tree
// Height of segment tree
let x = (Math.ceil(Math.log(n) / Math.log(2)));
// Maximum size of segment tree
let max_size = 2 * Math.pow(2, x) - 1;
let st = new Array(max_size);
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0, hash);
// Return the constructed segment tree
return st;
}
let arr = [ 1, 2, 3, 4, 8, 9 ];
let n = arr.length;
// find the largest node value in the array
let maxEle = Number.MIN_VALUE;
for(let i = 0; i < n; i++)
{
maxEle = Math.max(arr[i], maxEle);
}
// Creating a set containing all Fibonacci numbers
// upto the maximum data value in the array
let hash = new Set();
createHash(hash, maxEle);
// Build segment tree from given array
let st = constructST(arr, n, hash);
// Query 1: Query(start = 0, end = 4)
let start = 0;
let end = 4;
queryFibonacci(st, n, start, end);
// Query 2: Update(i = 3, x = 5),
// i.e Update a[i] to x
let i = 3;
let x = 5;
updateValue(arr, st, n, i, x, hash);
// uncomment to see array after update
// for(int i = 0; i < n; i++)
// cout << arr[i] << " ";
// Query 3: Query(start = 0, end = 4)
start = 0;
end = 4;
queryFibonacci(st, n, start, end);
// This code is contributed by divyesh072019.
</script>
Producción:
Number of Fibonacci numbers in subarray from 0 to 4 = 4 Number of Fibonacci numbers in subarray from 0 to 4 = 5
Complejidad de tiempo: la complejidad de tiempo de cada consulta y actualización es O(log n) y la de construir el árbol de segmentos es O(n)
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