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 Armstrong 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
Si no hay un número de Armstrong en el subarreglo, imprima -1 .
Ejemplo:
Entrada: arr = [192, 113, 535, 7, 19, 111]
Consulta 1: máximo (inicio = 1, final = 3)
Consulta 2: actualización (i = 1, x = 153) es decir, arr [1] = 153
Salida:
Número máximo de Armstrong en el rango dado = 7
Número máximo de Armstrong actualizado en el rango dado = 153
Explicación:
En la consulta máxima, el subarreglo [1…3] tiene 1 número de Armstrong 7 a saber. [113, 535, 7]
Por lo tanto, 7 es el número máximo de Armstrong en el rango dado.
En la consulta de actualización, el valor en el índice 1 se actualiza a 153, la array arr ahora es [192, 153, 535, 7, 19, 111]
En la consulta máxima actualizada, la array secundaria [1…3] tiene 2 Armstrong números 153 y 7 a saber. [153, 535, 7]
Por lo tanto, 153 es el número máximo de Armstrong en el rango dado.
Solución simple:
una solución simple es ejecutar un bucle de l a r y calcular el número máximo de elementos de Armstrong en un rango determinado. 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:
- Un enfoque eficiente será crear un árbol de segmentos en el que cada Node almacene dos valores ( valor y max_set_bits ) y realizar una consulta de rango para encontrar el número máximo de Armstrong.
- Si lo analizamos en profundidad, el número máximo de Armstrong para cualquier combinación de dos rangos será el número máximo de Armstrong del lado izquierdo o el número máximo de Armstrong del lado derecho, el que sea máximo se tendrá en cuenta.
- Representación de árboles de segmentos:
- Los Nodes hoja son los elementos de la array dada.
- Cada Node interno representa el número máximo de Armstrong de todos sus hijos o -1 si no existe ningún número de Armstrong en el rango.
- Se utiliza una representación de array de un á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 2*i+2 y el padre está en (i-1)/2 .
- Construcción del árbol de segmentos a partir de la array dada:
- Empezamos 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 numérico de Armstrong 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 de segmentos será log 2 n. Dado que el árbol se representa mediante una array y se debe mantener la relación entre los índices principales y secundarios, el tamaño de la memoria asignada para el árbol de segmentos será 2*( 2 ceil(log 2 n) ) – 1 .
- Un entero positivo de n dígitos se denomina número de Armstrong de orden n (el orden es un número de dígitos) si
abcd… = pow(a, n) + pow(b, n) + pow(c, n) + pow(d, n) + ….
- Para verificar los números de Armstrong, la idea es primero contar los dígitos de los números (o encontrar el orden). Sea n el número de dígitos. Para cada dígito r en el número de entrada x, calcule r n . Si la suma de todos estos valores es igual a n, devuelve verdadero o falso.
- Luego hacemos una consulta de rango en el árbol de segmentos para averiguar el número máximo de Armstrong para el rango dado y generar el valor correspondiente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
// A utility function to get the
// middle index of given range.
int getMid(int s, int e)
{
return s + (e - s) / 2;
}
// Function that return true
// if num is armstrong
// else return false
bool isArmstrong(int x)
{
int n = to_string(x).size();
int sum1 = 0;
int temp = x;
while (temp > 0) {
int digit = temp % 10;
sum1 += pow(digit, n);
temp /= 10;
}
if (sum1 == x)
return true;
return false;
}
/* A recursive function to get
the sum of values in the
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
the 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 (isArmstrong(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] = 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 (isArmstrong(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] = max(constructSTUtil(
arr, ss, mid, st,
si * 2 + 1),
constructSTUtil(
arr, mid + 1, se,
st, si * 2 + 2));
return st[si];
}
/* Function to construct a 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[] = { 192, 113,
535, 7, 19, 111 };
int n = sizeof(arr) / sizeof(arr[0]);
// Build segment tree from
// given array
int* st = constructST(arr, n);
// Print max of values in array
// from index 1 to 3
cout << "Maximum armstrong "
<< "number in given range = "
<< getMax(st, n, 1, 3) << endl;
// Update: set arr[1] = 153 and update
// corresponding segment tree nodes.
updateValue(arr, st, 0,
n - 1, 1, 153, 0);
// Find max after the value is updated
cout << "Updated Maximum armstrong "
<< "number in given range = "
<< getMax(st, n, 1, 3) << endl;
return 0;
}
Java
// Java code to implement
// the above approach
import java.util.*;
class GFG{
// A utility function to get the
// middle index of given range.
static int getMid(int s, int e)
{
return s + (e - s) / 2;
}
// Function that return true
// if num is armstrong
// else return false
static boolean isArmstrong(int x)
{
int n = String.valueOf(x).length();
int sum1 = 0;
int temp = x;
while (temp > 0)
{
int digit = temp % 10;
sum1 += Math.pow(digit, n);
temp /= 10;
}
if (sum1 == x)
return true;
return false;
}
/* A recursive function to get
the sum of values in the
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 ),
MaxUtil(st, mid + 1,
se, l, r,
2 * node + 1));
}
/* A recursive function to update
the nodes which have the given
the 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.print("Invalid Input" + "\n");
return;
}
if (ss == se)
{
// update value in array
// and in segment tree
arr[index] = value;
if (isArmstrong(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);
else
updateValue(arr, st, mid + 1,
se, index, value,
2 * node +1);
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");
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 (isArmstrong(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 ),
constructSTUtil(arr, mid + 1,
se, st,
si * 2 + 1));
return st[si];
}
/* Function to construct a 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)));
// 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[] = {192, 113,
535, 7, 19, 111};
int n = arr.length;
// Build segment tree from
// given array
int[] st = constructST(arr, n);
// Print max of values in array
// from index 1 to 3
System.out.print("Maximum armstrong " +
"number in given range = " +
getMax(st, n, 1, 3) + "\n");
// Update: set arr[1] = 153 and update
// corresponding segment tree nodes.
updateValue(arr, st, 0,
n - 1, 1, 153, 0);
// Find max after the value is updated
System.out.print("Updated Maximum armstrong " +
"number in given range = " +
getMax(st, n, 1, 3) + "\n");
}
}
// This code is contributed by gauravrajput1
Python3
# Python code to implement above approach
import math
# A utility function to get the
# middle index of given range.
def getMid(s: int, e: int) -> int:
return s + (e - s) // 2
# Function that return true
# if num is armstrong
# else return false
def isArmstrong(x: int) -> bool:
n = len(str(x))
sum1 = 0
temp = x
while (temp > 0):
digit = temp % 10
sum1 += pow(digit, n)
temp //= 10
if (sum1 == x):
return True
return False
''' A recursive function to get
the sum of values in the
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 '''
def 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 and r >= se):
return st[node]
# If segment of this node does not
# belong to given range
if (se < l or ss > r):
return -1
# If segment of this node is
# partially the part of given
# range
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
the 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.'''
def updateValue(arr, st, ss, se, index, value, node):
if (index < ss or index > se):
print("Invalid Input")
return
if (ss == se):
# update value in array
# and in segment tree
arr[index] = value
if (isArmstrong(value)):
st[node] = value
else:
st[node] = -1
else:
mid = getMid(ss, se)
if (index >= ss and 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).
def getMax(st, n, l, r):
# Check for erroneous input values
if (l < 0 or r > n - 1 or l > r):
print("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
def 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 (isArmstrong(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
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 a segment tree
from given array. This function
allocates memory for segment tree.'''
def constructST(arr, n):
# Height of segment tree
x = int(math.ceil(math.log2(n)))
# Maximum size of segment tree
max_size = 2 * int(math.pow(2, x)) - 1
# Allocate memory
st = [0 for _ in range(max_size)]
# Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0)
# Return the constructed
# segment tree
return st
# Driver code
if __name__ == "__main__":
arr = [192, 113, 535, 7, 19, 111]
n = len(arr)
# Build segment tree from
# given array
st = constructST(arr, n)
# Print max of values in array
# from index 1 to 3
print("Maximum armstrong number in given range = {}".format(
getMax(st, n, 1, 3)))
# Update: set arr[1] = 153 and update
# corresponding segment tree nodes.
updateValue(arr, st, 0, n - 1, 1, 153, 0)
# Find max after the value is updated
print("Updated Maximum armstrong number in given range = {}".format(
getMax(st, n, 1, 3)))
# This code is contributed by sanjeev2552
C#
// C# code to implement
// the above approach
using System;
class GFG{
// A utility function to get the
// middle index of given range.
static int getMid(int s, int e)
{
return s + (e - s) / 2;
}
// Function that return true
// if num is armstrong
// else return false
static bool isArmstrong(int x)
{
int n = String.Join("", x).Length;
int sum1 = 0;
int temp = x;
while (temp > 0)
{
int digit = temp % 10;
sum1 += (int)Math.Pow(digit, n);
temp /= 10;
}
if (sum1 == x)
return true;
return false;
}
/* A recursive function to get
the sum of values in the
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),
MaxUtil(st, mid + 1,
se, l, r,
2 * node + 1));
}
/* A recursive function to update
the nodes which have the given
the 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)
{
Console.Write("Invalid Input" + "\n");
return;
}
if (ss == se)
{
// update value in array
// and in segment tree
arr[index] = value;
if (isArmstrong(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);
else
updateValue(arr, st, mid + 1,
se, index, value,
2 * node + 1);
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)
{
Console.Write("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
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 (isArmstrong(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),
constructSTUtil(arr, mid + 1,
se, st,
si * 2 + 1));
return st[si];
}
/* Function to construct a 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.Ceiling(Math.Log(n)));
// 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 = {192, 113,
535, 7, 19, 111};
int n = arr.Length;
// Build segment tree from
// given array
int[] st = constructST(arr, n);
// Print max of values in array
// from index 1 to 3
Console.Write("Maximum armstrong " +
"number in given range = " +
getMax(st, n, 1, 3) + "\n");
// Update: set arr[1] = 153 and update
// corresponding segment tree nodes.
updateValue(arr, st, 0,
n - 1, 1, 153, 0);
// Find max after the value is updated
Console.Write("Updated Maximum armstrong " +
"number in given range = " +
getMax(st, n, 1, 3) + "\n");
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript code to implement
// the above approach
// A utility function to get the
// middle index of given range.
function getMid(s,e)
{
return s + Math.floor((e - s) / 2);
}
// Function that return true
// if num is armstrong
// else return false
function isArmstrong(x)
{
let n = (x).toString().length;
let sum1 = 0;
let temp = x;
while (temp > 0)
{
let digit = temp % 10;
sum1 += Math.pow(digit, n);
temp = Math.floor(temp/10);
}
if (sum1 == x)
return true;
return false;
}
/* A recursive function to get
the sum of values in the
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 ),
MaxUtil(st, mid + 1,
se, l, r,
2 * node + 1));
}
/* A recursive function to update
the nodes which have the given
the 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)
{
document.write("Invalid Input" + "<br>");
return;
}
if (ss == se)
{
// update value in array
// and in segment tree
arr[index] = value;
if (isArmstrong(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);
else
updateValue(arr, st, mid + 1,
se, index, value,
2 * node +1);
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)
{
document.write("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 (isArmstrong(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 ),
constructSTUtil(arr, mid + 1,
se, st,
si * 2 + 1));
return st[si];
}
/* Function to construct a segment tree
from given array. This function
allocates memory for segment tree.*/
function constructST(arr,n)
{
// Height of segment tree
let x = (Math.ceil(Math.log(n)));
// Maximum size of segment tree
let max_size = 2 * Math.pow(2, x) - 1;
// Allocate memory
let st = new Array(max_size);
// Fill the allocated memory st
constructSTUtil(arr, 0,
n - 1, st, 0);
// Return the constructed
// segment tree
return st;
}
// Driver code
let arr=[192, 113,
535, 7, 19, 111];
let n = arr.length;
// Build segment tree from
// given array
let st = constructST(arr, n);
// Print max of values in array
// from index 1 to 3
document.write("Maximum armstrong " +
"number in given range = " +
getMax(st, n, 1, 3) + "<br>");
// Update: set arr[1] = 153 and update
// corresponding segment tree nodes.
updateValue(arr, st, 0,
n - 1, 1, 153, 0);
// Find max after the value is updated
document.write("Updated Maximum armstrong " +
"number in given range = " +
getMax(st, n, 1, 3) + "<br>");
// This code is contributed by patel2127
</script>
Producción:
Maximum armstrong number in given range = 7 Updated Maximum armstrong number in given range = 153
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