Sum of prime numbers in range [ L , R ] from given Array for Q queries | Java program for the above approach ; Function to find the prime numbers ; 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 ; Check if prime [ p ] is not changed , then it is a prime ; 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 ; Function to get the middle index from corner indexes ; Function to get the sum of values in the given range of the array ; If segment of this node is a part of given range , then return the sum of the segment ; If segment of this node is outside the given range ; If a part of this segment overlaps with the given range ; Function to update the nodes which have the given index in their range ; If the input index lies outside the range of this segment ; If the input index is in range of this node , then update the value of the node and its children ; Function to update a value in input array and segment tree ; Check for erroneous input index ; Get the difference between new value and old value ; Update the value in array ; Update the values of nodes in segment tree only if either previous value or new value or both are prime ; If only new value is prime ; If only new value is prime ; If both are prime ; Return sum of elements in range from index qs ( query start ) to qe ( query end ) . It mainly uses getSumUtil ( ) ; Check for erroneous input values ; Function that constructs Segment Tree ; If there is one element in array , store it in current node of segment tree and return ; Only add those elements in segment tree which are prime ; If there are more than one elements , then recur for left and right subtrees and store the sum of values in this node ; Function to construct segment tree from given array ; Height of segment tree ; Maximum size of segment tree ; Allocate memory ; Fill the allocated memory st ; Return the constructed segment tree ; Driver Code ; Function call ; Build segment tree from given array ; Print sum of values in array from index 1 to 3 ; Update : set arr [ 1 ] = 10 and update corresponding segment tree nodes ; Find sum after the value is updated
import java . io . * ; import java . util . * ; class GFG { static int MAX = 1000001 ; static int prime [ ] = new int [ MAX ] ; static void SieveOfEratosthenes ( ) { Arrays . fill ( prime , 1 ) ; for ( int p = 2 ; p * p <= MAX ; p ++ ) { if ( prime [ p ] == 1 ) { for ( int i = p * p ; i <= MAX - 1 ; i += p ) prime [ i ] = 0 ; } } } static int getMid ( int s , int e ) { return s + ( e - s ) / 2 ; } static int getSumUtil ( int [ ] st , int ss , int se , int qs , int qe , int si ) { if ( qs <= ss && qe >= se ) return st [ si ] ; if ( se < qs ss > qe ) return 0 ; 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 ) ; } static void updateValueUtil ( int [ ] st , int ss , int se , int i , int diff , int si ) { if ( i < ss i > se ) return ; 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 ) ; } } static void updateValue ( int arr [ ] , int [ ] st , int n , int i , int new_val ) { if ( i < 0 i > n - 1 ) { System . out . print ( " - 1" ) ; return ; } int diff = new_val - arr [ i ] ; int prev_val = arr [ i ] ; arr [ i ] = new_val ; if ( ( prime [ new_val ] prime [ prev_val ] ) != 0 ) { if ( prime [ prev_val ] == 0 ) updateValueUtil ( st , 0 , n - 1 , i , new_val , 0 ) ; else if ( prime [ new_val ] == 0 ) updateValueUtil ( st , 0 , n - 1 , i , - prev_val , 0 ) ; else updateValueUtil ( st , 0 , n - 1 , i , diff , 0 ) ; } } static int getSum ( int [ ] st , int n , int qs , int qe ) { if ( qs < 0 qe > n - 1 qs > qe ) { System . out . println ( " - 1" ) ; return - 1 ; } return getSumUtil ( st , 0 , n - 1 , qs , qe , 0 ) ; } static int constructSTUtil ( int arr [ ] , int ss , int se , int [ ] st , int si ) { if ( ss == se ) { if ( prime [ arr [ ss ] ] != 0 ) st [ si ] = arr [ ss ] ; else st [ si ] = 0 ; return st [ si ] ; } 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 ] ; } static int [ ] constructST ( int arr [ ] , int n ) { int x = ( int ) ( Math . ceil ( Math . log ( n ) / Math . log ( 2 ) ) ) ; int max_size = 2 * ( int ) Math . pow ( 2 , x ) - 1 ; int [ ] st = new int [ max_size ] ; constructSTUtil ( arr , 0 , n - 1 , st , 0 ) ; return st ; } 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 } } ; SieveOfEratosthenes ( ) ; int [ ] st = constructST ( arr , n ) ; System . out . println ( getSum ( st , n , 1 , 3 ) ) ; updateValue ( arr , st , n , 1 , 10 ) ; System . out . println ( getSum ( st , n , 1 , 3 ) ) ; } }