惰性传播

Question

我正在解决 GSS3 in spoj 在段 trees.I 中使用惰性传播的问题，参考了这个博客： 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;

}

Answer 1

lazy数组用于指示节点有待处理的更新，必须尽可能处理它。

什么时候设置`lazy`？

当更新递归到达一个完全代表范围的节点时，它不再继续更新子节点，而是在惰性数组中设置它们的期望值，表明在未来某个时间它的子节点必须被更新还。然后它从递归中returns，避开它的子树的其余部分。

什么时候用`lazy`？

每当在更新或查询期间访问节点时，递归首先检查是否有待处理的惰性更新并首先应用它（将惰性值传播到节点的子节点）。

惰性传播

Lazy Propagation

c++

algorithm

segment-tree

lazy-propagation

什么时候设置`lazy`？

什么时候用`lazy`？

惰性传播

Lazy Propagation

c++

algorithm

segment-tree

lazy-propagation

什么时候设置lazy？

什么时候用lazy？

什么时候设置`lazy`？

什么时候用`lazy`？