Dada una array de N enteros, la tarea es realizar las siguientes dos operaciones en la array dada:
consulta (L, R) : imprime el número de números poderosos en el subarreglo de L a R.
update (i, x) : actualiza el valor en el índice i a x, es decir, arr [i] = x
Un número N se dice Número Poderoso si, para todo factor primo p de él, p 2 también lo divide.
Requisitos previos: número poderoso , árbol de segmentos
Ejemplos:
Entrada:
arr = {1, 12, 3, 8, 17, 9}
Consulta 1: consulta (L = 1, R = 4)
Consulta 2: actualización (i = 1, x = 9)
Consulta 3: consulta (L = 1, R = 4)
Salida:
1
2
Explicación:
Consulta 1: Los números poderosos en el rango arr[1:4] son 8.
Consulta 2: Los números poderosos en el rango arr[1:4] después de la operación de actualización son 9 y 8.
Enfoque:
dado que necesitamos manejar actualizaciones de puntos y consultas de rango, usaremos un árbol de segmentos para resolver el problema.
- Calcularemos previamente todos los números poderosos hasta el valor máximo que puede tomar arr[i], digamos MAX .
La complejidad temporal de esta operación será O(MAX * sqrt(MAX))
- Construyendo el árbol de segmentos:
- El problema se puede reducir a la suma de subarreglo utilizando el árbol de segmentos .
- Ahora podemos construir el árbol de segmentos donde los Nodes hoja representarán 1 (cuando un número es un número poderoso) o 0 (cuando un número no es un número poderoso). Todos los Nodes internos tendrán la suma de sus dos hijos.
- El problema se puede reducir a la suma de subarreglo utilizando el árbol de segmentos .
- Actualizaciones de puntos:
- Para actualizar un elemento, debemos observar el intervalo en el que se encuentra el elemento y repetirlo en consecuencia en el elemento secundario izquierdo o derecho. Si el elemento a actualizar es un número poderoso, entonces actualizamos la hoja como 1, de lo contrario, 0.
- Para actualizar un elemento, debemos observar el intervalo en el que se encuentra el elemento y repetirlo en consecuencia en el elemento secundario izquierdo o derecho. Si el elemento a actualizar es un número poderoso, entonces actualizamos la hoja como 1, de lo contrario, 0.
- Consulta de rango:
- Cada vez que obtenemos una consulta de L a R, podemos consultar el árbol de segmentos para la suma de los Nodes en el rango L a R, que a su vez representa la cantidad de números poderosos en el rango L a R.
- Cada vez que obtenemos una consulta de L a R, podemos consultar el árbol de segmentos para la suma de los Nodes en el rango L a R, que a su vez representa la cantidad de números poderosos en el rango L a R.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find the number
// of Powerful numbers in subarray
// using segment tree
#include <bits/stdc++.h>
using namespace std;
#define MAX 100000
// Size of segment tree = 2^{log(MAX)+1}
int tree[3 * MAX];
int arr[MAX];
bool powerful[MAX + 1];
// Function to check if the
// number is powerful
bool isPowerful(int n)
{
// First divide the number
// repeatedly by 2
while (n % 2 == 0)
{
int power = 0;
while (n % 2 == 0)
{
n /= 2;
power++;
}
// If only 2^1 divides
// n (not higher powers),
// then return false
if (power == 1)
return false;
}
// If n is not a power of 2 then
// this loop will execute
// repeat above process
for (int factor = 3; factor
<= sqrt(n); factor += 2)
{
// Find highest power of
// "factor" that divides n
int power = 0;
while (n % factor == 0)
{
n = n / factor;
power++;
}
// If only factor^1 divides n
// (not higher powers),
// then return false
if (power == 1)
return false;
}
// n must be 1 now if it is not
// a prime numenr. Since prime
// numbers are not powerful,
// we return false if n is not 1.
return (n == 1);
}
// Function to build the array
void BuildArray(int input[], int n)
{
for (int i = 0; i < n; i++)
{
// Check if input[i] is
// a Powerful number or not
if (powerful[input[i]])
arr[i] = 1;
else
arr[i] = 0;
}
return;
}
// A utility function to get the middle
// index from corner indexes.
int getMid(int s, int e)
{
return s + (e - s) / 2;
}
/* A recursive function that constructs
Segment Tree for array[ss..se].
si --> 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]
*/
void constructSTUtil(int si, int ss,
int se)
{
if (ss == se) {
// If there is one element
// in array
tree[si] = arr[ss];
return;
}
// 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
else {
int mid = getMid(ss, se);
constructSTUtil(2 * si + 1,
ss, mid);
constructSTUtil(2 * si + 2,
mid + 1, se);
tree[si] = tree[2 * si + 1]
+ tree[2 * si + 2];
}
}
/* A recursive function to update the
nodes which have the given index
in their range.
si --> 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]
ind --> Index of array to be updated
val --> The new value to be updated
*/
void updateValueUtil(int si, int ss, int se,
int idx, int val)
{
// Leaf node
if (ss == se) {
tree[si] = tree[si] - arr[idx] + val;
arr[idx] = val;
}
else {
int mid = getMid(ss, se);
// If idx is in the left child,
// recurse on the left child
if (ss <= idx and idx <= mid)
updateValueUtil(2 * si + 1, ss,
mid, idx, val);
// If idx is in the right child,
// recurse on the right child
else
updateValueUtil(2 * si + 2, mid + 1,
se, idx, val);
// Internal node will have the sum
// of both of its children
tree[si] = tree[2 * si + 1]
+ tree[2 * si + 2];
}
}
/* A recursive function to get the number
of Powerful numbers in a given
range of array indexes
si --> 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]
l & r --> Starting and ending indexes of
query range
*/
int queryPowerfulUtil(int si, int ss, int se,
int l, int r)
{
// If segment of this node is
// outside the given range
if (r < ss or se < l) {
return 0;
}
// If segment of this node is a part
// of given range, then return the
// number of composites
// in the segment
if (l <= ss and se <= r) {
return tree[si];
}
// If a part of this segment
// overlaps with the given range
int mid = getMid(ss, se);
int p1 = queryPowerfulUtil(2 * si + 1,
ss, mid, l,
r);
int p2 = queryPowerfulUtil(2 * si + 2,
mid + 1,
se, l, r);
return (p1 + p2);
}
void queryPowerful(int n, int l, int r)
{
printf("Number of Powerful numbers between %d to %d = %d\n",
l, r, queryPowerfulUtil(0, 0,
n - 1,
l, r));
}
void updateValue(int n, int ind, int val)
{
// If val is a Powerful number
// we will update 1 in tree
if (powerful[val])
updateValueUtil(0, 0, n - 1,
ind, 1);
else
updateValueUtil(0, 0, n - 1,
ind, 0);
}
void precomputePowerful()
{
memset(powerful, false,
sizeof(powerful));
// Computing all Powerful
// numbers till MAX
for (int i = 1; i <= MAX; i++)
{
// If the number is
// Powerful make
// powerful[i] = true
if (isPowerful(i))
powerful[i] = true;
}
}
// Driver Code
int main()
{
// Precompute all the powerful
// numbers till MAX
precomputePowerful();
// Input array
int input[] = { 4, 5, 18, 27, 40, 144 };
// Size of Input array
int n = sizeof(input) / sizeof(input[0]);
// Build the array.
BuildArray(input, n);
// Build segment tree from
// given array
constructSTUtil(0, 0, n - 1);
// Query 1: Query(L = 0, R = 3)
int l = 0, r = 3;
queryPowerful(n, l, r);
// Query 2: Update(i = 1, x = 9),
// i.e Update input[i] to x
int i = 1;
int val = 9;
updateValue(n, i, val);
// Query 3: Query(L = 0, R = 3)
queryPowerful(n, l, r);
return 0;
}
Java
// Java program to find the number
// of Powerful numbers in subarray
// using segment tree
import java.util.*;
class GFG{
static final int MAX = 100000;
// Size of segment tree = 2^{log(MAX)+1}
static int []tree = new int[3 * MAX];
static int []arr = new int[MAX];
static boolean []powerful = new boolean[MAX + 1];
// Function to check if the
// number is powerful
static boolean isPowerful(int n)
{
// First divide the number
// repeatedly by 2
while (n % 2 == 0)
{
int power = 0;
while (n % 2 == 0)
{
n /= 2;
power++;
}
// If only 2^1 divides
// n (not higher powers),
// then return false
if (power == 1)
return false;
}
// If n is not a power of 2 then
// this loop will execute
// repeat above process
for(int factor = 3;
factor <= Math.sqrt(n);
factor += 2)
{
// Find highest power of
// "factor" that divides n
int power = 0;
while (n % factor == 0)
{
n = n / factor;
power++;
}
// If only factor^1 divides n
// (not higher powers),
// then return false
if (power == 1)
return false;
}
// n must be 1 now if it is not
// a prime numenr. Since prime
// numbers are not powerful,
// we return false if n is not 1.
return (n == 1);
}
// Function to build the array
static void BuildArray(int input[], int n)
{
for(int i = 0; i < n; i++)
{
// Check if input[i] is
// a Powerful number or not
if (powerful[input[i]])
arr[i] = 1;
else
arr[i] = 0;
}
return;
}
// A utility function to get the middle
// index from corner indexes.
static int getMid(int s, int e)
{
return s + (e - s) / 2;
}
/* A recursive function that constructs
Segment Tree for array[ss..se].
si -. 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]
*/
static void constructSTUtil(int si, int ss,
int se)
{
if (ss == se)
{
// If there is one element
// in array
tree[si] = arr[ss];
return;
}
// 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
else
{
int mid = getMid(ss, se);
constructSTUtil(2 * si + 1,
ss, mid);
constructSTUtil(2 * si + 2,
mid + 1, se);
tree[si] = tree[2 * si + 1] +
tree[2 * si + 2];
}
}
/* A recursive function to update the
nodes which have the given index
in their range.
si -. 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]
ind -. Index of array to be updated
val -. The new value to be updated
*/
static void updateValueUtil(int si, int ss, int se,
int idx, int val)
{
// Leaf node
if (ss == se)
{
tree[si] = tree[si] - arr[idx] + val;
arr[idx] = val;
}
else
{
int mid = getMid(ss, se);
// If idx is in the left child,
// recurse on the left child
if (ss <= idx && idx <= mid)
updateValueUtil(2 * si + 1, ss,
mid, idx, val);
// If idx is in the right child,
// recurse on the right child
else
updateValueUtil(2 * si + 2, mid + 1,
se, idx, val);
// Internal node will have the sum
// of both of its children
tree[si] = tree[2 * si + 1] +
tree[2 * si + 2];
}
}
/* A recursive function to get the number
of Powerful numbers in a given
range of array indexes
si -. 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]
l & r -. Starting and ending indexes of
query range
*/
static int queryPowerfulUtil(int si, int ss,
int se, int l, int r)
{
// If segment of this node is
// outside the given range
if (r < ss || se < l)
{
return 0;
}
// If segment of this node is a part
// of given range, then return the
// number of composites
// in the segment
if (l <= ss && se <= r)
{
return tree[si];
}
// If a part of this segment
// overlaps with the given range
int mid = getMid(ss, se);
int p1 = queryPowerfulUtil(2 * si + 1,
ss, mid, l,
r);
int p2 = queryPowerfulUtil(2 * si + 2,
mid + 1,
se, l, r);
return (p1 + p2);
}
static void queryPowerful(int n, int l, int r)
{
System.out.printf("Number of Powerful numbers " +
"between %d to %d = %d\n", l, r,
queryPowerfulUtil(0, 0, n - 1,
l, r));
}
static void updateValue(int n, int ind, int val)
{
// If val is a Powerful number
// we will update 1 in tree
if (powerful[val])
updateValueUtil(0, 0, n - 1,
ind, 1);
else
updateValueUtil(0, 0, n - 1,
ind, 0);
}
static void precomputePowerful()
{
Arrays.fill(powerful, false);
// Computing all Powerful
// numbers till MAX
for(int i = 1; i <= MAX; i++)
{
// If the number is
// Powerful make
// powerful[i] = true
if (isPowerful(i))
powerful[i] = true;
}
}
// Driver Code
public static void main(String[] args)
{
// Precompute all the powerful
// numbers till MAX
precomputePowerful();
// Input array
int input[] = { 4, 5, 18, 27, 40, 144 };
// Size of Input array
int n = input.length;
// Build the array.
BuildArray(input, n);
// Build segment tree from
// given array
constructSTUtil(0, 0, n - 1);
// Query 1: Query(L = 0, R = 3)
int l = 0, r = 3;
queryPowerful(n, l, r);
// Query 2: Update(i = 1, x = 9),
// i.e Update input[i] to x
int i = 1;
int val = 9;
updateValue(n, i, val);
// Query 3: Query(L = 0, R = 3)
queryPowerful(n, l, r);
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 program to find the number
# of Powerful numbers in subarray
# using segment tree
import math
MAX = 100000
# Size of segment tree = 2^{log(MAX)+1}
tree = [0]*(3 * MAX)
arr = [0]*(MAX)
powerful = [False]*(MAX + 1)
# Function to check if the
# number is powerful
def isPowerful(n):
# First divide the number
# repeatedly by 2
while (n % 2 == 0):
power = 0
while (n % 2 == 0):
n = int(n / 2)
power += 1
# If only 2^1 divides
# n (not higher powers),
# then return false
if (power == 1):
return False
# If n is not a power of 2 then
# this loop will execute
# repeat above process
for factor in range(3, int(math.sqrt(n)) + 1, 2):
# Find highest power of
# "factor" that divides n
power = 0
while (n % factor == 0):
n = int(n / factor)
power += 1
# If only factor^1 divides n
# (not higher powers),
# then return false
if (power == 1):
return False
# n must be 1 now if it is not
# a prime number. Since prime
# numbers are not powerful,
# we return false if n is not 1.
return (n == 1)
# Function to build the array
def BuildArray(Input, n):
for i in range(n):
# Check if input[i] is
# a Powerful number or not
if (powerful[Input[i]]):
arr[i] = 1
else:
arr[i] = 0
return
# A utility function to get the middle
# index from corner indexes.
def getMid(s, e):
return s + int((e - s) / 2)
""" A recursive function that constructs
Segment Tree for array[ss..se].
si -. 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]
"""
def constructSTUtil(si, ss, se):
if (ss == se):
# If there is one element
# in array
tree[si] = arr[ss]
return
# 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
else:
mid = getMid(ss, se)
constructSTUtil(2 * si + 1, ss, mid)
constructSTUtil(2 * si + 2, mid + 1, se)
tree[si] = tree[2 * si + 1] + tree[2 * si + 2]
""" A recursive function to update the
nodes which have the given index
in their range.
si -. 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]
ind -. Index of array to be updated
val -. The new value to be updated
"""
def updateValueUtil(si, ss, se, idx, val):
# Leaf node
if (ss == se):
tree[si] = tree[si] - arr[idx] + val
arr[idx] = val
else:
mid = getMid(ss, se)
# If idx is in the left child,
# recurse on the left child
if (ss <= idx and idx <= mid):
updateValueUtil(2 * si + 1, ss, mid, idx, val)
# If idx is in the right child,
# recurse on the right child
else:
updateValueUtil(2 * si + 2, mid + 1, se, idx, val)
# Internal node will have the sum
# of both of its children
tree[si] = tree[2 * si + 1] + tree[2 * si + 2]
""" A recursive function to get the number
of Powerful numbers in a given
range of array indexes
si -. 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]
l & r -. Starting and ending indexes of
query range
"""
def queryPowerfulUtil(si, ss, se, l, r):
# If segment of this node is
# outside the given range
if (r < ss or se < l):
return 0
# If segment of this node is a part
# of given range, then return the
# number of composites
# in the segment
if (l <= ss and se <= r):
return tree[si]
# If a part of this segment
# overlaps with the given range
mid = getMid(ss, se)
p1 = queryPowerfulUtil(2 * si + 1, ss, mid, l, r)
p2 = queryPowerfulUtil(2 * si + 2, mid + 1, se, l, r)
return (p1 + p2)
def queryPowerful(n, l, r):
print("Number of Powerful numbers between", l, "to", r, "=", queryPowerfulUtil(0, 0, n - 1, l, r))
def updateValue(n, ind, val):
# If val is a Powerful number
# we will update 1 in tree
if (powerful[val]):
updateValueUtil(0, 0, n - 1, ind, 1)
else:
updateValueUtil(0, 0, n - 1, ind, 0)
def precomputePowerful():
for i in range(MAX + 1):
powerful[i] = False
# Computing all Powerful
# numbers till MAX
for i in range(1, MAX + 1):
# If the number is
# Powerful make
# powerful[i] = true
if (isPowerful(i)):
powerful[i] = True
# Precompute all the powerful
# numbers till MAX
precomputePowerful()
# Input array
Input = [ 4, 5, 18, 27, 40, 144 ]
# Size of Input array
n = len(Input)
# Build the array.
BuildArray(Input, n)
# Build segment tree from
# given array
constructSTUtil(0, 0, n - 1)
# Query 1: Query(L = 0, R = 3)
l, r = 0, 3
queryPowerful(n, l, r)
# Query 2: Update(i = 1, x = 9),
# i.e Update input[i] to x
i = 1
val = 9
updateValue(n, i, val)
# Query 3: Query(L = 0, R = 3)
queryPowerful(n, l, r)
# This code is contributed by divyesh072019.
C#
// C# program to find the number
// of Powerful numbers in subarray
// using segment tree
using System;
class GFG{
static readonly int MAX = 100000;
// Size of segment tree = 2^{log(MAX)+1}
static int []tree = new int[3 * MAX];
static int []arr = new int[MAX];
static bool []powerful = new bool[MAX + 1];
// Function to check if the
// number is powerful
static bool isPowerful(int n)
{
// First divide the number
// repeatedly by 2
while (n % 2 == 0)
{
int power = 0;
while (n % 2 == 0)
{
n /= 2;
power++;
}
// If only 2^1 divides
// n (not higher powers),
// then return false
if (power == 1)
return false;
}
// If n is not a power of 2 then
// this loop will execute
// repeat above process
for(int factor = 3;
factor <= Math.Sqrt(n);
factor += 2)
{
// Find highest power of
// "factor" that divides n
int power = 0;
while (n % factor == 0)
{
n = n / factor;
power++;
}
// If only factor^1 divides n
// (not higher powers),
// then return false
if (power == 1)
return false;
}
// n must be 1 now if it is not
// a prime numenr. Since prime
// numbers are not powerful,
// we return false if n is not 1.
return (n == 1);
}
// Function to build the array
static void BuildArray(int []input, int n)
{
for(int i = 0; i < n; i++)
{
// Check if input[i] is
// a Powerful number or not
if (powerful[input[i]])
arr[i] = 1;
else
arr[i] = 0;
}
return;
}
// A utility function to get the middle
// index from corner indexes.
static int getMid(int s, int e)
{
return s + (e - s) / 2;
}
/* A recursive function that constructs
Segment Tree for array[ss..se].
si -. 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]
*/
static void constructSTUtil(int si, int ss,
int se)
{
if (ss == se)
{
// If there is one element
// in array
tree[si] = arr[ss];
return;
}
// 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
else
{
int mid = getMid(ss, se);
constructSTUtil(2 * si + 1,
ss, mid);
constructSTUtil(2 * si + 2,
mid + 1, se);
tree[si] = tree[2 * si + 1] +
tree[2 * si + 2];
}
}
/* A recursive function to update the
nodes which have the given index
in their range.
si -. 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]
ind -. Index of array to be updated
val -. The new value to be updated
*/
static void updateValueUtil(int si, int ss, int se,
int idx, int val)
{
// Leaf node
if (ss == se)
{
tree[si] = tree[si] - arr[idx] + val;
arr[idx] = val;
}
else
{
int mid = getMid(ss, se);
// If idx is in the left child,
// recurse on the left child
if (ss <= idx && idx <= mid)
updateValueUtil(2 * si + 1, ss,
mid, idx, val);
// If idx is in the right child,
// recurse on the right child
else
updateValueUtil(2 * si + 2, mid + 1,
se, idx, val);
// Internal node will have the sum
// of both of its children
tree[si] = tree[2 * si + 1] +
tree[2 * si + 2];
}
}
/* A recursive function to get the number
of Powerful numbers in a given
range of array indexes
si -. 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]
l & r -. Starting and ending indexes of
query range
*/
static int queryPowerfulUtil(int si, int ss,
int se, int l, int r)
{
// If segment of this node is
// outside the given range
if (r < ss || se < l)
{
return 0;
}
// If segment of this node is a part
// of given range, then return the
// number of composites
// in the segment
if (l <= ss && se <= r)
{
return tree[si];
}
// If a part of this segment
// overlaps with the given range
int mid = getMid(ss, se);
int p1 = queryPowerfulUtil(2 * si + 1,
ss, mid, l,
r);
int p2 = queryPowerfulUtil(2 * si + 2,
mid + 1,
se, l, r);
return (p1 + p2);
}
static void queryPowerful(int n, int l, int r)
{
Console.WriteLine("Number of Powerful numbers " +
"between " + l +" to "+r+" = "+
queryPowerfulUtil(0, 0, n - 1,
l, r));
}
static void updateValue(int n, int ind, int val)
{
// If val is a Powerful number
// we will update 1 in tree
if (powerful[val])
updateValueUtil(0, 0, n - 1,
ind, 1);
else
updateValueUtil(0, 0, n - 1,
ind, 0);
}
static void precomputePowerful()
{
for(int i = 0; i <= MAX; i++)
powerful[i] = false;
// Computing all Powerful
// numbers till MAX
for(int i = 1; i <= MAX; i++)
{
// If the number is
// Powerful make
// powerful[i] = true
if (isPowerful(i))
powerful[i] = true;
}
}
// Driver Code
public static void Main(String[] args)
{
// Precompute all the powerful
// numbers till MAX
precomputePowerful();
// Input array
int []input = { 4, 5, 18, 27, 40, 144 };
// Size of Input array
int n = input.Length;
// Build the array.
BuildArray(input, n);
// Build segment tree from
// given array
constructSTUtil(0, 0, n - 1);
// Query 1: Query(L = 0, R = 3)
int l = 0, r = 3;
queryPowerful(n, l, r);
// Query 2: Update(i = 1, x = 9),
// i.e Update input[i] to x
int i = 1;
int val = 9;
updateValue(n, i, val);
// Query 3: Query(L = 0, R = 3)
queryPowerful(n, l, r);
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// JavaScript program to find the number
// of Powerful numbers in subarray
// using segment tree
let MAX = 100000;
// Size of segment tree = 2^{log(MAX)+1}
let tree = new Array(3 * MAX);
let arr = new Array(MAX);
let powerful = new Array(MAX + 1);
// Function to check if the
// number is powerful
function isPowerful(n)
{
// First divide the number
// repeatedly by 2
while (n % 2 == 0)
{
let power = 0;
while (n % 2 == 0)
{
n = parseInt(n / 2, 10);
power++;
}
// If only 2^1 divides
// n (not higher powers),
// then return false
if (power == 1)
return false;
}
// If n is not a power of 2 then
// this loop will execute
// repeat above process
for(let factor = 3;
factor <= Math.sqrt(n);
factor += 2)
{
// Find highest power of
// "factor" that divides n
let power = 0;
while (n % factor == 0)
{
n = parseInt(n / factor, 10);
power++;
}
// If only factor^1 divides n
// (not higher powers),
// then return false
if (power == 1)
return false;
}
// n must be 1 now if it is not
// a prime numenr. Since prime
// numbers are not powerful,
// we return false if n is not 1.
return (n == 1);
}
// Function to build the array
function BuildArray(input, n)
{
for(let i = 0; i < n; i++)
{
// Check if input[i] is
// a Powerful number or not
if (powerful[input[i]])
arr[i] = 1;
else
arr[i] = 0;
}
return;
}
// A utility function to get the middle
// index from corner indexes.
function getMid(s, e)
{
return s + parseInt((e - s) / 2, 10);
}
/* A recursive function that constructs
Segment Tree for array[ss..se].
si -. 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]
*/
function constructSTUtil(si, ss, se)
{
if (ss == se)
{
// If there is one element
// in array
tree[si] = arr[ss];
return;
}
// 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
else
{
let mid = getMid(ss, se);
constructSTUtil(2 * si + 1,
ss, mid);
constructSTUtil(2 * si + 2,
mid + 1, se);
tree[si] = tree[2 * si + 1] +
tree[2 * si + 2];
}
}
/* A recursive function to update the
nodes which have the given index
in their range.
si -. 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]
ind -. Index of array to be updated
val -. The new value to be updated
*/
function updateValueUtil(si, ss, se, idx, val)
{
// Leaf node
if (ss == se)
{
tree[si] = tree[si] - arr[idx] + val;
arr[idx] = val;
}
else
{
let mid = getMid(ss, se);
// If idx is in the left child,
// recurse on the left child
if (ss <= idx && idx <= mid)
updateValueUtil(2 * si + 1, ss,
mid, idx, val);
// If idx is in the right child,
// recurse on the right child
else
updateValueUtil(2 * si + 2, mid + 1,
se, idx, val);
// Internal node will have the sum
// of both of its children
tree[si] = tree[2 * si + 1] +
tree[2 * si + 2];
}
}
/* A recursive function to get the number
of Powerful numbers in a given
range of array indexes
si -. 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]
l & r -. Starting and ending indexes of
query range
*/
function queryPowerfulUtil(si, ss, se, l, r)
{
// If segment of this node is
// outside the given range
if (r < ss || se < l)
{
return 0;
}
// If segment of this node is a part
// of given range, then return the
// number of composites
// in the segment
if (l <= ss && se <= r)
{
return tree[si];
}
// If a part of this segment
// overlaps with the given range
let mid = getMid(ss, se);
let p1 = queryPowerfulUtil(2 * si + 1,
ss, mid, l,
r);
let p2 = queryPowerfulUtil(2 * si + 2,
mid + 1,
se, l, r);
return (p1 + p2);
}
function queryPowerful(n, l, r)
{
document.write("Number of Powerful numbers " +
"between " + l +" to "+r+" = "+
queryPowerfulUtil(0, 0, n - 1,
l, r) + "</br>");
}
function updateValue(n, ind, val)
{
// If val is a Powerful number
// we will update 1 in tree
if (powerful[val])
updateValueUtil(0, 0, n - 1,
ind, 1);
else
updateValueUtil(0, 0, n - 1,
ind, 0);
}
function precomputePowerful()
{
for(let i = 0; i <= MAX; i++)
powerful[i] = false;
// Computing all Powerful
// numbers till MAX
for(let i = 1; i <= MAX; i++)
{
// If the number is
// Powerful make
// powerful[i] = true
if (isPowerful(i))
powerful[i] = true;
}
}
// Precompute all the powerful
// numbers till MAX
precomputePowerful();
// Input array
let input = [ 4, 5, 18, 27, 40, 144 ];
// Size of Input array
let n = input.length;
// Build the array.
BuildArray(input, n);
// Build segment tree from
// given array
constructSTUtil(0, 0, n - 1);
// Query 1: Query(L = 0, R = 3)
let l = 0, r = 3;
queryPowerful(n, l, r);
// Query 2: Update(i = 1, x = 9),
// i.e Update input[i] to x
let i = 1;
let val = 9;
updateValue(n, i, val);
// Query 3: Query(L = 0, R = 3)
queryPowerful(n, l, r);
</script>
Producción:
Number of Powerful numbers between 0 to 3 = 2 Number of Powerful numbers between 0 to 3 = 3
Complejidad de tiempo: O (logN) por consulta
Publicación traducida automáticamente
Artículo escrito por saurabhshadow y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA