Suma de todos los cubos perfectos que se encuentran en el rango [L, R] para consultas Q

Dadas las consultas Q en forma de array 2D arr[][] cuyas filas consisten en dos números L y R que significan el rango [L, R], la tarea es encontrar la suma de todos los cubos perfectos que se encuentran en este rango.
Ejemplos: 
 

Entrada: Q = 2, arr[][] = {{4, 9}, {4, 44}} 
Salida: 8 35 
Del 4 al 9: solo 8 es el cubo perfecto. Por lo tanto, 8 es el ans 
De 4 a 44: 8, y 27 son los cubos perfectos. Por lo tanto, 8 + 27 = 35
Entrada: Q = 4, arr[][] = {{ 1, 10 }, { 1, 100 }, { 2, 25 }, { 4, 50 }} 
Salida: 9 100 8 35 
 

Enfoque: la idea es usar una array de suma de prefijos . 
 

1. La suma de todos los cubos se calcula previamente y se almacena en una array pref[] para que cada consulta se pueda responder en tiempo O(1).
2. Cada i ^-ésimo índice en la array pref[] representa la suma de cubos perfectos desde 1 hasta ese número.
3. Por lo tanto, la suma de cubos perfectos del rango dado ‘L’ a ‘R’ se puede encontrar a partir del prefijo sum array pref[].

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to find the sum of all
// perfect cubes in the given range
 
#include <bits/stdc++.h>
#define ll int
using namespace std;
 
// Array to precompute the sum of cubes
// from 1 to 100010 so that for every
// query, the answer can be returned in O(1).
long long pref[100010];
 
// Function to check if a number is
// a perfect Cube or not
int isPerfectCube(long long int x)
{
    // Find floating point value of
    // cube root of x.
    long double cr = round(cbrt(x));
 
    // If cube root of x is cr
    // return the x, else 0
    return (cr * cr * cr == x) ? x : 0;
}
 
// Function to precompute the perfect
// Cubes upto 100000.
void compute()
{
    for (int i = 1; i <= 100000; ++i) {
        pref[i] = pref[i - 1]
                  + isPerfectCube(i);
    }
}
 
// Function to print the sum for each query
void printSum(int L, int R)
{
    int sum = pref[R] - pref[L - 1];
    cout << sum << " ";
}
 
// Driver code
int main()
{
    // To calculate the precompute function
    compute();
 
    int Q = 4;
    int arr[][2] = { { 1, 10 },
                     { 1, 100 },
                     { 2, 25 },
                     { 4, 50 } };
 
    // Calling the printSum function
    // for every query
    for (int i = 0; i < Q; i++) {
        printSum(arr[i][0], arr[i][1]);
    }
 
    return 0;
}

// Java program to find the sum of all
// perfect cubes in the given range
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class GFG
{
    // Array to precompute the sum of cubes
    // from 1 to 100010 so that for every
    // query, the answer can be returned in O(1).
     public static int []pref=new int[100010];
       
    // Function to check if a number is
    // a perfect Cube or not
    static int isPerfectCube(int x)
    {
        // Find floating point value of
        // cube root of x.
        double cr = Math.round(Math.cbrt(x));
       
        // If cube root of x is cr
        // return the x, else 0
        if(cr*cr*cr==(double)x) return x;
        return 0;
    }
       
    // Function to precompute the perfect
    // Cubes upto 100000.
    static void compute()
    {
        for (int i = 1; i <= 100000; ++i) {
            pref[i] = pref[i - 1]+ isPerfectCube(i);
        }
    }
       
    // Function to print the sum for each query
    static void printSum(int L, int R)
    {
        long sum = pref[R] - pref[L - 1];
        System.out.print(sum+" ");
    }
       
   
    
    // Driver code
    public static void main (String[] args)
    {
         // To calculate the precompute function
        compute();
       
        int Q = 4;
        int [][] arr = { { 1, 10 },
                                { 1, 100 },
                                { 2, 25 },
                                { 4, 50 } };
       
        // Calling the printSum function
        // for every query
        for (int i = 0; i < Q; i++) {
            printSum(arr[i][0], arr[i][1]);
        }
    }
}
 
// This code is contributed by chitranayal

