Consultas de suma de rango y actualización con raíz cuadrada

Dada una array A de N enteros y un número de consultas Q. Tienes que responder a dos tipos de consultas. 
 

• Actualizar [l, r] : para cada i en el rango de l a r , actualice A _i con sqrt(A _i ) , donde sqrt(A _i ) representa la raíz cuadrada de A _i en forma integral.
• Consulta [l, r] : calcule la suma de todos los números que oscilan entre l y r en la array A.

Requisito previo: árboles indexados binarios | Ejemplos de árboles de segmentos :
 
 

Entrada: A[] = { 4, 5, 1, 2, 4 }, Q = {{2, 1, 5}, {1, 1, 2}, {1, 2, 4}, {2, 1, 5}} 
Salida: 16 
9 
Teniendo en cuenta la indexación basada en 1, la primera consulta es calcular la suma de los números de A ₁ a A ₅ 
, que es 4 + 5 + 1 + 2 + 4 = 16. La 
segunda consulta es actualizar A ₁ a A ₂ con su raíz cuadrada. Ahora, la array se convierte en A[] = { 2, 2, 1, 2, 4 }. 
De manera similar, la tercera consulta es actualizar A ₂ a A ₄ con su raíz cuadrada. Ahora, la array se convierte en A[] = { 2, 1, 1, 1, 4 }. 
La cuarta consulta es calcular la suma de los números de A ₁ a A ₅ , que es 2 + 1 + 1 + 1 + 4 = 9.
Entrada:A[] = { 4, 9, 25, 36 }, Q = {{1, 2, 4}, {2, 1, 4}} 
Salida: 18 
 

Enfoque ingenuo: una solución simple es ejecutar un ciclo de l a r y calcular la suma de los elementos en el rango dado. Para actualizar un valor, simplemente reemplace arr[i] con su raíz cuadrada, es decir, arr[i] = sqrt[arr[i]] .
Enfoque eficiente: la idea es reducir la complejidad del tiempo para cada operación de consulta y actualización a O(logN) . Utilice árboles indexados binarios (BIT) o árboles de segmentos . Construya una array BIT[] y tenga dos funciones para la operación de consulta y actualización. Ahora, para cada operación de actualización, la observación clave es que el número 1 tendrá 1como su raíz cuadrada, por lo que si existe en el rango de consulta de actualización, no necesita actualizarse. Usaremos un conjunto para almacenar el índice de solo aquellos números que son mayores que 1 y usaremos la búsqueda binaria para encontrar el índice l de la consulta de actualización e incrementar el índice l hasta que cada elemento se actualice en el rango de esa consulta de actualización. Si el arr[i] tiene 1 como su raíz cuadrada, luego de actualizarlo, elimínelo del conjunto, ya que siempre será 1 incluso después de cualquier consulta de actualización siguiente. Para la operación de consulta de suma, simplemente haga query(r) – query(l – 1) .
A continuación se muestra la implementación del enfoque anterior:
 

// CPP program to calculate sum
// in an interval and update with
// square root
#include <bits/stdc++.h>
using namespace std;
 
// Maximum size of input array
const int MAX = 100;
 
int BIT[MAX + 1];
 
// structure for queries with members type,
// leftIndex, rightIndex of the query
struct queries {
    int type, l, r;
};
 
// function for updating the value
void update(int x, int val, int n)
{
    for (x; x <= n; x += x & -x) {
        BIT[x] += val;
    }
}
 
// function for calculating the required
// sum between two indexes
int sum(int x)
{
    int s = 0;
    for (x; x > 0; x -= x & -x) {
        s += BIT[x];
    }
    return s;
}
 
// function to return answer to queries
void answerQueries(int arr[], queries que[], int n, int q)
{
    // Declaring a Set
    set<int> s;
    for (int i = 1; i < n; i++) {
 
        // inserting indexes of those numbers
        // which are greater than 1
        if (arr[i] > 1)
            s.insert(i);
        update(i, arr[i], n);
    }
 
    for (int i = 0; i < q; i++) {
 
        // update query
        if (que[i].type == 1) {
            while (true) {
 
                // find the left index of query in
                // the set using binary search
                auto it = s.lower_bound(que[i].l);
 
                // if it crosses the right index of
                // query or end of set, then break
                if (it == s.end() || *it > que[i].r)
                    break;
 
                que[i].l = *it;
 
                // update the value of arr[i] to
                // its square root
                update(*it, (int)sqrt(arr[*it]) - arr[*it], n);
 
                arr[*it] = (int)sqrt(arr[*it]);
 
                // if updated value becomes equal to 1
                // remove it from the set
                if (arr[*it] == 1)
                    s.erase(*it);
 
                // increment the index
                que[i].l++;
            }
        }
 
        // sum query
        else {
            cout << (sum(que[i].r) - sum(que[i].l - 1)) << endl;
        }
    }
}
 
// Driver Code
int main()
{
    int q = 4;
 
    // input array using 1-based indexing
    int arr[] = { 0, 4, 5, 1, 2, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // declaring array of structure of type queries
    queries que[q + 1];
 
    que[0].type = 2, que[0].l = 1, que[0].r = 5;
    que[1].type = 1, que[1].l = 1, que[1].r = 2;
    que[2].type = 1, que[2].l = 2, que[2].r = 4;
    que[3].type = 2, que[3].l = 1, que[3].r = 5;
 
    // answer the Queries
    answerQueries(arr, que, n, q);
 
    return 0;
}

# Python program to calculate sum
# in an interval and update with
# square root
from typing import List
import bisect
from math import sqrt, floor
 
# Maximum size of input array
MAX = 100
BIT = [0 for _ in range(MAX + 1)]
 
# structure for queries with members type,
# leftIndex, rightIndex of the query
class queries:
    def __init__(self, type: int = 0, l: int = 0, r: int = 0) -> None:
        self.type = type
        self.l = l
        self.r = r
 
# function for updating the value
def update(x: int, val: int, n: int) -> None:
    a = x
    while a <= n:
        BIT[a] += val
        a += a & -a
 
# function for calculating the required
# sum between two indexes
def sum(x: int) -> int:
    s = 0
    a = x
    while a:
        s += BIT[a]
        a -= a & -a
 
    return s
 
# function to return answer to queries
def answerQueries(arr: List[int], que: List[queries], n: int, q: int) -> None:
 
    # Declaring a Set
    s = set()
    for i in range(1, n):
 
        # inserting indexes of those numbers
        # which are greater than 1
        if (arr[i] > 1):
            s.add(i)
        update(i, arr[i], n)
 
    for i in range(q):
 
        # update query
        if (que[i].type == 1):
            while True:
                ss = list(sorted(s))
                 
                # find the left index of query in
                # the set using binary search
                # auto it = s.lower_bound(que[i].l);
                it = bisect.bisect_left(ss, que[i].l)
 
                # if it crosses the right index of
                # query or end of set, then break
                if it == len(s) or ss[it] > que[i].r:
                    break
                que[i].l = ss[it]
 
                # update the value of arr[i] to
                # itss square root
                update(ss[it], floor(sqrt(arr[ss[it]]) - arr[ss[it]]), n)
 
                arr[ss[it]] = floor(sqrt(arr[ss[it]]))
 
                # if updated value becomes equal to 1
                # remove it from the set
                if (arr[ss[it]] == 1):
                    s.remove(ss[it])
 
                # increment the index
                que[i].l += 1
 
        # sum query
        else:
            print(sum(que[i].r) - sum(que[i].l - 1))
 
 
# Driver Code
if __name__ == "__main__":
 
    q = 4
 
    # input array using 1-based indexing
    arr = [0, 4, 5, 1, 2, 4]
    n = len(arr)
    # declaring array of structure of type queries
    que = [queries() for _ in range(q + 1)]
 
    que[0].type, que[0].l, que[0].r = 2, 1, 5
    que[1].type, que[1].l, que[1].r = 1, 1, 2
    que[2].type, que[2].l, que[2].r = 1, 2, 4
    que[3].type, que[3].l, que[3].r = 2, 1, 5
 
    # answer the Queries
    answerQueries(arr, que, n, q)
 
# This code is contributed by sanjeev2552

// JavaScript program to calculate sum
// in an interval and update with
// square root
 
// Maximum size of input array
let MAX = 100;
let BIT = new Array(MAX + 1).fill(0);
 
function lower_bound(arr, ele)
{
    for (var i = 0; i < arr.length; i++)
    {
        if (arr[i] >= ele)
            return i;
    }
    return arr.length - 1;
}
 
// structure for queries with members type,
// leftIndex, rightIndex of the query
class queries
{
    constructor(type, l, r)
    {
        this.type = type;
        this.l = l;
        this.r = r;
    }
}
 
// function for updating the value
function update(BIT, x, val, n)
{
    var a = x;
    while (a <= n)
    {
        BIT[a] += val;
        a += (a & -a);
    }
    return BIT;
}
 
// function for calculating the required
// sum between two indexes
function sum(x)
{
    var s = 0;
    var a = x;
    while (a > 0)
    {
        s += BIT[a];
        a -= (a & -a);
    }
 
    return s;
}
 
// function to return answer to queries
function answerQueries(arr, que, n, q)
{
    // Declaring a Set
    let s = new Set();
     
    for (var i = 1; i < n; i++)
    {
        // inserting indexes of those numbers
        // which are greater than 1
        if (arr[i] > 1)
            s.add(i);
        BIT = update(BIT, i, arr[i], n);
    }
    for (var i = 0; i < q; i++)
    {
        // update query
        if (que[i].type == 1)
        {
            while (true)
            {
                var ss = Array.from(s);
                ss.sort();
                 
                // find the left index of query in
                // the set using binary search
                // auto it = s.lower_bound(que[i].l);
                let it = lower_bound(ss, que[i].l);
 
                // if it crosses the right index of
                // query or end of set, then break
                if (it == s.length || ss[it] > que[i].r)
                    break;
                que[i].l = ss[it];
 
                // update the value of arr[i] to
                // its square root
                BIT = update(BIT, ss[it], (Math.pow(arr[ss[it]], 0.5)) - arr[ss[it]], n);
 
                arr[ss[it]] = (Math.pow(arr[ss[it]], 0.5));
 
                // if updated value becomes equal to 1
                // remove it from the set
                if (arr[ss[it]] == 1)
                    arr.splice(ss[it], 1);
 
                // increment the index
                que[i].l += 1;
            }
        }
 
        // sum query
        else
            console.log(Math.floor(sum(que[i].r) - sum(que[i].l - 1)));
    }
}
 
 
// Driver Code
let q = 4;
 
// input array using 1-based indexing
let arr = [0, 4, 5, 1, 2, 4];
let n = arr.length;
// declaring array of structure of type queries
let que = [new queries(2, 1, 5), new queries(1, 1, 2), new queries(1, 2, 4),
new queries(2, 1, 5)];
 
// answer the Queries
answerQueries(arr, que, n, q);
 
// This code is contributed by phasing17

16
9

Complejidad de tiempo: O(logN) por consulta 
Espacio auxiliar: O(N)