Using lazy propagation for queries of more than 2 types

1
votes

I have a question with a lot of queries which are of four types:

  1. Add to range.

  2. Initialize a range.

  3. Multiply a range with scalar.

  4. Find running sum over a range.

Since queries are in huge numbers I have to use segment tree with lazy propagation but I am stuck on how to use lazy propagation on more than 2 types of queries. How would I be able to identify that when updates are to be made later, then what type of update(i.e. addition, multiplication, initializing) is to be made?

2
calgorithmsegment-treelazy-propagation
I think you need to explain more about what you're doing (though I recognize that Nafeeur Rahman seems to understand what you're after — but I'm not sure I follow his answer, either). How big are your 'huge numbers' — 10s, 100s, 1000s, more? How are the queries formatted? What data is the running sum summed over? Are the values integers or floating point (or something else)? – Jonathan Leffler
Revisiting this question, I'm still not certain what a range is: [lower, upper) or the set of integers between two bounds? – greybeard
@greybeard range is the elements of array within two bounds where bounds are defined by lower and upper index. – user3933528
There is an array involved? You don't say so. Not in the question proper up to now, that is. – greybeard
Moderator notice: Questions about on-going contests are not off-topic for Stack Overflow. Moderators can and will not police third-party agreements and that includes contest rules. It is up to the contest to discipline or police their rules. Please do not flag this post just because it is about a CodeChef contest. – Martijn Pieters

2 Answers

0
votes

You could possibly give the Update funtcion another argument, call it Query. Depending on the value of that argument, the corresponding operation is done.

For additions and multiplications, the information for the lazy propagation can be contained in two fields:

Let A be the initial value of the leaf and there is an arbitrary series of multiplications and additions, for example: +u +v *w +x *y +z. Apply those operations on lazy1. So its value would be: ((u+v) * w +x) * y + z. lazy2 should only contain the multiplications, this would be w * y.

To update the node, first multiply by lazy2, then add lazy1.

Reason: Apply the operations to the initial value A and you get: A * w * y + ((u+v)*w +x)*y + z. It is trivial that only the multiplications affect the initial value A directly. So those can be stored in one field and the other field could contain the additions and also the multiplications have to be applied on it as the order is important here.

0
votes

1.2.3. This is the simple initialization and update part.

struct info
{
    int prop,sum;
} tree[mx*3];

void update(int node,int b,int e,int i,int j,int x)
{
    if (i > e || j < b) return;
    if (b >= i && e <= j)
    {
        tree[node].sum+=((e-b+1)*x);
        tree[node].prop+=x;
        return;
    }
    int Left=node*2;
    int Right=(node*2)+1;
    int mid=(b+e)/2;
    update(Left,b,mid,i,j,x);
    update(Right,mid+1,e,i,j,x);
    tree[node].sum=tree[Left].sum+tree[Right].sum+(e-b+1)*tree[node].prop;

}

4.This is the query part:

int query(int node,int b,int e,int i,int j,int carry=0)
{
    if (i > e || j < b) return 0;

    if(b>=i and e<=j) return tree[node].sum+carry*(e-b+1);

    int Left=node<<1;
    int Right=(node<<1)+1;
    int mid=(b+e)>>1;

    int p1 = query(Left, b,mid, i, j, carry+tree[node].prop); 
    int p2 = query(Right, mid+1, e, i, j,carry+tree[node].prop);

    return p1+p2;
}

And from main

update(1,1,number_of_element,first_range,last_range,value);
query(1,1,n,first_range,last_range);

Here, tree is the segment tree. Every node will contain two informations. One is with which number you added before. prop will store that history. And sum is the total value of that node.

**After your comment:

//Initialization:

void init(int node,int b,int e)
{
    if(b==e)
    {
        tree[node]=arr[b];
        return;
    }
    int Left=node*2;
    int Right=node*2+1;
    int mid=(b+e)/2;
    init(Left,b,mid);
    init(Right,mid+1,e);
    tree[node]=tree[Left]+tree[Right];
}