Dada una array arr[] que consta de N enteros positivos y una array Query[][2] que consta de Q consultas de la forma {L, R} , la tarea es encontrar la suma de todos los elementos de la array del rango [L, R] , que tiene un número impar de divisores .
Ejemplos:
Entrada: arr[] = {2, 4, 5, 6, 9}, Q = 3, Query[][] = {{0, 2}, {1, 3}, {1, 4}}
Salida: 4 4 13
Explicación:
Consulta 1: Los elementos de los índices [0, 2] son {2, 4, 5}. De ellos, solo 4 tiene un número impar de divisores. Por lo tanto, la suma es 4.
Consulta 2: Los elementos de los índices [1, 3] son {4, 5, 6}. De ellos, solo 4 tiene un número impar de divisores. Por tanto, la suma es 4.
Consulta 3: Los elementos de los índices [1, 4] son {4, 5, 6, 9}. De ellos, solo 4, 9 tiene un número impar de divisores. Por lo tanto, la suma es 13.Entrada: arr[] = {1, 16, 5, 4, 9}, Q = 2, Query[][] = {{1, 3}, {0, 2}}
Salida: 20 17
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es atravesar la array dada arr[] sobre el rango [L, R] para cada consulta y encontrar la suma de los elementos en el rango [L, R] que tienen números impares de divisores e imprime la suma resultante.
Complejidad de Tiempo: O(Q * N *√N)
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar, lo que se basa en la siguiente observación:
- El número de divisores es impar solo si el número es un cuadrado perfecto .
- Entonces, el problema se puede resolver reemplazando los números enteros que no tienen un número impar de divisores con 0. Luego, construye un árbol de segmentos que encuentre la suma de los elementos en el rango para responder a las consultas.
Siga los pasos a continuación para resolver el problema:
- Recorra la array dada arr[] y reemplace los enteros que no son cuadrados perfectos con 0 .
- Cree un árbol de segmentos para responder a las consultas de suma entre el rango.
- Repita todas las consultas Q y, para cada consulta, obtenga la suma del rango particular del árbol de segmentos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get the middle index
// from the given ranges
int getMid(int s, int e)
{
return s + (e - s) / 2;
}
// Recursive function to find the sum
// of values in the given range of
// the array
int getSumUtil(int* st, int ss, int se,
int qs, int qe, int si)
{
// If segment of this node is a
// part of given range, then
// return the sum of the segment
if (qs <= ss && qe >= se)
return st[si];
// If segment of this node is
// outside the given range
if (se < qs || ss > qe)
return 0;
// If a part of this segment
// overlaps the given range
int mid = getMid(ss, se);
return getSumUtil(st, ss, mid,
qs, qe, 2 * si + 1)
+ getSumUtil(st, mid + 1,
se, qs, qe,
2 * si + 2);
}
// Function to find the sum of elements
// in the range from index qs (query
// start) to qe (query end)
int getSum(int* st, int n, int qs, int qe)
{
// Invalid ranges
if (qs < 0 || qe > n - 1 || qs > qe) {
cout << "Invalid Input";
return -1;
}
return getSumUtil(st, 0, n - 1, qs, qe, 0);
}
// Recursive function to construct the
// Segment Tree for array[ss..se]. si
// is index of current node in tree st
int constructSTUtil(int arr[], int ss,
int se, int* st,
int si)
{
// If there is one element
// in the array
if (ss == se) {
st[si] = arr[ss];
return arr[ss];
}
int mid = getMid(ss, se);
// Recur for left and right
// subtrees and store the sum
// of values in this node
st[si] = constructSTUtil(arr, ss, mid,
st, si * 2 + 1)
+ constructSTUtil(arr, mid + 1,
se, st,
si * 2 + 2);
return st[si];
}
// Function to construct segment tree
// from the given array
int* constructST(int arr[], int n)
{
// Allocate memory for the segment
// tree Height of segment tree
int x = (int)(ceil(log2(n)));
// Maximum size of segment tree
int max_size = 2 * (int)pow(2, x) - 1;
// Allocate memory
int* st = new int[max_size];
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0);
// Return the constructed
// segment tree
return st;
}
// Function to find the sum of elements
// having odd number of divisors in
// index range [L, R] for Q queries
void OddDivisorsSum(int n, int q, int arr[],
vector<pair<int, int> > Query)
{
// Traverse the array, arr[]
for (int i = 0; i < n; i++) {
int sq = sqrt(arr[i]);
// Replace elements that are
// not perfect squares with 0
if (sq * sq != arr[i])
arr[i] = 0;
}
// Build segment tree from the
// given array
int* st = constructST(arr, n);
// Iterate through all the queries
for (int i = 0; i < q; i++) {
int l = Query[i].first;
int r = Query[i].second;
// Print sum of values in
// array from index l to r
cout << getSum(st, n, l, r) << " ";
}
}
// Driver Code
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;
}
Java
// java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
public class GFG {
// Function to get the middle index
// from the given ranges
static int getMid(int s, int e)
{
return s + (e - s) / 2;
}
// Recursive function to find the sum
// of values in the given range of
// the array
static int getSumUtil(int st[], int ss, int se, int qs,
int qe, int si)
{
// If segment of this node is a
// part of given range, then
// return the sum of the segment
if (qs <= ss && qe >= se)
return st[si];
// If segment of this node is
// outside the given range
if (se < qs || ss > qe)
return 0;
// If a part of this segment
// overlaps the given range
int mid = getMid(ss, se);
return getSumUtil(st, ss, mid, qs, qe, 2 * si + 1)
+ getSumUtil(st, mid + 1, se, qs, qe,
2 * si + 2);
}
// Function to find the sum of elements
// in the range from index qs (query
// start) to qe (query end)
static int getSum(int st[], int n, int qs, int qe)
{
// Invalid ranges
if (qs < 0 || qe > n - 1 || qs > qe) {
System.out.println("Invalid Input");
return -1;
}
return getSumUtil(st, 0, n - 1, qs, qe, 0);
}
// Recursive function to construct the
// Segment Tree for array[ss..se]. si
// is index of current node in tree st
static int constructSTUtil(int arr[], int ss, int se,
int st[], int si)
{
// If there is one element
// in the array
if (ss == se) {
st[si] = arr[ss];
return arr[ss];
}
int mid = getMid(ss, se);
// Recur for left and right
// subtrees and store the sum
// of values in this node
st[si]
= constructSTUtil(arr, ss, mid, st, si * 2 + 1)
+ constructSTUtil(arr, mid + 1, se, st,
si * 2 + 2);
return st[si];
}
// Function to construct segment tree
// from the given array
static int[] constructST(int arr[], int n)
{
// Allocate memory for the segment
// tree Height of segment tree
int x = (int)(Math.ceil(Math.log(n) / Math.log(2)));
// Maximum size of segment tree
int max_size = 2 * (int)Math.pow(2, x) - 1;
// Allocate memory
int st[] = new int[max_size];
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0);
// Return the constructed
// segment tree
return st;
}
// Function to find the sum of elements
// having odd number of divisors in
// index range [L, R] for Q queries
static void OddDivisorsSum(int n, int q, int arr[],
int Query[][])
{
// Traverse the array, arr[]
for (int i = 0; i < n; i++) {
int sq = (int)Math.sqrt(arr[i]);
// Replace elements that are
// not perfect squares with 0
if (sq * sq != arr[i])
arr[i] = 0;
}
// Build segment tree from the
// given array
int st[] = constructST(arr, n);
// Iterate through all the queries
for (int i = 0; i < q; i++) {
int l = Query[i][0];
int r = Query[i][1];
// Print sum of values in
// array from index l to r
System.out.print(getSum(st, n, l, r) + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 4, 5, 6, 9 };
int N = arr.length;
int Q = 3;
int Query[][] = { { 0, 2 }, { 1, 3 }, { 1, 4 } };
OddDivisorsSum(N, Q, arr, Query);
}
}
// This code is contributed by Kingash.
Javascript
<script>
// JavaScript program for the above approach
// Function to get the middle index
// from the given ranges
function getMid(s,e)
{
return s + Math.floor((e - s) / 2);
}
// Recursive function to find the sum
// of values in the given range of
// the array
function getSumUtil(st,ss,se,qs,qe,si)
{
// If segment of this node is a
// part of given range, then
// return the sum of the segment
if (qs <= ss && qe >= se)
return st[si];
// If segment of this node is
// outside the given range
if (se < qs || ss > qe)
return 0;
// If a part of this segment
// overlaps the given range
let mid = getMid(ss, se);
return getSumUtil(st, ss, mid, qs, qe, 2 * si + 1)
+ getSumUtil(st, mid + 1, se, qs, qe,
2 * si + 2);
}
// Function to find the sum of elements
// in the range from index qs (query
// start) to qe (query end)
function getSum( st, n, qs, qe)
{
// Invalid ranges
if (qs < 0 || qe > n - 1 || qs > qe) {
document.write("Invalid Input");
return -1;
}
return getSumUtil(st, 0, n - 1, qs, qe, 0);
}
// Recursive function to construct the
// Segment Tree for array[ss..se]. si
// is index of current node in tree st
function constructSTUtil(arr,ss,se,st,si)
{
// If there is one element
// in the array
if (ss == se) {
st[si] = arr[ss];
return arr[ss];
}
let mid = getMid(ss, se);
// Recur for left and right
// subtrees and store the sum
// of values in this node
st[si]
= constructSTUtil(arr, ss, mid, st, si * 2 + 1)
+ constructSTUtil(arr, mid + 1, se, st,
si * 2 + 2);
return st[si];
}
// Function to construct segment tree
// from the given array
function constructST(arr,n)
{
// Allocate memory for the segment
// tree Height of segment tree
let x = (Math.ceil(Math.log(n) / Math.log(2)));
// Maximum size of segment tree
let max_size = 2 * Math.pow(2, x) - 1;
// Allocate memory
let st = new Array(max_size);
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0);
// Return the constructed
// segment tree
return st;
}
// Function to find the sum of elements
// having odd number of divisors in
// index range [L, R] for Q queries
function OddDivisorsSum(n,q,arr,Query)
{
// Traverse the array, arr[]
for (let i = 0; i < n; i++) {
let sq = Math.sqrt(arr[i]);
// Replace elements that are
// not perfect squares with 0
if (sq * sq != arr[i])
arr[i] = 0;
}
// Build segment tree from the
// given array
let st = constructST(arr, n);
// Iterate through all the queries
for (let i = 0; i < q; i++) {
let l = Query[i][0];
let r = Query[i][1];
// Print sum of values in
// array from index l to r
document.write(getSum(st, n, l, r) + " ");
}
}
// Driver Code
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);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
4 4 13
Complejidad de tiempo: O(Q * log(N))
Espacio auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar una array auxiliar que almacene la suma de prefijos de elementos que tienen un número impar de divisores. Siga los pasos a continuación para resolver el problema:
- Inicialice una array dp[] de tamaño N con 0 .
- Recorra la array dada arr[] usando la variable i y verifique si algún elemento es un cuadrado perfecto . Si se determina que es cierto, actualice el valor de dp[i] como arr[i] .
- Encuentre la suma del prefijo de la array dp[] .
- Repita todas las consultas y para cada consulta en el rango [L, R], la respuesta estará dada por (dp[R] – dp[L – 1]) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the sum of elements
// having odd number of divisors in
// index range [L, R] for Q queries
void OddDivisorsSum(int n, int q, int a[],
vector<pair<int, int> > Query)
{
// Initialize the dp[] array
int DP[n] = { 0 };
// Traverse the array, arr[]
for (int i = 0; i < n; i++) {
int x = sqrt(a[i]);
// If a[i] is a perfect square,
// then update value of DP[i] to a[i]
if (x * x == a[i])
DP[i] = a[i];
}
// Find the prefix sum of DP[] array
for (int i = 1; i < n; i++) {
DP[i] = DP[i - 1] + DP[i];
}
// Iterate through all the queries
for (int i = 0; i < q; i++) {
int l = Query[i].first;
int r = Query[i].second;
// Find the sum for each query
if (l == 0) {
cout << DP[r] << " ";
}
else {
cout << DP[r] - DP[l - 1]
<< " ";
}
}
}
// Driver Code
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;
}
Python3
# Python3 program for the above approach from math import sqrt # Function to find the sum of elements # having odd number of divisors in # index range [L, R] for Q queries def OddDivisorsSum(n, q, a, Query): # Initialize the dp[] array DP = [0]*n # Traverse the array, arr[] for i in range(n): x = sqrt(a[i]) # If a[i] is a perfect square, # then update value of DP[i] to a[i] if (x * x == a[i]): DP[i] = a[i] # Find the prefix sum of DP[] array for i in range(1, n): DP[i] = DP[i - 1] + DP[i] # Iterate through all the queries for i in range(q): l = Query[i][0] r = Query[i][1] # Find the sum for each query if (l == 0): print(DP[r], end=" ") else: print(DP[r] - DP[l - 1], end=" ") # Driver Code if __name__ == '__main__': arr = [2, 4, 5, 6, 9] N = len(arr) Q = 3 Query = [ [ 0, 2 ], [ 1, 3 ], [ 1, 4 ] ] OddDivisorsSum(N, Q, arr, Query) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the sum of elements
// having odd number of divisors in
// index range [L, R] for Q queries
static void OddDivisorsSum(int n, int q, int[] a,
int[, ] Query)
{
// Initialize the dp[] array
int[] DP = new int[n];
// Traverse the array, arr[]
for (int i = 0; i < n; i++) {
int x = (int)(Math.Sqrt(a[i]));
// If a[i] is a perfect square,
// then update value of DP[i] to a[i]
if (x * x == a[i])
DP[i] = a[i];
}
// Find the prefix sum of DP[] array
for (int i = 1; i < n; i++) {
DP[i] = DP[i - 1] + DP[i];
}
// Iterate through all the queries
for (int i = 0; i < q; i++) {
int l = Query[i, 0];
int r = Query[i, 1];
// Find the sum for each query
if (l == 0) {
Console.Write(DP[r] + " ");
}
else {
Console.Write(DP[r] - DP[l - 1] + " ");
}
}
}
// Driver Code
public static void Main()
{
int[] arr = { 2, 4, 5, 6, 9 };
int N = arr.Length;
int Q = 3;
int[, ] Query = { { 0, 2 }, { 1, 3 }, { 1, 4 } };
OddDivisorsSum(N, Q, arr, Query);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript 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
function OddDivisorsSum(n, q, a, Query)
{
// Initialize the dp[] array
let DP = new Array(n);
for(let i = 0; i < n; i++)
{
DP[i] = 0;
}
// Traverse the array, arr[]
for(let i = 0; i < n; i++)
{
let x = Math.floor(Math.sqrt(a[i]));
// If a[i] is a perfect square,
// then update value of DP[i] to a[i]
if (x * x == a[i])
DP[i] = a[i];
}
// Find the prefix sum of DP[] array
for(let i = 1; i < n; i++)
{
DP[i] = DP[i - 1] + DP[i];
}
// Iterate through all the queries
for(let i = 0; i < q; i++)
{
let l = Query[i][0];
let r = Query[i][1];
// Find the sum for each query
if (l == 0)
{
document.write(DP[r] + " ");
}
else
{
document.write(DP[r] - DP[l - 1] + " ");
}
}
}
// Driver Code
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);
// This code is contributed by patel2127
</script>
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
// Function to find the sum of elements
// having odd number of divisors in
// index range [L, R] for Q queries
static void OddDivisorsSum(int n, int q, int[] a,
int[][] Query)
{
// Initialize the dp[] array
int[] DP = new int[n];
// Traverse the array, arr[]
for (int i = 0; i < n; i++) {
int x = (int)(Math.sqrt(a[i]));
// If a[i] is a perfect square,
// then update value of DP[i] to a[i]
if (x * x == a[i])
DP[i] = a[i];
}
// Find the prefix sum of DP[] array
for (int i = 1; i < n; i++) {
DP[i] = DP[i - 1] + DP[i];
}
// Iterate through all the queries
for (int i = 0; i < q; i++) {
int l = Query[i][0];
int r = Query[i][1];
// Find the sum for each query
if (l == 0) {
System.out.print(DP[r] + " ");
}
else {
System.out.print(DP[r] - DP[l - 1] + " ");
}
}
}
// Driver Code
public static void main (String[] args) {
int[] arr = { 2, 4, 5, 6, 9 };
int N = arr.length;
int Q = 3;
int[][] Query = { { 0, 2 }, { 1, 3 }, { 1, 4 } };
OddDivisorsSum(N, Q, arr, Query);
}
}
Producción:
4 4 13
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sudhanshugupta2019a y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA