Clever Geek Handbook

Lazy Spread Segment Tree - Multiply all values ​​in a range

I have the following code, which is for a lazy spread partition tree, that I could write. This code does not work for multiplying all numbers in a range with a value such as x. I think I am doing something wrong in the update_mult function. The tree supports the sum of the range.

I couldn't figure out the issue with update_mult. Experts, can you please help me find out where I am going wrong with the implementation?

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <set>
#include <assert.h>
#include <cstring>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <time.h>
#include <climits>

using namespace std;

#define FOR(i,a,b) for(int i=a;i<b;++i)
#define FORR(i,a,b) for(int i=a;i>=b;--i)
#define FORC(it,container) for(typeof(container.begin()) it=container.begin();it!=container.end();++it)
#define INT(x) scanf("%d",&x)
#define LLD(x) scanf("%lld",&x)
#define STR(x) scanf("%s",x)
#define CHAR(x) scanf("%c",&x)
#define PINT(x) printf("%d\n",x)
#define PLLD(x) printf("%lld\n",x)
#define CLR(x) memset(x,0,sizeof(x));

const int INF = INT_MAX;
const int MAX = 1000001;


typedef long long LL;

LL arr[MAX+5];
LL MOD = 1e9 + 7;

struct data
{
    LL sumsq;
    LL sum;
    LL lazyset;
    LL setval;
    LL lazyMult;
    LL lazyVal;
    LL addval;

    void assignleaf()
    {

    }
    void assignleaf(int idx ,int val)
    {

    }

    void combine(data &l, data &r)
    {
        sum = (l.sum + r.sum)%MOD;
    }
};

data tree[10*MAX+5];

void pushdown(int node,int segs,int sege)
{
    int mid = segs+sege; mid /= 2;

    if(tree[node].lazyset==1)
    {
            tree[node].lazyset=0;

            tree[2*node].lazyset=1;
            tree[2*node+1].lazyset=1;

            tree[2*node].setval = tree[node].setval; 
            tree[2*node+1].setval = tree[node].setval;

            tree[2*node].sum = ((mid-segs+1)*tree[node].setval)%MOD;
            tree[2*node+1].sum = ((sege-mid)*tree[node].setval)%MOD;

            tree[2*node].addval=0;
            tree[2*node+1].addval=0;

    }

    if(tree[node].lazyMult==1)
    {
            tree[node].lazyMult=0;

            tree[2*node].lazyMult=1;
            tree[2*node+1].lazyMult=1;


            tree[2*node].sum = (tree[2*node].sum  * tree[node].lazyVal)%MOD;
            tree[2*node+1].sum = (tree[2*node+1].sum  * tree[node].lazyVal)%MOD;

            tree[2*node].addval=0;
            tree[2*node+1].addval=0;
    }

    if(tree[node].addval)
    {

            tree[2*node].addval = (tree[2*node].addval +tree[node].addval)%MOD;
            tree[2*node+1].addval = (tree[2*node+1].addval +tree[node].addval)%MOD; 

            tree[2*node].sum = (tree[2*node].sum + ((mid-segs+1)*tree[node].addval)%MOD)%MOD;
            tree[2*node+1].sum =(tree[2*node+1].sum+ ((sege-mid)*tree[node].addval)%MOD)%MOD;

            tree[node].addval = 0;
    }   
}

void build_tree(int node,int s,int e)
{
    tree[node].addval=0;
    tree[node].lazyset=0;

    if(s>e) return;

    if(s==e)
    {
        tree[node].sum = arr[s];
        return;
    }

    int mid=(s+e)/2;

    build_tree(2*node,s,mid);
    build_tree(2*node+1,mid+1,e);

    tree[node].combine(tree[2*node],tree[2*node+1]);

}

LL query(int node,int segs,int sege,int qs,int qe)
{

//cout<<" q -- node = "<<node<<" segs = "<<segs<<" sege = "<<sege<<" qs = "<<qs<<" qe =  "<<qe<<endl;


    if(segs>sege || segs>qe || sege < qs) 
    {
        if(tree[node].lazyset||tree[node].addval)
             pushdown(node,segs,sege);

        return 0;

    }

    if(tree[node].lazyset || tree[node].addval)
        pushdown(node,segs,sege);

    if(segs>=qs && sege<=qe)
    {

    //cout<<"q1 node = "<<node<<" segs = "<<segs<<" sege = "<<sege<<" sumsq  = "<<tree[node].sumsq<<endl;
        return tree[node].sum % MOD;

    }

    int mid= segs+sege; mid /= 2;


    return (query(2*node,segs,mid,qs,qe) + query(2*node+1,mid+1,sege,qs,qe))%MOD;

}

//comm=1
void update_add(int node,int segs,int sege,int qs,int qe,int x)
{

    if(segs>sege||segs>qe||sege<qs) return;

    if(segs>=qs && sege<=qe)
    {
        tree[node].addval = (tree[node].addval+x)%MOD;
        tree[node].sum   = (tree[node].sum + ((LL)(sege-segs+1)*x)%MOD)%MOD;
        return;
    }

    int mid= segs+sege; mid /= 2;

    if(tree[node].lazyset || tree[node].addval)
        pushdown(node,segs,sege);

    update_add(2*node,segs,mid,qs,qe,x);
        update_add(2*node+1,mid+1,sege,qs,qe,x);

    tree[node].combine(tree[2*node],tree[2*node+1]); 


}

void update_mult(int node,int segs,int sege,int qs,int qe,LL x)
{

//cout<<" ua -  node = "<<node<<" segs = "<<segs<<" sege = "<<sege<<" qs = "<<qs<<" qe =  "<<qe<<" x = "<<x<<endl;


    if(segs>sege||segs>qe||sege<qs) return;

    if(segs>=qs && sege<=qe)
    {
        //tree[node].addval = (tree[node].addval * x)%MOD;
        tree[node].sum   = (tree[node].sum * x)%MOD;
        tree[node].lazyMult = 1;
        tree[node].lazyVal = x;
        tree[node].addval = 0;
        return;
    }

    int mid= segs+sege; mid /= 2;

    if(tree[node].lazyMult || tree[node].addval)
        pushdown(node,segs,sege);

    update_mult(2*node,segs,mid,qs,qe,x);
        update_mult(2*node+1,mid+1,sege,qs,qe,x);

    tree[node].combine(tree[2*node],tree[2*node+1]); 


}

//comm=0
void update_set(int node,int segs,int sege,int qs,int qe,LL x)
{

    //cout<<" node = "<<node<<" segs = "<<segs<<" sege = "<<sege<<" qs = "<<qs<<" qe =  "<<qe<<" x = "<<x<<endl;

    if(segs>sege||segs>qe||sege<qs)
        return;


    if(segs>=qs && sege<=qe)
    {
        tree[node].lazyset= 1;
        tree[node].setval=x;
        tree[node].sum   = ((LL)(sege-segs+1)*x)%MOD;
        tree[node].addval = 0;
        return;
    }

    if(tree[node].lazyset || tree[node].addval)
        pushdown(node,segs,sege);


      int mid= segs+sege; 
      mid /= 2;


     update_set(2*node,segs,mid,qs,qe,x);
     update_set(2*node+1,mid+1,sege,qs,qe,x);

    tree[node].combine(tree[2*node],tree[2*node+1]);


}





int main()
{

    int test = 1;

    FOR(tt,1,test+1)
    {
        int n,q; INT(n); INT(q);


        CLR(arr);
        CLR(tree);

        FOR(i,0,n)
            LLD(arr[i]);

        build_tree(1,0,n-1);

        while(q--)
        {
            int comm; int l,r; 

            INT(comm); INT(l); INT(r);


            if(comm==3)
            {
                //set x 
                LL x; LLD(x);       
                update_set(1,0,n-1,l-1,r-1,x);      

            }
            else if(comm==1)
            {
                //add x
                LL x; LLD(x);               
                update_add(1,0,n-1,l-1,r-1,x);

            }
            else if(comm==2)
            {
                //add x
                LL x; LLD(x);               
                update_mult(1,0,n-1,l-1,r-1,x);

            }
            else if(comm==4)
            {
                LL ans = query(1,0,n-1,l-1,r-1);

                PLLD(ans);

            }

        }

    }

return 0;
}
+3


source to share


3 answers


I think the problem is in the order of the code blocks in the pushdown function.



0


source


When you are multiplying, how can you set the addval of the child to 0. In the case of initialization, this is fine, because now any multiplication and addition becomes redundant, but not in the case of multiplication. In the case of multiplication, you cannot do this, because you still need to add this value. Moreover, I think the order of addition and multiplication might also come into play.



0


source


Try this test case, you figure out your error:

4 10

1 3 4 5

1 1 2 1

4 1 4

2 1 3 4

4 1 4

3 2 4 2

4 1 4

0


source






More articles:


All Articles