Lazy Propagation

Hey leppy, i am facing problem understanding lazy propagation. It's been a week for me and i am still not able to understand this concept. I didn't clearly get your point in the above post. Suppose we call update on (3,7) for segment tree (1,10). How do we proceed and handle flags for (1,10) (1,5) (6,10)..?? I actually dont understand how do we handle flags of segments that either includes the update or query interval or intersect with it..Here are the functions that i have coded which of course dont work correctly..

[bbone=text,240]void update(long int node,long int b,long int e,long int i,long int j)
{
if(b>j || e

if(b>=i && e<=j)
{
    if(flag[node])
    {
        flag[node]=0;
        return;
    }
    else
    {
        tree[node]=e-b+1-tree[node];

        flag[2*node]=!flag[2*node];
        flag[2*node+1]=!flag[2*node+1];

        return;
    }
}
else
{
    if(flag[node])
    {
        flag[node]=0;

        tree[node]=e-b+1-tree[node];

        flag[2*node]=!flag[2*node];
        flag[2*node+1]=!flag[2*node+1];
    }
    update(2*node,b,(b+e)/2,i,j);
    update(2*node+1,(b+e)/2+1,e,i,j);

    tree[node]=tree[2*node]+tree[2*node+1];
    return;
}

}

long int query(long int node,long int b,long int e,long int i,long int j)
{
long int l,r;

if(b>j || e<i) return -1;

if(b>=i && e<=j)
{
    if(!flag[node]) return tree[node];
    else
    {
        flag[node]=0;

        tree[node]=e-b+1-tree[node];

        flag[2*node]=!flag[2*node];
        flag[2*node+1]=!flag[2*node+1];

        return tree[node];
    }
}
else
{
    if(flag[node])
    {
        flag[node]=0;

        tree[node]=e-b+1-tree[node];

        flag[2*node]=!flag[2*node];
        flag[2*node+1]=!flag[2*node+1];
    }
    l=query(2*node,b,(b+e)/2,i,j);
    r=query(2*node+1,(b+e)/2+1,e,i,j);

    if(l==-1) return tree[node]=r;
    if(r==-1) return tree[node]=l;
    return tree[node]=l+r;


    //return tree[node]=query(2*node,b,(b+e)/2,i,j)+query(2*node+1,(b+e)/2+1,e,i,j);
}

}[/bbone]

I am trying to solve LITE/Flipping coins problem.

Please help me out with this..

Update [3,7] assuming no nodes are flagged for update

[1,10] - update value for node after updating children.
[1,5] - update value for node after updating children.
[3,5] - flag for later update and update value.
[6,10] - update value of node after updating children.
[6,7] - flag for later update and update value.

It's essentially just a DFS with a postorder updating of the values in the nodes.

I was lazy writing this so I used [3,5]. My actual implementation would split [1,5] into [1,3] and [4,5].

Thanks for reply leppy. My code works correctly for the initial queries (when no segments are flagged for updates). The problem actually comes out when i have to handle updates considering there have been some previous queries and updates (and so the flags of segements maybe 0 or 1). I am not able to figure out how to handle previously set or reset flags..If you could throw some light on that with the previous example, it'd certainly enlighten me more

Update [3,7] assuming [1,5] is flagged for update.
[1,10] update value after updating children
[1,5] push update flag to [1,2] and [3,5]. Update value after updating children.
[3,5] update value. Don't push update flag because the state of [3,3] and [4,5] will be flipped twice, which is the same as none.

Helow leppy!
I'm solving the problem of flipping coins too, and I'm getting TLE.
How can I improve my approach?
my code for update is this:

removed after getting accepted

I'm representing the segment tree as an array with the root in the position 0 (no 1). So the childs of node n are 2*n+1 and 2*n+2.
In my code the variable nm is an array that mantains the elements that Need Modify.

Remove your code please.

I am trying to solve the flipping coin problem and unable to understand the lazy propagation method clearly. I searched on internet and found some codes.

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<cstdio>
#include<cmath>
#define MAX 300000
#define loop0(i,j) for(int i=0;i<j;i++)
#define loop1(i,j) for(int i=1;i<j;i++)
using namespace std;
bool flag[MAX];
int value[MAX];
/*void initialize(int node, int b, int e)
{
    if (b == e)
    {
        flag[node] = false;
        value[node] = 0;
    }
    else
    {
        initialize(2 * node, b, (b + e) / 2);
        initialize(2 * node + 1, (b + e) / 2 + 1, e);
        value[node] = 0;
        flag[node] = false;
    }
}*/
int update(int node, int b, int e, int i, int j)
{
    int p1, p2;
    if (i > e || j < b)
        return 0;
    if (b >= i && e <= j)
    {
        if(b==e)
        {
            if(flag[node] == true)
                return 1;
            else
                return 0;
        }
        else if(flag[node] == true)
        {
            flag[node] = false;
            flag[2*node] = !flag[2*node];
            flag[2*node+1] = !flag[2*node+1];
            p1 = update(2 * node, b, (b + e) / 2, i, j);
            p2 = update(2 * node + 1, (b + e) / 2 + 1, e, i, j);
            return value[node] = p1 + p2;
        }
        else
            return value[node];
    }
    else
    {
        if(flag[node]==true)
        {
            flag[node]=false;
            flag[2*node]=!flag[2*node];
            flag[2*node+1]=!flag[2*node+1];
        }
        p1 = update(2 * node, b, (b + e) / 2, i, j);
        p2 = update(2 * node + 1, (b + e) / 2 + 1, e, i, j);
        return value[node] = p1 + p2;
    }
}
int query(int node, int b, int e, int i, int j)
{
    int p1, p2;
    if (i > e || j < b)
        return 0;
    if (b >= i && e <= j)
    {
        flag[node] = !flag[node];
        return value[node] = e - b + 1 - value[node];
    }
    else
    {
        if(flag[node]==true)
        {
            flag[node]=false;
            flag[2*node]=!flag[2*node];
            flag[2*node+1]=!flag[2*node+1];
        }
        p1 = query(2 * node, b, (b + e) / 2, i, j);
        p2 = query(2 * node + 1, (b + e) / 2 + 1, e, i, j);
        if(p1==-1)
            p1=0;
        if(p2==-1)
            p2=0;
        return (value[node] = p1 + p2);
    }
}
int main()
{
       int k, t, tests, m, n;
       int f, a, b, z;
//       cin >> tests >> m;
       scanf("%d %d",&tests,&m);
   //    initialize(1, 0, tests-1);
       loop0(i, m)
       {
           scanf("%d %d %d",&f,&a,&b);
//           cin >> f >> a >> b;
           if(f==0)
               value[1] = query(1,0,tests-1,a,b);
           else
               printf("%d\n",update(1,0,tests-1,a,b));
//               cout << update(1,0,tests-1,a,b) <<"\n";
       }
       return 0;
}

I don't know whether this is correct or not because its still giving TLE on Codechef. Please explain lazy propagation in detail or tell whether this code is correct or not. I will try to understand it according to the code.

Ignore the code and focus on the posts that I have already made in this topic. Those posts are the main reason that I created this topic.

Do you understand a segment tree correctly first? It's a prerequisite for understanding lazy propagation.

yeah I understood the segment tree, but without lazy propagation its useless. Ok will try to do it again. Doing it from past 10 days

Are you operating using my method where the value in a node with a flag is correct? If so, then this is incorrect:

        if(flag[node]==true)
        {
            flag[node]=false;
            flag[2*node]=!flag[2*node];
            flag[2*node+1]=!flag[2*node+1];
        }

Leppy please help us with some code for update range [i,j] and query sum[i,j]. Except your explanation can't find anything on the internet.Even you explained very clear still fail to implement. It would be really useful not only for me. Thanks.

I prefer not to write code. If you are having a specific problem please feel free to post your misunderstanding and I can attempt to help you.

hey i'm getting WA in flipping coins at codechef can u point out where the mistake might be.i've used lazy propagation and the flags are used to denote that if the coins in the range have to be flipped or not.
here is my code
the problem is codechef.com/problems/FLIPCOIN1
thanks got ac

Please use code tags when posting code. Please post a link to the problem.

plz reply

Your update function is incorrect.

can u plz give me a test case where my code would fail.

Think carefully about why you are performing each step. You will quickly find your mistake if you think about what you are doing. This is a very important skill to learn.

i have another problem with lazy propagation method :

suppose we have 4 kind of updates operation consequently, and then a query for a range result . so 4 update should be done on some ranges one by one , but i think having 4 updates consequently on big intervals don't allow to updates done one by one on small intervals and this cause a problem.
let's see an example on FlipConis Problem (codechef.com/problems/FLIPCOIN) :

6 5
0 0 6
0 0 3
0 2 5
0 1 6
1 1 6

so what's the order of updates ? when updates done on small intervals ??
i'm so confused about how several updates done one by one.

sorry for my poor english
thanks