Dado un Array arr[] de enteros positivos de tamaño n. Estamos obligados a realizar las siguientes 3 consultas en una array dada:
1) Dados L y R, tenemos que encontrar la suma de los cuadrados de todos los elementos que se encuentran en el rango [L,R]
2) Dados L, R y X, tenemos que configurar todos los elementos que se encuentran en el rango [L,R] a X
3) Dados L, R y X, tenemos que incrementar el valor de todos los elementos que se encuentran en el rango [L,R] en X
Formato de entrada : la primera línea contiene el número de casos de prueba T
La siguiente línea contiene dos enteros positivos: N (Tamaño de la array) y Q (Número de consultas que se realizarán).
La siguiente línea contiene N enteros de array
Cada una de las siguientes líneas Q contiene las consultas Q que se van a realizar. Cada línea comienza con un número, que indica el tipo de consulta seguido de los argumentos de entrada requeridos. El formato de entrada para las 3 consultas se verá así:
0 LRX: establece todos los números en el rango [L, R] en «X»
1 LRX: AGREGAR «X» a todos los números en el rango [L, R]
2 LR : Devuelve la suma de los cuadrados de los números en Rango {L, R]
Formato de salida : para cada caso de prueba, genere «Caso <TestCaseNo>:» en la primera línea y luego genere la suma de cuadrados para cada consulta de tipo 2 en líneas separadas.
Input:
1
3 3
1 2 3
0 1 2 2
1 1 3 3
2 1 3
Output : Case 1:
86
Explanation : With 1st query (type 0), array elements from range [1,2] will set as 2. Updated array will become [2,2,3]
With 2nd query (type 1), array elements from range [1,3] will be incremented by 3. Updated array will become [5,5,6]
With 3rd query (type 2), Sum of Squares for range [1,3] will be 5^2+5^2+6^2 =86
Input:
1
4 5
1 2 3 4
2 1 4
0 3 4 1
2 1 4
1 3 4 1
2 1 4
Output : Case 1:
30
7
13
Solución optimizada
Ejemplo de árbol de segmentos
Con la ayuda del árbol de segmentos con propagación perezosa, podemos realizar todas las consultas dadas en tiempo O (logn).
Para saber cómo funciona Segment Tree, siga este enlace: https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/
Para esto, crearemos un árbol de segmentos con dos variables: la primera almacenará la suma de los cuadrados en un rango y la otra almacenará la suma de los elementos en el rango dado. (Discutiremos esto más adelante por qué necesitamos dos variables aquí). Para actualizar los valores en el rango dado, usaremos la técnica de propagación diferida.
Para obtener más información sobre el enlace de uso de propagación perezosa: https://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/
Aquí, si tenemos que establecer todos los números en X en un rango determinado, podemos usar esta fórmula para actualizar los valores de un Node en particular (que se encuentra en el rango dado):
Suma de cuadrados actualizada = (R-L+1)*X*X
Suma actualizada = (R-L+1)*X
(Como hay elementos R-L+1 presentes en ese Node en particular que deben configurarse como X)
Si necesitamos incrementar todos los valores en el rango dado [L,R] con el valor X, podemos usar esta fórmula para actualizar los valores para un Node en particular (que se encuentra en el rango dado) –
Suma del cuadrado actualizada = Suma del cuadrado en el rango [L,R] + (R-L+1)*X*X + 2*X*(suma en el rango [L,R])
Suma actualizada = Suma en rango [L,R] + (R-L+1)*X
(Como hay elementos R-L+1 presentes debajo de ese Node en particular que deben incrementarse en X. El valor de cada Node se puede representar como: (Previous_val + X). Para calcular una nueva suma de cuadrados para un Node raíz, podemos usa esta expresión –
(Valor_anterior1+ x)^2 + (Valor_anterior2 + x)^2 + ….. (para todos los Nodes secundarios)
La expresión anterior se simplificará a Suma de cuadrados en el rango [L,R] + (R-L+1)*X*X + 2*X*(suma en el rango [L,R])
Aquí puede ver que necesitamos la suma de los elementos para el cálculo, por lo tanto, la hemos almacenado en nuestro árbol de segmentos junto con la suma de los cuadrados para ajustar nuestro cálculo.
Cómo actualizar usando árboles perezosos
Aquí puedes ver que necesitamos 3 árboles perezosos:
1. Para mantener la actualización establecida
2. Para mantener el incremento por actualización X
3. Para mantener el orden de las operaciones, en caso de que surjan múltiples consultas para un solo Node
Ahora creando 3 árboles perezosos, no será efectivo en el espacio. Pero podemos resolver esto creando 1 árbol perezoso (cambio, tipo) con dos variables: una para mantener el valor de actualización (X) y otra para el tipo (qué actualización necesitamos incrementar o establecer).
Ahora, para manejar el orden de múltiples consultas en un solo Node, hay dos posibilidades:
1) Primero incremente y luego establezca la consulta : en este caso, en realidad no necesitamos incrementar el valor, podemos establecer directamente el valor en X. Debido a que establecer el valor de un Node en X, antes y después del incremento seguirá siendo el mismo.
2) Primero establezca y luego incremente la consulta : aquí estamos actualizando efectivamente el valor de cada Node como: X (consulta establecida) + X (consulta incrementada). Por lo tanto, podemos mantener nuestro tipo de consulta como establecido y el valor de cambio (es decir, en qué Nodes se establecerá el valor) como (X_set + X_increment)
Por ejemplo, arr[]=[1,2,3,4] primero configure [3,4] con 2 y luego incremente [3,4] con 1
array después de establecer consulta = [1,2,2,2]
array después de consulta de incremento = [1,2,3,3]
Podemos lograr esto en una operación estableciendo el valor para todos los Nodes de rango dados como:
(X_conjunto + X_incremento) = 2 + 1 = 3
Array actualizada = [1,2,3,3]
C++
// We will use 1 based indexing
// type 0 = Set
// type 1 = increment
#include<bits/stdc++.h>
using namespace std;
class segmenttree{
public:
int sum_of_squares;
int sum_of_element;
};
class lazytree{
public:
int change;
int type;
};
// Query On segment Tree
int query(segmenttree*tree,lazytree*lazy,int start,int end,int low,int high,int treeindex){
if(lazy[treeindex].change!=0){
int change=lazy[treeindex].change;
int type=lazy[treeindex].type;
if(lazy[treeindex].type==0){
tree[treeindex].sum_of_squares=(end-start+1)*change*change;
tree[treeindex].sum_of_element=(end-start+1)*change;
if(start!=end){
lazy[2*treeindex].change=change;
lazy[2*treeindex].type=type;
lazy[2*treeindex+1].change=change;
lazy[2*treeindex+1].type=type;
}
}
else{
tree[treeindex].sum_of_squares+=((end-start+1)*change*change)+(2*change*tree[treeindex].sum_of_element);
tree[treeindex].sum_of_element+=(end-start+1)*change;
if(start!=end){
if(lazy[2*treeindex].change==0 || lazy[2*treeindex].type==1){
lazy[2*treeindex].change+=change;
lazy[2*treeindex].type=type;
}else{
lazy[2*treeindex].change+=change;
}
if(lazy[2*treeindex+1].change==0 || lazy[2*treeindex+1].type==1){
lazy[2*treeindex+1].change+=change;
lazy[2*treeindex+1].type=type;
}else{
lazy[2*treeindex+1].change+=change;
}
}
}
lazy[treeindex].change=0;
}
if(start>high || end<low){
return 0;
}
if(start>=low && high>=end){
return tree[treeindex].sum_of_squares;
}
int mid=(start+end)/2;
int ans=query(tree,lazy,start,mid,low,high,2*treeindex);
int ans1=query(tree,lazy,mid+1,end,low,high,2*treeindex+1);
return ans+ans1;
}
// Update on Segment Tree
void update(int*arr,segmenttree*tree,lazytree*lazy,int start,int end,int low,int high,int change,int type,int treeindex){
if(lazy[treeindex].change!=0){
int change=lazy[treeindex].change;
int type=lazy[treeindex].type;
if(lazy[treeindex].type==0){
tree[treeindex].sum_of_squares=(end-start+1)*change*change;
tree[treeindex].sum_of_element=(end-start+1)*change;
if(start!=end){
lazy[2*treeindex].change=change;
lazy[2*treeindex].type=type;
lazy[2*treeindex+1].change=change;
lazy[2*treeindex+1].type=type;
}
}
else{
tree[treeindex].sum_of_squares+=((end-start+1)*change*change)+(2*change*tree[treeindex].sum_of_element);
tree[treeindex].sum_of_element+=(end-start+1)*change;
if(start!=end){
if(lazy[2*treeindex].change==0 || lazy[2*treeindex].type==1){
lazy[2*treeindex].change+=change;
lazy[2*treeindex].type=type;
}else{
lazy[2*treeindex].change+=change;
}
if(lazy[2*treeindex+1].change==0 || lazy[2*treeindex+1].type==1){
lazy[2*treeindex+1].change+=change;
lazy[2*treeindex+1].type=type;
}else{
lazy[2*treeindex+1].change+=change;
}
}
}
lazy[treeindex].change=0;
}
if(start>high || end<low){
return;
}
if(start>=low && high>=end){
if(type==0){
tree[treeindex].sum_of_squares=(end-start+1)*change*change;
tree[treeindex].sum_of_element=(end-start+1)*change;
if(start!=end){
lazy[2*treeindex].change=change;
lazy[2*treeindex].type=type;
lazy[2*treeindex+1].change=change;
lazy[2*treeindex+1].type=type;
}
}else{
tree[treeindex].sum_of_squares+=((end-start+1)*change*change)+(2*change*tree[treeindex].sum_of_element);
tree[treeindex].sum_of_element+=(end-start+1)*change;
if(start!=end){
if(lazy[2*treeindex].change==0 || lazy[2*treeindex].type==1){
lazy[2*treeindex].change+=change;
lazy[2*treeindex].type=type;
}else{
lazy[2*treeindex].change+=change;
}
if(lazy[2*treeindex+1].change==0 || lazy[2*treeindex+1].type==1){
lazy[2*treeindex+1].change+=change;
lazy[2*treeindex+1].type=type;
}else{
lazy[2*treeindex+1].change+=change;
}
}
}
return;
}
int mid=(start+end)/2;
update(arr,tree,lazy,start,mid,low,high,change,type,2*treeindex);
update(arr,tree,lazy,mid+1,end,low,high,change,type,2*treeindex+1);
tree[treeindex].sum_of_squares=tree[2*treeindex].sum_of_squares+tree[2*treeindex+1].sum_of_squares;
tree[treeindex].sum_of_element=tree[2*treeindex].sum_of_element+tree[2*treeindex+1].sum_of_element;
}
// creation of segment tree
void create(int*arr,segmenttree*tree,int start,int end,int treeindex){
if(start==end){
tree[treeindex].sum_of_squares=start*start;
tree[treeindex].sum_of_element=start;
return;
}
int mid=(start+end)/2;
create(arr,tree,start,mid,treeindex*2);
create(arr,tree,mid+1,end,2*treeindex+1);
tree[treeindex].sum_of_squares=tree[treeindex*2].sum_of_squares+tree[2*treeindex+1].sum_of_squares;
tree[treeindex].sum_of_element=tree[treeindex*2].sum_of_element+tree[2*treeindex+1].sum_of_element;
}
int main() {
int t;
cin>>t;
int case1=1;
while(t--){
cout<<"Case "<<case1++<<":"<<endl;
int n,q;
cin>>n>>q;
int*arr=new int[n+1];
for(int i=1;i<=n;i++){
cin>>arr[i];
}
segmenttree*tree=new segmenttree[2*n];
lazytree*lazy=new lazytree[2*n];
create(arr,tree,1,n,1);
while(q--){
int type;
cin>>type;
if(type==2){
int start,end;
cin>>start>>end;
cout<<query(tree,lazy,1,n,start,end,1)<<endl;
}else{
int start,end,change;
cin>>start>>end>>change;
update(arr,tree,lazy,1,n,start,end,change,type,1);
}
}
}
}
Complejidad del tiempo:
La complejidad del tiempo para la construcción del árbol es O(n). Hay un total de 2n-1 Nodes, y el valor de cada Node se calcula solo una vez en la construcción del árbol.
La complejidad del tiempo para consultar es O (Iniciar sesión).
La complejidad del tiempo de actualización también es O (Iniciar sesión).
Complejidad espacial : O(2*N) .
Publicación traducida automáticamente
Artículo escrito por yashbeersingh42 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA