Range Sum Queries and Update with Square Root | Python program to calculate sum in an interval and update with square root ; Maximum size of input array ; structure for queries with members type , leftIndex , rightIndex of the query ; function for updating the value ; function for calculating the required sum between two indexes ; function to return answer to queries ; Declaring a Set ; inserting indexes of those numbers which are greater than 1 ; update query ; find the left index of query in the set using binary search auto it = s . lower_bound ( que [ i ] . l ) ; ; if it crosses the right index of query or end of set , then break ; update the value of arr [ i ] to itss square root ; if updated value becomes equal to 1 remove it from the set ; increment the index ; sum query ; Driver Code ; input array using 1 - based indexing ; declaring array of structure of type queries ; answer the Queries
from typing import List NEW_LINE import bisect NEW_LINE from math import sqrt , floor NEW_LINE MAX = 100 NEW_LINE BIT = [ 0 for _ in range ( MAX + 1 ) ] NEW_LINE class queries : NEW_LINE INDENT def __init__ ( self , type : int = 0 , l : int = 0 , r : int = 0 ) -> None : NEW_LINE INDENT self . type = type NEW_LINE self . l = l NEW_LINE self . r = r NEW_LINE DEDENT DEDENT def update ( x : int , val : int , n : int ) -> None : NEW_LINE INDENT a = x NEW_LINE while a <= n : NEW_LINE INDENT BIT [ a ] += val NEW_LINE a += a & - a NEW_LINE DEDENT DEDENT def sum ( x : int ) -> int : NEW_LINE INDENT s = 0 NEW_LINE a = x NEW_LINE while a : NEW_LINE INDENT s += BIT [ a ] NEW_LINE a -= a & - a NEW_LINE DEDENT return s NEW_LINE DEDENT def answerQueries ( arr : List [ int ] , que : List [ queries ] , n : int , q : int ) -> None : NEW_LINE INDENT s = set ( ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT if ( arr [ i ] > 1 ) : NEW_LINE INDENT s . add ( i ) NEW_LINE DEDENT update ( i , arr [ i ] , n ) NEW_LINE DEDENT for i in range ( q ) : NEW_LINE INDENT if ( que [ i ] . type == 1 ) : NEW_LINE INDENT while True : NEW_LINE INDENT ss = list ( sorted ( s ) ) NEW_LINE it = bisect . bisect_left ( ss , que [ i ] . l ) NEW_LINE if it == len ( s ) or ss [ it ] > que [ i ] . r : NEW_LINE INDENT break NEW_LINE DEDENT que [ i ] . l = ss [ it ] NEW_LINE update ( ss [ it ] , floor ( sqrt ( arr [ ss [ it ] ] ) - arr [ ss [ it ] ] ) , n ) NEW_LINE arr [ ss [ it ] ] = floor ( sqrt ( arr [ ss [ it ] ] ) ) NEW_LINE if ( arr [ ss [ it ] ] == 1 ) : NEW_LINE INDENT s . remove ( ss [ it ] ) NEW_LINE DEDENT que [ i ] . l += 1 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT print ( sum ( que [ i ] . r ) - sum ( que [ i ] . l - 1 ) ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT q = 4 NEW_LINE arr = [ 0 , 4 , 5 , 1 , 2 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE que = [ queries ( ) for _ in range ( q + 1 ) ] NEW_LINE que [ 0 ] . type , que [ 0 ] . l , que [ 0 ] . r = 2 , 1 , 5 NEW_LINE que [ 1 ] . type , que [ 1 ] . l , que [ 1 ] . r = 1 , 1 , 2 NEW_LINE que [ 2 ] . type , que [ 2 ] . l , que [ 2 ] . r = 1 , 2 , 4 NEW_LINE que [ 3 ] . type , que [ 3 ] . l , que [ 3 ] . r = 2 , 1 , 5 NEW_LINE answerQueries ( arr , que , n , q ) NEW_LINE DEDENT