Dada una array arr[] de N enteros, la tarea es realizar las siguientes dos consultas:
- consulta (inicio, fin) : imprime la cantidad de números 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
Ejemplos:
Entrada: arr = { 18, 153, 8, 9, 14, 5}
Consulta 1: consulta (inicio = 0, final = 4)
Consulta 2: actualización (i = 3, x = 11)
Consulta 3: consulta (inicio = 0, final = 4)
Salida: 3
2
Explicación
en Consulta 1 ,
18 -> 1*1 + 8*8 != 18
153 -> 1*1*1 + 5*5*5 + 3*3*3 = 153
8 -> 8 = 8
9 -> 9 = 9
14 -> 1*1 + 4*4 != 14
el subarreglo [0…4] tiene 3 números de Armstrong a saber. {18, 153, 8, 9, 14}
En la Consulta 2 , el valor en el índice 3 se actualiza a 11,
la array arr ahora es, { 18, 153, 8, 11, 14, 5}
En la Consulta 3 ,
18 – > 1*1 + 8*8 != 18
153 -> 1*1*1 + 5*5*5 + 3*3*3 = 153
8 -> 8 = 8
9 -> 1*1 + 1*1 != 11
14 -> 1*1 + 4* 4 != 14
el subarreglo [0…4] tiene 2 números de Armstrong a saber. {18, 153, 8, 11, 14}
Enfoque: para manejar actualizaciones de puntos y consultas de rango, un árbol de segmentos es óptimo para este propósito.
Un entero positivo de n dígitos se denomina número de Armstrong de orden n (el orden es el 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 esos valores es igual a n, configúrelo en 1, de lo contrario, en 0.
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 de Armstrong) o 1 (si es un número de Armstrong).
- 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 totales de Armstrong 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 Nodes en el rango de principio a fin, que a su vez representa la cantidad de números de Armstrong 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: si x e y son números
de Armstrong La cantidad de números de Armstrong en el subarreglo no cambia, así que solo actualizamos el arreglo y no modificamos el árbol de segmentos - Caso 2: si x e y no son números
de Armstrong La cantidad de números de Armstrong 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 Armstrong pero x no lo es,
el recuento de números de Armstrong 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 Armstrong pero x es un número de Armstrong El número
de números de Armstrong 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: si x e y son números
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the number
// of Armstrong numbers in a
// subarray and performing updates
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
// 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 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 Armstrong 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 queryArmstrongUtil(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 Armstrong 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 queryArmstrongUtil(
st, ss, mid, qs,
qe, 2 * index + 1)
+ queryArmstrongUtil(
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)
{
// 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 Armstrong numbers
if (isArmstrong(oldValue)
&& isArmstrong(new_val))
return;
// Case 2: Old and new values
// both not Armstrong numbers
if (!isArmstrong(oldValue)
&& !isArmstrong(new_val))
return;
// Case 3: Old value was Armstrong,
// new value is non Armstrong
if (isArmstrong(oldValue) && !isArmstrong(new_val)) {
diff = -1;
}
// Case 4: Old value was non Armstrong,
// new_val is Armstrong
if (!isArmstrong(oldValue)
&& !isArmstrong(new_val)) {
diff = 1;
}
// Update the values of
// nodes in segment tree
updateValueUtil(
st, 0, n - 1,
i, diff, 0);
}
// Return number of Armstrong numbers
// in range from index qs (query start)
// to qe (query end).
// It mainly uses queryArmstrongUtil()
void queryArmstrong(int* st, int n,
int qs, int qe)
{
int ArmstrongInRange
= queryArmstrongUtil(st, 0, n - 1,
qs, qe, 0);
cout << "Number of Armstrong numbers "
<< "in subarray from "
<< qs << " to "
<< qe << " = "
<< ArmstrongInRange << "\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)
{
// If there is one element in array,
// check if it is Armstrong number
// then store 1 in the segment tree
// else store 0 and return
if (ss == se) {
// if arr[ss] is Armstrong number
if (isArmstrong(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)
+ 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 and
// calls constructSTUtil() to
// fill the allocated memory
int* constructST(int arr[], int n)
{
// 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);
// Return the constructed segment tree
return st;
}
// Driver Code
int main()
{
int arr[] = { 18, 153, 8, 9, 14, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
// Build segment tree from given array
int* st = constructST(arr, n);
// Query 1: Query(start = 0, end = 4)
int start = 0;
int end = 4;
queryArmstrong(st, n, start, end);
// Query 2: Update(i = 3, x = 11),
// i.e Update a[i] to x
int i = 3;
int x = 11;
updateValue(arr, st, n, i, x);
// Print array after update
cout << "Array after update: ";
for (int i = 0; i < n; i++)
cout << arr[i] << ", ";
cout << endl;
// Query 3: Query(start = 0, end = 4)
start = 0;
end = 4;
queryArmstrong(st, n, start, end);
return 0;
}
Python3
# Python3 program to find the number
# of Armstrong numbers in a
# subarray and performing updates
import math
MAX = 1000
# Function that return true
# if num is armstrong
# else return false
def isArmstrong(x):
n = len(str(x))
sum1 = 0
temp = x
while temp > 0:
digit = temp % 10
sum1 += pow(digit, n)
temp = temp // 10
if sum1 == x:
return True
return False
# A utility function to get the middle
# index from corner indexes.
def getMid(s, e):
return s + (e - s) // 2
# Recursive function to get the number
# of Armstrong 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 queryArmstrongUtil(st, ss, se, qs, qe, index):
# If segment of this node is a part
# of given range, then return
# the number of Armstrong 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 (queryArmstrongUtil(st, ss, mid, qs,
qe, 2 * index + 1) +
queryArmstrongUtil(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):
# Check for erroneous input index
if i < 0 or i > n - 1:
print('Invalid Input')
return
oldValue = arr[i]
# Update the value in array
arr[i] = new_val
# Case 1: Old and new values
# both are Armstrong numbers
if (isArmstrong(oldValue) and
isArmstrong(new_val)):
return
# Case 2: Old and new values
# both not Armstrong numbers
if (not isArmstrong(oldValue) and
not isArmstrong(new_val)):
return
# Case 3: Old value was Armstrong,
# new value is non Armstrong
if (isArmstrong(oldValue) and (not
isArmstrong(new_val))):
diff = -1
# Case 4: Old value was non Armstrong,
# new_val is Armstrong
if (not isArmstrong(oldValue) and
not isArmstrong(new_val)):
diff = 1
# Update the values of
# nodes in segment tree
updateValueUtil(st, 0, n - 1, i, diff, 0)
# Return number of Armstrong numbers
# in range from index qs (query start)
# to qe (query end).
# It mainly uses queryArmstrongUtil()
def queryArmstrong(st, n, qs, qe):
ArmstrongInRange = queryArmstrongUtil(st, 0, n - 1,
qs, qe, 0)
print("Number of Armstrong numbers in "
"subarray from", qs, "to", qe, "=",
ArmstrongInRange)
# 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,
# check if it is Armstrong number
# then store 1 in the segment tree
# else store 0 and return
if ss == se:
# If arr[ss] is Armstrong number
if isArmstrong(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
mid = getMid(ss, se)
st[si] = (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 and
# calls constructSTUtil() to
# fill the allocated memory
def constructST(arr, n):
# Allocate memory for segment tree
# Height of segment tree
x = int(math.ceil(math.log2(n)))
# Maximum size of segment tree
max_size = 2 * int(pow(2, x)) - 1
st = [-1] * max_size
# Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0)
# Return the constructed segment tree
return st
# Driver code
arr = [ 18, 153, 8, 9, 14, 5 ]
n = len(arr)
# Build segment tree from given array
st = constructST(arr, n)
# Query 1: Query(start = 0, end = 4)
start = 0
end = 4
queryArmstrong(st, n, start, end)
# Query 2: Update(i = 3, x = 11),
# i.e Update a[i] to x
i = 3
x = 11
updateValue(arr, st, n, i, x)
# Print array after update
print("Array after update:", end = " ")
for i in range(n):
print(arr[i], end = ", ")
print()
# Query 3: Query(start = 0, end = 4)
start = 0
end = 4
queryArmstrong(st, n, start, end)
# This code is contributed by stutipathak31jan
C#
// C# program to find the number
// of Armstrong numbers in a
// subarray and performing updates
using System;
class GFG{
public int MAX = 1000;
// Function that return true
// if num is armstrong
// else return false
static bool isArmstrong(int x)
{
int n = x.ToString().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 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 Armstrong 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 queryArmstrongUtil(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 Armstrong 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 queryArmstrongUtil(st, ss, mid, qs, qe,
2 * index + 1) +
queryArmstrongUtil(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)
{
// Check for erroneous input index
if (i < 0 || i > n - 1)
{
Console.Write("Invalid Input");
return;
}
int diff = 0, oldValue = 0;
oldValue = arr[i];
// Update the value in array
arr[i] = new_val;
// Case 1: Old and new values
// both are Armstrong numbers
if (isArmstrong(oldValue) &&
isArmstrong(new_val))
return;
// Case 2: Old and new values
// both not Armstrong numbers
if (!isArmstrong(oldValue) &&
!isArmstrong(new_val))
return;
// Case 3: Old value was Armstrong,
// new value is non Armstrong
if (isArmstrong(oldValue) &&
!isArmstrong(new_val))
{
diff = -1;
}
// Case 4: Old value was non Armstrong,
// new_val is Armstrong
if (!isArmstrong(oldValue) &&
!isArmstrong(new_val))
{
diff = 1;
}
// Update the values of
// nodes in segment tree
updateValueUtil(st, 0, n - 1, i, diff, 0);
}
// Return number of Armstrong numbers
// in range from index qs (query start)
// to qe (query end).
// It mainly uses queryArmstrongUtil()
static void queryArmstrong(int[] st, int n, int qs,
int qe)
{
int ArmstrongInRange = queryArmstrongUtil(
st, 0, n - 1, qs, qe, 0);
Console.WriteLine("Number of Armstrong numbers " +
"in subarray from " + qs + " to " +
qe + " = " + ArmstrongInRange);
}
// 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,
// check if it is Armstrong number
// then store 1 in the segment tree
// else store 0 and return
if (ss == se)
{
// If arr[ss] is Armstrong number
if (isArmstrong(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) +
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 and
// calls constructSTUtil() to
// fill the allocated memory
static int[] constructST(int[] arr, int n)
{
// Allocate memory for segment tree
// Height of segment tree
int x = (int)(Math.Ceiling(Math.Log(n, 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);
// Return the constructed segment tree
return st;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 18, 153, 8, 9, 14, 5 };
int n = arr.Length;
// Build segment tree from given array
int[] st = constructST(arr, n);
// Query 1: Query(start = 0, end = 4)
int start = 0;
int end = 4;
queryArmstrong(st, n, start, end);
// Query 2: Update(i = 3, x = 11),
// i.e Update a[i] to x
int i = 3;
int x = 11;
updateValue(arr, st, n, i, x);
// Print array after update
Console.Write("Array after update: ");
for(int j = 0; j < n; j++)
Console.Write(arr[j] + ", ");
Console.WriteLine();
// Query 3: Query(start = 0, end = 4)
start = 0;
end = 4;
queryArmstrong(st, n, start, end);
}
}
// This code is contributed by ukasp
Producción:
Number of Armstrong numbers in subarray from 0 to 4 = 3 Array after update: 18, 153, 8, 11, 14, 5, Number of Armstrong numbers in subarray from 0 to 4 = 2
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