Problem
Given an array A of size n and an array Query[][2] of size q consisting of queries of the form {L, R}, find the sum of array elements from the index range [L, R], having an odd number of divisors. Assume all the array elements are positive.
Input:
 An integer n.
 The next n lines contain the array elements.
 The next line contains an integer q that represents the size of the Query array.
 The next q lines contain two integers, L and R, representing the array's left and right indexes.
Output: For each query, print the answer in a new line.
The questions you can ask the interviewer:
 What are the constraints on n and q?
 What is the range of the elements of A?
Alert Ninjas: Don’t stop now! Enroll in the Competitive Programming course today. Learn the art of writing time and spaceefficient code and compete in code competitions worldwide.
Example:
Input: n = 9, A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}, q = 3, Query[][] = {{0, 3}, {1, 5}, {4, 8}} Output: 5 4 9 Explanation: Query 1: Array elements from [0, 3] are {1, 2, 3, 4}. Out of them, only 1,4 has an odd number of divisors. Therefore, the sum is 5. Query 2: Elements from indices [1, 5] are {2, 3, 4, 5, 6}. Only 4 have an odd number of divisors. Hence, the sum is 4. Query 3: Elements from the indices [4, 8] are {5, 6, 7, 8, 9}. Out of them, only 9 have an odd number of divisors. Therefore, the sum is 9. 
Recommended: Try to solve it yourself before moving on to the solution.
Solution
Naive Approach:
The most obvious solution that comes to our mind is that for each query, traverse the array A, over the range [L, R] and determine the sum of the array elements in the range [L, R] with odd numbers of divisors, then print the resultant sum.
The time complexity of the above approach is O( n * q * √n). As the time complexity to solve each query is O(q) *, the time complexity to traverse the index range [L, R] is O(n) *, the time complexity to find the divisors of each element in that range is O(√n).
Can we do better?
Segment Tree Approach:
Idea: The idea is to use Segment Trees.
Use the fact that the number of divisors of a positive integer is odd if only the integer is a perfect square. As a result, replace all the array elements that do not have the odd number of divisors with 0. Then, build a segment tree to answer each query.
Algorithm:
 Traverse array A and replace the elements that are not a perfect square with 0.
 Build a segment tree of the given array elements.
 Iterate over the array Queries, and for each query, calculate the sum of the [L, R] range from the segment tree.
 Print the answer in a separate line.
Time Complexity: O(q * log(n)); Time complexity of building the segment tree is O(logn) * time complexity of iterating over the array Queries.
Space Complexity: O(n); Space used to build the segment tree.
Let's try to reduce the time complexity further.
Better Approach:
Idea: The idea is to use Dynamic Programming such that dp[i] will be A[i] if A[i] is a perfect square, 0 otherwise. Find the prefix sum of the dp array to answer each query.
Algorithm:
 Initialize a dp array of size n with values 0.
 Iterate through array A using variable i and change dp[i] to A[i] if A[i] is a perfect square.
 Calculate the prefix sum of the dp array.
 Iterate over all the queries, and the answer for each query in the range [L, R] will be (dp[R] – dp[L – 1]).
C++
#include <bits/stdc++.h>

Input: n = 9, A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}, q = 3, Query[][] = {{0, 3}, {1, 5}, {4, 8}}.
Output:
Time Complexity: The time complexity is either O(n) or O(q), whichever is greater.
Space Complexity: O(n); Space used to create the DP array.
Also see, Euclid GCD Algorithm