Sum of all Perfect Squares lying in the range [ L , R ] for Q queries | C ++ program to find the sum of all perfect squares in the given range ; Array to precompute the sum of squares from 1 to 100010 so that for every query , the answer can be returned in O ( 1 ) . ; Function to check if a number is a perfect square or not ; Find floating point value of square root of x . ; If square root is an integer ; Function to precompute the perfect squares upto 100000. ; Function to print the sum for each query ; Driver code ; To calculate the precompute function ; Calling the printSum function for every query
#include <bits/stdc++.h> NEW_LINE #define ll  int NEW_LINE using namespace std ; long long pref [ 100010 ] ; int isPerfectSquare ( long long int x ) { long double sr = sqrt ( x ) ; return ( ( sr - floor ( sr ) ) == 0 ) ? x : 0 ; } void compute ( ) { for ( int i = 1 ; i <= 100000 ; ++ i ) { pref [ i ] = pref [ i - 1 ] + isPerfectSquare ( i ) ; } } void printSum ( int L , int R ) { int sum = pref [ R ] - pref [ L - 1 ] ; cout << sum << " ▁ " ; } int main ( ) { compute ( ) ; int Q = 4 ; int arr [ ] [ 2 ] = { { 1 , 10 } , { 1 , 100 } , { 2 , 25 } , { 4 , 50 } } ; for ( int i = 0 ; i < Q ; i ++ ) { printSum ( arr [ i ] [ 0 ] , arr [ i ] [ 1 ] ) ; } return 0 ; }