# Python3 program to find the sum of all
# perfect cubes in the given range
 
# Array to precompute the sum of cubes
# from 1 to 100010 so that for every
# query, the answer can be returned in O(1).
pref = [0]*100010;
 
# Function to check if a number is
# a perfect Cube or not
def isPerfectCube(x) :
 
    # Find floating point value of
    # cube root of x.
    cr = round(x**(1/3));
 
    # If cube root of x is cr
    # return the x, else 0
    rslt = x if (cr * cr * cr == x) else 0;
    return rslt;
 
# Function to precompute the perfect
# Cubes upto 100000.
def compute() :
    for i in range(1, 100001) :
        pref[i] = pref[i - 1] + isPerfectCube(i);
 
# Function to print the sum for each query
def printSum(L, R) :
 
    sum = pref[R] - pref[L - 1];
    print(sum ,end= " ");
 
# Driver code
if __name__ == "__main__" :
 
    # To calculate the precompute function
    compute();
 
    Q = 4;
    arr= [ [ 1, 10 ],
            [ 1, 100 ],
            [ 2, 25 ],
            [ 4, 50 ] ];
 
    # Calling the printSum function
    # for every query
    for i in range(Q) :
        printSum(arr[i][0], arr[i][1]);
 
# This code is contributed by AnkitRai01

// C# program to find the sum of all
// perfect cubes in the given range
using System;
       
class GFG {
// Array to precompute the sum of cubes
// from 1 to 100010 so that for every
// query, the answer can be returned in O(1).
 public static long []pref=new long[100010];
  
// Function to check if a number is
// a perfect Cube or not
static long isPerfectCube(long x)
{
    // Find floating point value of
    // cube root of x.
    double cr = Math.Round(MathF.Cbrt(x));
  
    // If cube root of x is cr
    // return the x, else 0
    if(cr*cr*cr==(double)x) return x;
    return 0;
}
  
// Function to precompute the perfect
// Cubes upto 100000.
static void compute()
{
    for (long i = 1; i <= 100000; ++i) {
        pref[i] = pref[i - 1]
                  + isPerfectCube(i);
    }
}
  
// Function to print the sum for each query
static void printSum(int L, int R)
{
    long sum = pref[R] - pref[L - 1];
    Console.Write(sum+" ");
}
  
// Driver code
public static void Main()
  {
    // To calculate the precompute function
    compute();
  
    int Q = 4;
    int [,] arr = new int[,]{ { 1, 10 },
                            { 1, 100 },
                            { 2, 25 },
                            { 4, 50 } };
  
    // Calling the printSum function
    // for every query
    for (int i = 0; i < Q; i++) {
        printSum(arr[i,0], arr[i,1]);
    }
  }
} 
 
// This code is contributed by mohit kumar 29

<script>
 
// Javascript program to find the sum of all
// perfect cubes in the given range
 
// Array to precompute the sum of cubes
// from 1 to 100010 so that for every
// query, the answer can be returned in O(1).
var pref=Array(100010).fill(0);
 
// Function to check if a number is
// a perfect Cube or not
function isPerfectCube(x)
{
    // Find floating point value of
    // cube root of x.
    var cr = Math.round(Math.cbrt(x));
 
    // If cube root of x is cr
    // return the x, else 0
    return (cr * cr * cr == x) ? x : 0;
}
 
// Function to precompute the perfect
// Cubes upto 100000.
function compute()
{
    for (var i = 1; i <= 100000; ++i) {
        pref[i] = pref[i - 1]
                  + isPerfectCube(i);
    }
}
 
// Function to print the sum for each query
function printSum(L, R)
{
    var sum = pref[R] - pref[L - 1];
    document.write(sum + " ");
}
 
// Driver code
 
// To calculate the precompute function
compute();
var Q = 4;
var arr = [ [ 1, 10 ],
                 [ 1, 100 ],
                 [ 2, 25 ],
                 [ 4, 50 ] ];
// Calling the printSum function
// for every query
for (var i = 0; i < Q; i++) {
    printSum(arr[i][0], arr[i][1]);
}
 
</script>

9 100 8 35

Complejidad de tiempo: O (100000)

Espacio Auxiliar: O(100010)