Sum of prime numbers in range [ L , R ] from given Array for Q queries | Python3 program for the above approach ; Create a boolean array prime [ ] and initialize all entires it as true A value in prime [ i ] will finally be false if i is Not a prime ; Function to find prime numbers ; 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 errorneous imput 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 old 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 the 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 value is updated
import math NEW_LINE MAX = 1000001 NEW_LINE prime = [ True ] * MAX NEW_LINE def SieveOfEratosthenes ( ) : NEW_LINE INDENT p = 2 NEW_LINE while p * p <= MAX : NEW_LINE INDENT if prime [ p ] == True : NEW_LINE INDENT for i in range ( p * p , MAX , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT DEDENT def getMid ( s , e ) : NEW_LINE INDENT return s + ( e - s ) // 2 NEW_LINE DEDENT def getSumUtil ( st , ss , se , qs , qe , si ) : NEW_LINE INDENT if qs <= ss and qe >= se : NEW_LINE INDENT return st [ si ] NEW_LINE DEDENT if se < qs or ss > qe : NEW_LINE INDENT return 0 NEW_LINE DEDENT mid = getMid ( ss , se ) NEW_LINE return ( getSumUtil ( st , ss , mid , qs , qe , 2 * si + 1 ) + getSumUtil ( st , mid + 1 , se , qs , qe , 2 * si + 2 ) ) NEW_LINE DEDENT def updateValueUtil ( st , ss , se , i , diff , si ) : NEW_LINE INDENT if i < ss or i > se : NEW_LINE INDENT return NEW_LINE DEDENT st [ si ] = st [ si ] + diff NEW_LINE if se != ss : NEW_LINE INDENT mid = getMid ( ss , se ) NEW_LINE updateValueUtil ( st , ss , mid , i , diff , 2 * si + 1 ) NEW_LINE updateValueUtil ( st , mid + 1 , se , i , diff , 2 * si + 2 ) NEW_LINE DEDENT DEDENT def updateValue ( arr , st , n , i , new_val ) : NEW_LINE INDENT if i < 0 or i > n - 1 : NEW_LINE INDENT print ( - 1 ) NEW_LINE return NEW_LINE DEDENT diff = new_val - arr [ i ] NEW_LINE prev_val = arr [ i ] NEW_LINE arr [ i ] = new_val NEW_LINE if prime [ new_val ] or prime [ prev_val ] : NEW_LINE INDENT if not prime [ prev_val ] : NEW_LINE INDENT updateValueUtil ( st , 0 , n - 1 , i , new_val , 0 ) NEW_LINE DEDENT elif not prime [ new_val ] : NEW_LINE INDENT updateValueUtil ( st , 0 , n - 1 , i , - prev_val , 0 ) NEW_LINE DEDENT else : NEW_LINE INDENT updateValueUtil ( st , 0 , n - 1 , i , diff , 0 ) NEW_LINE DEDENT DEDENT DEDENT def getSum ( st , n , qs , qe ) : NEW_LINE INDENT if qs < 0 or qe > n - 1 or qs > qe : NEW_LINE INDENT return - 1 NEW_LINE DEDENT return getSumUtil ( st , 0 , n - 1 , qs , qe , 0 ) NEW_LINE DEDENT def constructSTUtil ( arr , ss , se , st , si ) : NEW_LINE INDENT if ss == se : NEW_LINE INDENT if prime [ arr [ ss ] ] : NEW_LINE INDENT st [ si ] = arr [ ss ] NEW_LINE DEDENT else : NEW_LINE INDENT st [ si ] = 0 NEW_LINE DEDENT return st [ si ] NEW_LINE DEDENT mid = getMid ( ss , se ) NEW_LINE st [ si ] = ( constructSTUtil ( arr , ss , mid , st , 2 * si + 1 ) + constructSTUtil ( arr , mid + 1 , se , st , 2 * si + 2 ) ) NEW_LINE return st [ si ] NEW_LINE DEDENT def constructST ( arr , n ) : NEW_LINE INDENT x = int ( math . ceil ( math . log2 ( n ) ) ) NEW_LINE max_size = 2 * int ( pow ( 2 , x ) ) - 1 NEW_LINE st = [ 0 ] * max_size NEW_LINE constructSTUtil ( arr , 0 , n - 1 , st , 0 ) NEW_LINE return st NEW_LINE DEDENT arr = [ 1 , 3 , 5 , 7 , 9 , 11 ] NEW_LINE n = len ( arr ) NEW_LINE Q = [ [ 1 , 1 , 3 ] , [ 2 , 1 , 10 ] , [ 1 , 1 , 3 ] ] NEW_LINE SieveOfEratosthenes ( ) NEW_LINE st = constructST ( arr , n ) NEW_LINE print ( getSum ( st , n , 1 , 3 ) ) NEW_LINE updateValue ( arr , st , n , 1 , 10 ) NEW_LINE print ( getSum ( st , n , 1 , 3 ) ) NEW_LINE