<分区>
我正在解决 GSS3 in spoj在线段树中使用惰性传播。我引用了这个博客: Lazy Propagation
我应该如何使用惰性传播来解决这个问题，我不明白这个博客中是如何使用惰性数组的？
#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;
}