Lazy Propagation

Question

I was solving GSS3 in spoj using lazy propagation in segment trees.I referred to this blog : Lazy Propagation

How should i proceed in this question using lazy propagation and i couldn't understand how lazy array is being used in this blog?

#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

The lazy array is used to indicate that there is a pending update to the node and it must be processed whenever possible.

When lazy is set?

When the update recursion reaches a node that represents the range entirely, instead of continue updating the children, it just sets the expected value for them in the lazy array, indicating that some time in the future its children must be updated also. Then it returns from the recursion, avoiding the rest of its subtree.

When lazy is used?

Whenever a node is visited during the update or query, the recursion first checks if there is a lazy update pending and applies it first (propagating the lazy value to the node's children).