Queries to calculate sum of array elements consisting of odd number of divisors | Function to find the sum of elements having odd number of divisors in index range [ L , R ] for Q queries ; Initialize the dp [ ] array ; Traverse the array , arr [ ] ; If a [ i ] is a perfect square , then update value of DP [ i ] to a [ i ] ; Find the prefix sum of DP [ ] array ; Iterate through all the queries ; Find the sum for each query ; Driver Code
function OddDivisorsSum ( n , q , a , Query ) { let DP = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) { DP [ i ] = 0 ; } for ( let i = 0 ; i < n ; i ++ ) { let x = Math . floor ( Math . sqrt ( a [ i ] ) ) ; if ( x * x == a [ i ] ) DP [ i ] = a [ i ] ; } for ( let i = 1 ; i < n ; i ++ ) { DP [ i ] = DP [ i - 1 ] + DP [ i ] ; } for ( let i = 0 ; i < q ; i ++ ) { let l = Query [ i ] [ 0 ] ; let r = Query [ i ] [ 1 ] ; if ( l == 0 ) { document . write ( DP [ r ] + " " ) ; } else { document . write ( DP [ r ] - DP [ l - 1 ] + " " ) ; } } } let arr = [ 2 , 4 , 5 , 6 , 9 ] ; let N = arr . length ; let Q = 3 let Query = [ [ 0 , 2 ] , [ 1 , 3 ] , [ 1 , 4 ] ] ; OddDivisorsSum ( N , Q , arr , Query ) ;