Lazy Propagation

Posts on all other matters, possibly unrelated to programming or this site

Lazy Propagation

Postby matrix_4 » Fri Nov 26, 2010 13:21

I found a problem that could be solved with a segment tree using "Lazy Propagation". How does that work?
matrix_4
 
Posts: 8
Joined: Sun Mar 08, 2009 20:41

Re: Lazy Propagation

Postby leppy » Fri Nov 26, 2010 13:41

[Removed Problem Spoilers]

Lazy Propagation means that you only update what you actually need to, when you need to.

For example, if we have a segment tree that covers the range 1-20. If we update segment [1,20], we update only the value of the root node of the tree and set a flag on it's children [1,10] and [11,20] to let them know that they need to be updated.

Next, if we query [6,7] then when we reach a node in the traversal that has the update flag on, we need to flag it's children and update it's value.

[1,10] is flagged for update
query [6,7]
Traversal Route:
[1,10] - push update flag to [1,5] and [6,10] and update value of [1,10]
[6,10] - push update flag to [6,8] and [9,10] and update value of [6,10]
[6.8] - push update flag to [6,7] and [8,8] and update value of [6,8]
[6,7] - push update flag to [6,6] and [7,7] and update value of [6,7]

This leaves [1,5], [6,6], [7,7], [8,8], [9,10] flagged for update.
leppy
Global Moderator
 
Posts: 5699
Joined: Fri Aug 01, 2008 18:06

Re: Lazy Propagation

Postby arpit » Sat Jan 15, 2011 20:10

Hey i am trying to solve the problem http://www.codechef.com/problems/FLIPCOIN using segment trees but its giving TLE. I tried using lazy propagation technique. Is there some problem with the approach.

Code: Select all
changed update function and got AC, thanks leppy
Last edited by arpit on Sun Jan 16, 2011 13:16, edited 1 time in total.
arpit
 
Posts: 88
Joined: Fri Mar 20, 2009 10:05
Location: Hyderabad, India

Re: Lazy Propagation

Postby leppy » Sun Jan 16, 2011 00:26

You don't need to go until b = e. If the range is 1 to 10 and the query range is 1 to 10, that takes only one node to check.
leppy
Global Moderator
 
Posts: 5699
Joined: Fri Aug 01, 2008 18:06

Re: Lazy Propagation

Postby jsrvh » Tue Jan 25, 2011 23:01

thank s Leppy,
quite good explanation of lazy propagation.
:D
jsrvh
 
Posts: 13
Joined: Sun Oct 24, 2010 17:50

Re: Lazy Propagation

Postby jacky001 » Thu Jun 09, 2011 11:39

a HUGIN EXPERT A/S, Gasværksvej 5, DK-9000 Aalborg, Denmark
Received 16 November 2008;
revised 1 June 2009;
accepted 25 August 2009.
Available online 28 January 2010.

Abstract

Even though existing algorithms for belief update in Bayesian networks (BNs) have exponential time and space complexity, belief update in many real-world BNs is feasible. However, in some cases the efficiency of belief update may be insufficient. In such cases minor improvements in efficiency may be important or even necessary to make a task tractable. This paper introduces two improvements to the message computation in Lazy propagation (LP): (1) we introduce myopic methods for sorting the operations involved in a variable elimination using arc-reversal and (2) extend LP with the any-space property. The performance impacts of the methods are assessed empirically.
jacky001
 
Posts: 1
Joined: Thu Jun 09, 2011 11:30

Re: Lazy Propagation

Postby sid_gup » Sun Jul 10, 2011 13:45

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.. :(

Language: Text
void update(long int node,long int b,long int e,long int i,long int j)
{
    if(b>j || e<i) return;
 
    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);
    }
}


I am trying to solve LITE/Flipping coins problem.

Please help me out with this..
sid_gup
 
Posts: 41
Joined: Fri Dec 17, 2010 23:26

Re: Lazy Propagation

Postby leppy » Sun Jul 10, 2011 15:42

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].
leppy
Global Moderator
 
Posts: 5699
Joined: Fri Aug 01, 2008 18:06

Re: Lazy Propagation

Postby sid_gup » Sun Jul 10, 2011 16:33

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 :)
sid_gup
 
Posts: 41
Joined: Fri Dec 17, 2010 23:26

Re: Lazy Propagation

Postby leppy » Sun Jul 10, 2011 17:31

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.
leppy
Global Moderator
 
Posts: 5699
Joined: Fri Aug 01, 2008 18:06

Re: Lazy Propagation

Postby alei » Fri Jun 15, 2012 21:53

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:
Code: Select all
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.
Last edited by alei on Sat Jun 16, 2012 00:24, edited 1 time in total.
alei
 
Posts: 2
Joined: Fri Jun 15, 2012 21:47

Re: Lazy Propagation

Postby alei » Fri Jun 15, 2012 22:44

I replace the cout and cin for scanf and printf and I get accepted!!!!!!!!! :D :D :D :D :D
alei
 
Posts: 2
Joined: Fri Jun 15, 2012 21:47

Re: Lazy Propagation

Postby leppy » Fri Jun 15, 2012 23:57

Remove your code please.
leppy
Global Moderator
 
Posts: 5699
Joined: Fri Aug 01, 2008 18:06

Re: Lazy Propagation

Postby androidify » Sat Jun 23, 2012 13:28

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.

Code: Select all
#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.
androidify
 
Posts: 4
Joined: Sat Jun 23, 2012 13:09

Re: Lazy Propagation

Postby leppy » Sat Jun 23, 2012 18:43

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.
leppy
Global Moderator
 
Posts: 5699
Joined: Fri Aug 01, 2008 18:06

Next

Return to Off-topic

Who is online

Users browsing this forum: No registered users and 1 guest