Dada una array arr[] del tamaño de N seguida de una array de consultas Q , de los siguientes dos tipos:
- Tipo de consulta 1: dados dos números enteros L y R, encuentre la suma de los elementos primos del índice L a R donde 0 <= L <= R <= N-1.
- Tipo de consulta 2: Dados dos enteros i y X, cambie arr[i] = X donde 0 <= i <= n-1.
Nota: Cada primer índice de la subconsulta determina el tipo de consulta a responder.
Ejemplo:
Entrada: arr[] = {1, 3, 5, 7, 9, 11}, Q = { { 1, 1, 3}, {2, 1, 10}, {1, 1, 3 } }
Salida:
15
12
Explicación:
La primera consulta es de tipo 1, por lo que la respuesta es (3 + 5 + 7), = 15
La segunda consulta es de tipo 2, por lo que arr[1] = 10
La tercera consulta es de tipo 1, donde arr[1] = 10, que no es primo, por lo que la respuesta es (5 + 7) = 12Entrada: arr[] = {1, 2, 35, 7, 14, 11}, Q = { {2, 4, 3}, {1, 4, 5 } }
Salida: 14
Explicación:
la primera consulta es de tipo 2 , Entonces actualice arr[4] = 3 La
segunda consulta es de tipo 1, ya que arr[4] = 3, que es primo. Entonces la respuesta es (3 + 11) = 14
Enfoque ingenuo: la idea es iterar para cada consulta entre L a R y realizar la operación requerida en la array dada.
Complejidad de tiempo: O(Q * N * (O(sqrt(max(arr[i]))
Enfoque: Para optimizar el problema, utilice el árbol de segmentos y la criba de Eratóstenes.
- Primero, cree una array booleana que marcará los números primos.
- Ahora, mientras crea el árbol de segmentos, solo agregue esos elementos de array como Nodes de hoja que son primos.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int const MAX = 1000001;
bool prime[MAX];
// Function to find the prime numbers
void SieveOfEratosthenes()
{
// Create a boolean array prime[]
// and initialize all entries it as true
// A value in prime[i] will
// finally be false if i is Not a prime
memset(prime, true, sizeof(prime));
for (int p = 2; p * p <= MAX; p++) {
// Check if prime[p] is not
// changed, then it is a prime
if (prime[p] == true) {
// Update all multiples of p
// greater than or equal to
// the square of it numbers
// which are multiple of p
// and are less than p^2 are
// already been marked
for (int i = p * p; i <= MAX; i += p)
prime[i] = false;
}
}
}
// Function to get the middle
// index from corner indexes
int getMid(int s, int e)
{
return s + (e - s) / 2;
}
// Function to get the sum of
// values in the given range
// of the array
int getSumUtil(int* st, int ss,
int se, int qs,
int qe, int si)
{
// If segment of this node is a
// part of given range, then
// return the sum of the segment
if (qs <= ss && qe >= se)
return st[si];
// 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 getSumUtil(st, ss, mid,
qs, qe,
2 * si + 1)
+ getSumUtil(st, mid + 1,
se, qs, qe,
2 * si + 2);
}
// Function to update the nodes which
// have the given index in their range
void updateValueUtil(int* st, int ss,
int se, int i,
int diff, int si)
{
// 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
// input array and 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) {
cout << "-1";
return;
}
// Get the difference between
// new value and old value
int diff = new_val - arr[i];
int prev_val = arr[i];
// Update the value in array
arr[i] = new_val;
// Update the values of
// nodes in segment tree
// only if either previous
// value or new value
// or both are prime
if (prime[new_val]
|| prime[prev_val]) {
// If only new value is prime
if (!prime[prev_val])
updateValueUtil(st, 0, n - 1,
i, new_val, 0);
// If only new value is prime
else if (!prime[new_val])
updateValueUtil(st, 0, n - 1,
i, -prev_val, 0);
// If both are prime
else
updateValueUtil(st, 0, n - 1,
i, diff, 0);
}
}
// Return sum of elements in range
// from index qs (query start) to qe
// (query end). It mainly uses getSumUtil()
int getSum(int* st, int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n - 1 || qs > qe) {
cout << "-1";
return -1;
}
return getSumUtil(st, 0, n - 1,
qs, qe, 0);
}
// Function that constructs Segment Tree
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) {
// Only add those elements in segment
// tree which are prime
if (prime[arr[ss]])
st[si] = arr[ss];
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 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 segment
// tree from given array
int* constructST(int arr[], int n)
{
// Allocate memory for the 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;
// Allocate memory
int* st = new int[max_size];
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0);
// Return the constructed segment tree
return st;
}
// Driver code
int main()
{
int arr[] = { 1, 3, 5, 7, 9, 11 };
int n = sizeof(arr) / sizeof(arr[0]);
int Q[3][3]
= { { 1, 1, 3 },
{ 2, 1, 10 },
{ 1, 1, 3 } };
// Function call
SieveOfEratosthenes();
// Build segment tree from given array
int* st = constructST(arr, n);
// Print sum of values in
// array from index 1 to 3
cout << getSum(st, n, 1, 3) << endl;
// Update: set arr[1] = 10
// and update corresponding
// segment tree nodes
updateValue(arr, st, n, 1, 10);
// Find sum after the value is updated
cout << getSum(st, n, 1, 3) << endl;
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
static int MAX = 1000001;
static int prime[] = new int[MAX];
// Function to find the prime numbers
static void SieveOfEratosthenes()
{
// Create a boolean array prime[]
// and initialize all entries it as true
// A value in prime[i] will
// finally be false if i is Not a prime
Arrays.fill(prime, 1);
for (int p = 2; p * p <= MAX; p++)
{
// Check if prime[p] is not
// changed, then it is a prime
if (prime[p] == 1)
{
// Update all multiples of p
// greater than or equal to
// the square of it numbers
// which are multiple of p
// and are less than p^2 are
// already been marked
for (int i = p * p; i <= MAX - 1; i += p)
prime[i] = 0;
}
}
}
// Function to get the middle
// index from corner indexes
static int getMid(int s, int e)
{
return s + (e - s) / 2;
}
// Function to get the sum of
// values in the given range
// of the array
static int getSumUtil(int[] st, int ss,
int se, int qs,
int qe, int si)
{
// If segment of this node is a
// part of given range, then
// return the sum of the segment
if (qs <= ss && qe >= se)
return st[si];
// 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 getSumUtil(st, ss, mid,
qs, qe,
2 * si + 1)
+ getSumUtil(st, mid + 1,
se, qs, qe,
2 * si + 2);
}
// Function to update the nodes which
// have the given index in their range
static void updateValueUtil(int[] st, int ss,
int se, int i,
int diff, int si)
{
// 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
// input array and 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)
{
System.out.print("-1");
return;
}
// Get the difference between
// new value and old value
int diff = new_val - arr[i];
int prev_val = arr[i];
// Update the value in array
arr[i] = new_val;
// Update the values of
// nodes in segment tree
// only if either previous
// value or new value
// or both are prime
if ((prime[new_val] | prime[prev_val]) != 0)
{
// If only new value is prime
if (prime[prev_val] == 0)
updateValueUtil(st, 0, n - 1,
i, new_val, 0);
// If only new value is prime
else if (prime[new_val] == 0)
updateValueUtil(st, 0, n - 1, i, -prev_val, 0);
// If both are prime
else
updateValueUtil(st, 0, n - 1,
i, diff, 0);
}
}
// Return sum of elements in range
// from index qs (query start) to qe
// (query end). It mainly uses getSumUtil()
static int getSum(int[] st, int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n - 1 || qs > qe)
{
System.out.println( "-1");
return -1;
}
return getSumUtil(st, 0, n - 1,
qs, qe, 0);
}
// Function that constructs Segment Tree
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) {
// Only add those elements in segment
// tree which are prime
if (prime[arr[ss]] != 0)
st[si] = arr[ss];
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 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 segment
// tree from given array
static int[] constructST(int arr[], int n)
{
// Allocate memory for the 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;
// Allocate memory
int[] st = new int[max_size];
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0);
// Return the constructed segment tree
return st;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 3, 5, 7, 9, 11 };
int n = arr.length;
int Q[][] = { { 1, 1, 3 },
{ 2, 1, 10 },
{ 1, 1, 3 } };
// Function call
SieveOfEratosthenes();
// Build segment tree from given array
int[] st = constructST(arr, n);
// Print sum of values in
// array from index 1 to 3
System.out.println(getSum(st, n, 1, 3));
// Update: set arr[1] = 10
// and update corresponding
// segment tree nodes
updateValue(arr, st, n, 1, 10);
// Find sum after the value is updated
System.out.println(getSum(st, n, 1, 3));
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python3 program for the above approach import math MAX = 1000001 # Create a boolean array prime[] # and initialize all entries it as true # A value in prime[i] will # finally be false if i is Not a prime prime = [True] * MAX # Function to find prime numbers def SieveOfEratosthenes(): p = 2 while p * p <= MAX: # Check if prime[p] is not # changed, then it is a prime if prime[p] == True: # Update all multiples of p # greater than or equal to # the square of it numbers # which are multiple of p # and are less than p^2 are # already been marked for i in range(p * p, MAX, p): prime[i] = False p += 1 # Function to get the middle # index from corner indexes def getMid(s, e): return s + (e - s) // 2 # Function to get the sum of # values in the given range # of the array def getSumUtil(st, ss, se, qs, qe, si): # If segment of this node is a # part of given range, then # return the sum of the segment if qs <= ss and qe >= se: return st[si] # 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 (getSumUtil(st, ss, mid, qs, qe, 2 * si + 1) + getSumUtil(st, mid + 1, se, qs, qe, 2 * si + 2)) # Function to update the nodes which # have the given index in their range def updateValueUtil(st, ss, se, i, diff, si): # 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 # input array and segment tree def updateValue(arr, st, n, i, new_val): # Check for errorneous input index if i < 0 or i > n - 1: print(-1) return # Get the difference between # new value and old value diff = new_val - arr[i] prev_val = arr[i] # Update the value in array arr[i] = new_val # Update the values of nodes # in segment tree only if # either previous value or # new value or both are prime if prime[new_val] or prime[prev_val]: # If only new value is prime if not prime[prev_val]: updateValueUtil(st, 0, n - 1, i, new_val, 0) # If only old value is prime elif not prime[new_val]: updateValueUtil(st, 0, n - 1, i, -prev_val, 0) # If both are prime else: updateValueUtil(st, 0, n - 1, i, diff, 0) # Return sum of elements in range # from index qs (query start) to qe # (query end). It mainly uses getSumUtil() def getSum(st, n, qs, qe): # Check for erroneous input values if qs < 0 or qe > n-1 or qs > qe: return -1 return getSumUtil(st, 0, n - 1, qs, qe, 0) # Function that constructs the Segment Tree 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: # Only add those elements in segment # tree which are prime if prime[arr[ss]]: st[si] = arr[ss] 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 values in this node mid = getMid(ss, se) st[si] = (constructSTUtil(arr, ss, mid, st, 2 * si + 1) + constructSTUtil(arr, mid + 1, se, st, 2 * si + 2)) return st[si] # Function to construct segment # tree from given array def constructST(arr, n): # Allocate memory for the 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 # Allocate memory st = [0] * max_size # Fill the allocated memory st constructSTUtil(arr, 0, n - 1, st, 0) # Return the constructed segment tree return st # Driver code arr = [ 1, 3, 5, 7, 9, 11 ] n = len(arr) Q = [ [ 1, 1, 3 ], [ 2, 1, 10 ], [ 1, 1, 3 ] ] # Function call SieveOfEratosthenes() # Build segment tree from given array st = constructST(arr, n) # Print sum of values in # array from index 1 to 3 print(getSum(st, n, 1, 3)) # Update: set arr[1] = 10 # and update corresponding # segment tree nodes updateValue(arr, st, n, 1, 10) # Find sum after value is updated print(getSum(st, n, 1, 3)) # This code is contributed by Stuti Pathak
C#
// C# program for the above approach
using System;
class GFG {
static int MAX = 1000001;
static int[] prime = new int[MAX];
// Function to find the prime numbers
static void SieveOfEratosthenes()
{
// Create a boolean array prime[]
// and initialize all entries it as true
// A value in prime[i] will
// finally be false if i is Not a prime
Array.Fill(prime, 1);
for (int p = 2; p * p <= MAX; p++)
{
// Check if prime[p] is not
// changed, then it is a prime
if (prime[p] == 1)
{
// Update all multiples of p
// greater than or equal to
// the square of it numbers
// which are multiple of p
// and are less than p^2 are
// already been marked
for (int i = p * p; i <= MAX - 1; i += p)
prime[i] = 0;
}
}
}
// Function to get the middle
// index from corner indexes
static int getMid(int s, int e)
{
return s + (e - s) / 2;
}
// Function to get the sum of
// values in the given range
// of the array
static int getSumUtil(int[] st, int ss,
int se, int qs,
int qe, int si)
{
// If segment of this node is a
// part of given range, then
// return the sum of the segment
if (qs <= ss && qe >= se)
return st[si];
// 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 getSumUtil(st, ss, mid,
qs, qe,
2 * si + 1)
+ getSumUtil(st, mid + 1,
se, qs, qe,
2 * si + 2);
}
// Function to update the nodes which
// have the given index in their range
static void updateValueUtil(int[] st, int ss,
int se, int i,
int diff, int si)
{
// 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
// input array and 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("-1");
return;
}
// Get the difference between
// new value and old value
int diff = new_val - arr[i];
int prev_val = arr[i];
// Update the value in array
arr[i] = new_val;
// Update the values of
// nodes in segment tree
// only if either previous
// value or new value
// or both are prime
if ((prime[new_val] | prime[prev_val]) != 0)
{
// If only new value is prime
if (prime[prev_val] == 0)
updateValueUtil(st, 0, n - 1,
i, new_val, 0);
// If only new value is prime
else if (prime[new_val] == 0)
updateValueUtil(st, 0, n - 1, i, -prev_val, 0);
// If both are prime
else
updateValueUtil(st, 0, n - 1,
i, diff, 0);
}
}
// Return sum of elements in range
// from index qs (query start) to qe
// (query end). It mainly uses getSumUtil()
static int getSum(int[] st, int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n - 1 || qs > qe)
{
Console.WriteLine( "-1");
return -1;
}
return getSumUtil(st, 0, n - 1,
qs, qe, 0);
}
// Function that constructs Segment Tree
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) {
// Only add those elements in segment
// tree which are prime
if (prime[arr[ss]] != 0)
st[si] = arr[ss];
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 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 segment
// tree from given array
static int[] constructST(int[] arr, int n)
{
// Allocate memory for the 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;
// 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
static void Main()
{
int[] arr = { 1, 3, 5, 7, 9, 11 };
int n = arr.Length;
// Function call
SieveOfEratosthenes();
// Build segment tree from given array
int[] st = constructST(arr, n);
// Print sum of values in
// array from index 1 to 3
Console.WriteLine(getSum(st, n, 1, 3));
// Update: set arr[1] = 10
// and update corresponding
// segment tree nodes
updateValue(arr, st, n, 1, 10);
// Find sum after the value is updated
Console.WriteLine(getSum(st, n, 1, 3));
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript program for the above approach
let MAX = 1000001;
let prime = new Array(MAX);
// Function to find the prime numbers
function SieveOfEratosthenes()
{
// Create a boolean array prime[]
// and initialize all entries it as true
// A value in prime[i] will
// finally be false if i is Not a prime
prime.fill(1);
for (let p = 2; p * p <= MAX; p++)
{
// Check if prime[p] is not
// changed, then it is a prime
if (prime[p] == 1)
{
// Update all multiples of p
// greater than or equal to
// the square of it numbers
// which are multiple of p
// and are less than p^2 are
// already been marked
for (let i = p * p; i <= MAX - 1; i += p)
prime[i] = 0;
}
}
}
// Function to get the middle
// index from corner indexes
function getMid(s, e)
{
return s + parseInt((e - s) / 2, 10);
}
// Function to get the sum of
// values in the given range
// of the array
function getSumUtil(st, ss, se, qs, qe, si)
{
// If segment of this node is a
// part of given range, then
// return the sum of the segment
if (qs <= ss && qe >= se)
return st[si];
// 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 getSumUtil(st, ss, mid,
qs, qe,
2 * si + 1)
+ getSumUtil(st, mid + 1,
se, qs, qe,
2 * si + 2);
}
// Function to update the nodes which
// have the given index in their range
function updateValueUtil(st, ss, se, i, diff, si)
{
// 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
// input array and segment tree
function updateValue(arr, st, n, i, new_val)
{
// Check for erroneous input index
if (i < 0 || i > n - 1)
{
document.write("-1");
return;
}
// Get the difference between
// new value and old value
let diff = new_val - arr[i];
let prev_val = arr[i];
// Update the value in array
arr[i] = new_val;
// Update the values of
// nodes in segment tree
// only if either previous
// value or new value
// or both are prime
if ((prime[new_val] | prime[prev_val]) != 0)
{
// If only new value is prime
if (prime[prev_val] == 0)
updateValueUtil(st, 0, n - 1,
i, new_val, 0);
// If only new value is prime
else if (prime[new_val] == 0)
updateValueUtil(st, 0, n - 1, i, -prev_val, 0);
// If both are prime
else
updateValueUtil(st, 0, n - 1,
i, diff, 0);
}
}
// Return sum of elements in range
// from index qs (query start) to qe
// (query end). It mainly uses getSumUtil()
function getSum(st, n, qs, qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n - 1 || qs > qe)
{
document.write( "-1");
return -1;
}
return getSumUtil(st, 0, n - 1,
qs, qe, 0);
}
// Function that constructs Segment Tree
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) {
// Only add those elements in segment
// tree which are prime
if (prime[arr[ss]] != 0)
st[si] = arr[ss];
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 values in this node
let 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 segment
// tree from given array
function constructST(arr, n)
{
// Allocate memory for the segment tree
// Height of segment tree
let x = parseInt((Math.ceil(Math.log(n)/Math.log(2))), 10);
// 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;
}
let arr = [ 1, 3, 5, 7, 9, 11 ];
let n = arr.length;
let Q = [ [ 1, 1, 3 ],
[ 2, 1, 10 ],
[ 1, 1, 3 ] ];
// Function call
SieveOfEratosthenes();
// Build segment tree from given array
let st = constructST(arr, n);
// Print sum of values in
// array from index 1 to 3
document.write(getSum(st, n, 1, 3) + "</br>");
// Update: set arr[1] = 10
// and update corresponding
// segment tree nodes
updateValue(arr, st, n, 1, 10);
// Find sum after the value is updated
document.write(getSum(st, n, 1, 3) + "</br>");
// This code is contributed by mukesh07.
</script>
Producción:
15 12
Complejidad temporal: O(Q * log N)
Espacio auxiliar: O(N)