Queries to calculate sum of array elements consisting of odd number of divisors | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void OddDivisorsSum ( int n , int q , int a [ ] , vector < pair < int , int > > Query ) { int DP [ n ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) { int x = sqrt ( a [ i ] ) ; if ( x * x == a [ i ] ) DP [ i ] = a [ i ] ; } for ( int i = 1 ; i < n ; i ++ ) { DP [ i ] = DP [ i - 1 ] + DP [ i ] ; } for ( int i = 0 ; i < q ; i ++ ) { int l = Query [ i ] . first ; int r = Query [ i ] . second ; if ( l == 0 ) { cout << DP [ r ] << " ▁ " ; } else { cout << DP [ r ] - DP [ l - 1 ] << " ▁ " ; } } } int main ( ) { int arr [ ] = { 2 , 4 , 5 , 6 , 9 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int Q = 3 ; vector < pair < int , int > > Query = { { 0 , 2 } , { 1 , 3 } , { 1 , 4 } } ; OddDivisorsSum ( N , Q , arr , Query ) ; return 0 ; }