Ленивое Распространение
Я решал GSS3 в спой используя ленивое распространение в деревьях сегментов. Я ссылался на этот блог:
Ленивое Распространение
Как мне продолжить этот вопрос, используя ленивое распространение, и я не мог понять, как ленивый массив используется в этом блоге?
#include<iostream>
#include<iomanip>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
int tree[(2*MAX)+1],arr[MAX],lazy[(2*MAX)+1];
void build_tree(int node ,int a,int b)
{
if(a > b) return;
if(a==b)
{
tree[node] = arr[a];
return;
}
build_tree(node*2,a,(a+b)/2);
build_tree(node*2+1,((a+b)/2)+1,b);
tree[node] = max(tree[node*2],tree[node*2+1]);
}
void update_tree(int node,int a,int b,int i,int j,int value)
{
if(lazy[node]!=0)
{
tree[node]+=lazy[node];
if(a!=b)
{
lazy[node*2]+= lazy[node];
lazy[node*2+1]+= lazy[node];
}
lazy[node] = 0;
}
if(a > b || a > j || b < i)
return;
if(a>=i && b<=j)
{
tree[node]+=value;
if(a!=b)
{
lazy[node*2]+= value;
lazy[node*2+1]+= value;
}
return;
}
update_tree(node*2,a,((a+b)/2),i,j,value);
update_tree(node*2+1,((a+b)/2)+1,b,i,j,value);
tree[node] +=(tree[node*2]+tree[node*2+1]);
}
int query_tree(int node,int a,int b,int i,int j)
{
if(a > b || a > j || b < i) return -inf;
if(lazy[node]!=0)
{
tree[node]+=lazy[node];
if(a!=b)
{
lazy[node*2]+= lazy[node];
lazy[node*2+1]+= lazy[node];
}
lazy[node] = 0;
}
if(a>=i && b<=j) return tree[node];
int q1 = query_tree(node*2,a,((a+b)/2),i,j);
int q2 = query_tree(node*2+1,((a+b)/2)+1,b,i,j);
int res = max(q1,q2);
return res;
}
int main()
{
int n,m;
scanf("%d",&n);
memset(lazy, 0, sizeof lazy);
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
build_tree(1, 0, n-1);
scanf("%d",&m);
for(int i=0;i<m;i++)
{
int q;
scanf("%d",&q);
if(q==0)
{
int x,y;
scanf("%d",&x);
scanf("%d",&y);
update_tree(1,0,n-1,x,y);
// What Should i do here ?
}
if(q==1)
{
int x,y;
scanf("%d",&x);
scanf("%d",&y);
query_tree(1,0,n-1,x-1,y-1,);
}
}
return 0;
}
Решение
lazy массив используется, чтобы указать, что есть ожидающее обновление для узла, и это должно быть обработано всякий раз, когда это возможно.
когда lazy установлен?
Когда рекурсия обновления достигает узла, который представляет диапазон полностью, вместо продолжения обновления дочерних элементов, она просто устанавливает ожидаемое значение для них в ленивом массиве, указывая, что некоторое время в будущем его дочерние элементы также должны быть обновлены. Затем он возвращается из рекурсии, избегая остальной части своего поддерева.
когда lazy используется?
Всякий раз, когда узел посещается во время обновления или запроса, рекурсия сначала проверяет наличие отложенного обновления и сначала применяет его (распространяя значение lazy для дочерних узлов).
Другие решения