Friday, 19 June 2015

seg tree sum in the range with update

#include<iostream>
#include<string.h>
long long int arr[1000005],seg[10000005],lzy[10000005];
using namespace std;
#define inf 100000001
 int ups,upe,qs,qe;//qs = query start index , qe= query end index  
 long long int val;// ups = update start index , upe =update end index
 long long  int qry(int index,int start,int end)
  {
 
     if(lzy[index]!=0)
      {
      seg[index]+=lzy[index]*(end-start+1);
      if(start!=end)
      {
     
     
      lzy[2*index]+=lzy[index];
      lzy[2*index+1]+=lzy[index];
      }
      lzy[index]=0;
      }
       if(start>end || end<qs || start>qe)
     {
      return 0;
     }
      if(start>=qs && end<=qe)
       {
        return  seg[index];
       
       }
      long long  int q1=qry(2*index,start,(start+end)/2);
      long long  int q2=qry(2*index+1,((start+end)/2)+1,end);
       return q1+q2;
 
  }
 
 
void update(int index,int start,int end)
{
if(lzy[index]!=0)// means index contain some un updated range so update seg tree and  make its   child lazy if have child
 {
  seg[index]+=lzy[index]*(end-start+1);
  //  checking if having child than make it lzy
  if(start!=end)//  adding lzy[index] bcos making parent unlaxy and if parent have any child tnhan mak it lazy equal
                // exactly to its parent amount .......
  {
 
     
      lzy[2*index]+=lzy[index];
      lzy[2*index+1]+=lzy[index];
  }
  lzy[index]=0;
 
 }
 if(start>end || start>upe || end<ups) return ;// if(range in complitly out of range sooo need not to update ;;;;)
 if(start>=ups && end<=upe)//     ( means if range (start and end ) is complitle within the update qry )...
  {
    seg[index]+=(end-start+1)*val;// just update the parent  and make its chile lzy so thate will be update latter
    if(start!=end)/// adding  only val sice it is new dew it is not propogating from parent
     {
   
     
      lzy[2*index]+=val;
      lzy[2*index+1]+=val;
     }
     return;
   
  }
 
   update(2*index,start,(start+end)/2);
   update(2*index+1,((start+end)/2)+1,end);
 
   seg[index]=seg[2*index]+seg[2*index+1];
 
 }



int main()
 {
  int t;
  cin>>t;
    while(t--)
     {
     
   
        int n,q;
      cin>>n>>q;
      memset(seg,0,10000001);
      memset(lzy,0,10000001);
         while(q--)
          {
          int qq;
          cin>>qq;
           if(qq==0)
            {
            cin>>ups>>upe>>val;
            ups-=1;
            upe-=1;
            update(1,0,n-1);
           
           
            }
            else
             {
              cin>>qs>>qe;
              qs-=1;
              qe-=1;
              long long int  ans=  qry(1,0,n-1);
               cout<<ans<<endl;
             
             
             }
         
     
          }
      }
  return 0;
 }

No comments:

Post a Comment